이분탐색

[python] 백준 - 2512. 예산

🤔문제 해결 S3 | 이분탐색 이분 탐색의 기본문제 이분탐색이란? 탐색 부분을 두 부분으로 분할해서 답을 찾는 과정이다. 1부터 10까지 값이 있다고 가정했을 때 7이란 값을 찾아보자 최소는 1이고 최대는 10이다. 절반으로 나누면 5인데 운이 좋아서 5가 맞으면 정답, 하지만 찾는 값은 7이므로 정답이 아니다 크기를 비교해서 찾는 값이 5보다 작으면 최대를 줄이고, 찾는 값이 5보다 크면 최소를 늘린다. 찾는 값이 5보다 크므로 최소를 늘린다. 최소는 절반+1 최대는 그대로 10이다. 절반으로 나누면 8 찾는 값은 8보다 작으므로 최대를 줄인다. 최소는 6 최대는 절반-1이다. 절반으로 나누면 6 찾는 값이 6보다 크므로 최소를 늘린다. 최소는 절반+1 최대는 7이다. 절반으로 나누면 7이므로 정답! ..

[python] 프로그래머스 - 지형 편집

🤔문제 해결 Lv4 | 이분탐색 or 완전탐색(?) 이분탐색으로 코드를 구현했더니 효율성에서 실패했다. 그래서 한층한층 값을 저장하고 다음 층의 값을 구할 때는 이전에 저장한 층의 값을 이용하기로 했다. 먼저 2차원 행렬을 일렬로 세운고 오름차순 정렬한다. [[4, 4, 3], [3, 2, 2], [2, 1, 0]] ➡ [0, 1, 2, 2, 2, 3, 3, 4, 4] 다음 제일 낮은 층( 여기서는 0 )으로 평평하게 만들 경우를 구한다. 지형을 빼는 작업만 하면 되므로 ( 전체지형 수 - 가장 낮은층의 지형 수 ) * Q(빼는 비용) 빨간 부분을 다 지우면 높이가 0인 평평한 지형을 만들 수 있다. 값은 21칸 * Q(지우는 값) = 63 이제 일렬로 세운 리스트를 하나하나 탐색한다. ( 맨앞은 했으니..

[python] 프로그래머스 - 징검다리

🤔문제 해결 Lv4 | 이분 탐색 딱 보자마자 이분탐색인지는 모르겠다. 하지만 문제 카테고리에 써있다. 이분탐색을 하려면 어떤 값을 왔다 갔다 이분탐색할지 정해야 한다. 여기서는 답으로 구해야 하는 최댓값을 이분탐색 했다. 먼저 답을 정해놓고 시작한다. 0과 마지막 지점인 distance(25)를 가지고 가운데 값으로 12로 정했다. 이 문제에 답이 12라면 바위를 n개 제거했을 때 최소 거리가 12인 녀석이 있어야 한다. 처음 위치를 0으로 두고 다음 바위까지의 거리가 mid(12) 보다 작으면 제거 아니면 그 바위로 이동 0 에서 2 까지의 거리 2 12: 살려둠 and 14로 이동 14 에서 17 ..