본문 바로가기

이진 탐색4

[백준] 1920번 수 찾기 (Python) 정답 코드 및 풀이는 맨 아래에 있습니다. https://www.acmicpc.net/problem/1920 쉬운 이분 탐색 문제였다. [문제] N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. [입력] 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다. [출력] M개의 줄에 답을 출력한다. 존재하면 1을, 존재하.. 2023. 2. 14.
이진 탐색 - 정렬된 배열에서 특정 수의 개수 구하기 [문제] N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 {1,1,2,2,2,2,3}이 있을 때 x = 2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다. [입력] 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다. (1 2023. 2. 14.
이진 탐색 - 떡볶이 떡 만들기 이 문제는 백준 나무 자르기 문제와 동일한 문제로 아래 링크에서 채점이 가능합니다. https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net [문제] 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다... 2023. 2. 14.
이진 탐색 이론 bisect이진 탐색이란, 기존의 하나하나 검사하는 탐색 방법보다 더 빠른 탐색 알고리즘이다. 원래대로라면 길이가 N인 배열에서 어떠한 원소를 찾고자 한다면, 처음부터 N개의 원소를 하나하나 검사해보는 방식으로 탐색을 한다. 따라서 기존의 탐색 시간복잡도는 O(N)이다. 하지만 배열이 정렬되어 있다는 가정 하에 이진 탐색은 더 빠른 시간복잡도를 보장한다. 이진탐색이란? 이진탐색이란 정렬되어있는 배열에서 특정 값을 찾는 방법이다. 찾고자 하는 값을 target이라고 할 때, 배열의 중간 위치의 값이 target보다 작은지 큰지를 검사한다. 배열을 반으로 나눈 후 중간 위치의 값이 target보다 작다면 뒤의 배열에서 같은 방식으로 탐색을 반복하고, 크다면 앞의 배열에서 같은 방식으로 탐색을 반복한다. 길이.. 2023. 2. 13.

티스토리툴바