[WEEK 02] 알고리즘 - 이분 탐색 문제풀이

1920. 수 찾기

https://www.acmicpc.net/problem/1920

이분 탐색이라는 개념의 기본이 되는 문제.
이분 탐색을 이용해 입력값이 주어진 수에 존재하는지 확인하는 문제이다.

import sys

sys.stdin = open("1-1_1920.txt", "r")
input = sys.stdin.readline

N = int(input())
A = sorted(list(map(int, input().split())))

M = int(input())
num_list = list(map(int, input().split()))

def binary_search(A, num):
    left = 0
    right = len(A) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if A[mid] == num:
            return 1
        elif A[mid] < num:
            left = mid + 1
        else:
            right = mid - 1
    return 0

for num in num_list:
    print(binary_search(A, num))

결과값이 1에 해당되는 경우에도 0이 함께 출력되는 상황이 발생하였는데, flag를 적절히 이용하여 이러한 문제를 해결할 수 있음을 배웠다.

---

2805. 나무 자르기

https://www.acmicpc.net/problem/2805

입력값이 주어진 수들 중에 존재하는지를 확인하는 것이 아니라 최적화 해답을 찾는 문제라는 점에서 1920. 수 찾기와 다르다.

최적화 문제를 결정 문제로 바꾸는 파라메트릭 서치를 이용해 해결하는 문제이다.

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
heights = sorted(list(map(int, input().split())))

left = 0
right = max(heights)

answer = 0

while left <= right:
    total = 0
    mid = (left + right) // 2
    
    for height in heights:
        if height > mid:
            total += height - mid
    
    if total < M:
        right = mid - 1
    else:
        answer = mid
        left = mid + 1

print(answer)

---

2470. 두 용액

https://www.acmicpc.net/problem/2470

양의 특성값을 가지는 산성 용액과 음의 특성값을 가지는 알칼리 용액을 혼합하여 두 특성값의 합이 0에 가까운 혼합 용액을 만드는 문제이다.

두 변수의 최적의 합을 구한다는 점에서 기존의 이분 탐색 문제들과 다르다.

import sys

input = sys.stdin.readline

N = int(input())
arr = sorted(list(map(int, input().split())))

left = 0
right = N - 1
answer = 10 ** 10
idx = (0, 0)

while left != right:
	if answer > abs(arr[left] + arr[right]):
    	answer = abs(arr[left] + arr[right])
        idx = (left, right)
    
    if arr[left] + arr[right] < 0:
    	left += 1
    elif arr[left] + arr[right] >0:
    	right -= 1
    else:
    	break

print(arr[idx[0]], arr[idx[1]])

일반적인 이분 탐색 문제들과 다르게 반복문의 조건을 left >= right이 아닌 left != right으로 설정한다.

---

11053. 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

import sys

input = sys.stdin.readline

N = int(input())

A = list(map(int, input().split()))

# N개의 모든 수열의 길이는 1부터 시작하기 때문에
lengths = [1] * N

for i in range(1, N):
    for j in range(i):
        if (A[i] > A[j]) and (lengths[i] < lengths[j] + 1):
            lengths[i] = lengths[j] + 1

print(max(lengths))

그렇다고 한다.