[알고리즘] 13일차 (원하는 정수 찾기, 블루레이 만들기, 배열에서 K번째 수 찾기) #백준1920번 #백준2343번 #백준1300번

05-3 이진 탐색

• 이진 탐색은 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다.
• 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.
• 기능: 타깃 데이터 탐색
• 특징: 중앙값 비교를 통한 대상 축소 방식
• 시간 복잡도: O(logN)
• 이진 탐색은 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘이다.
• 구현 및 원리가 비교적 간단하므로 많은 코딩 테스트에서 부분 문제로 요구하는 영역이다.

[이진 탐색의 핵심 이론]

• 이진 탐색은 오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복한다.

1. 현재 데이터셋의 중앙값을 선택한다.
2. 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.
3. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다.
4. 1~3번 과정을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.

📌 문제 029) 원하는 정수 찾기

시간 제한 2초, 실버 IV, 백준 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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

5 # 데이터 개수
4 1 5 2 3
5 # 찾아야 할 숫자 개수
1 3 7 9 5

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

1
1
0
0
1

1단계 문제 분석

• N의 최대 범위가 100,000이므로 단순 반복문으로는 이 문제를 풀 수 없다.
• 이진 탐색을 적용하면 데이터 정렬까지 고려하여 O(nlogn) 시간 복잡도로 해결할 수 있다.
• 이진 탐색은 정렬을 가정하므로 정렬 함수도 사용하자.
• 기본 정렬은 O(nlogn)의 시간 복잡도를 가지므로 정렬을 수행해도 제한 시간을 초과하지 않는다.

2단계 슈도 코드

N(수 개수 저장)
A(수 데이터 리스트 저장)
A 리스트 정렬
M(탐색할 숫자 개수 저장)
target_list(탐색할 수 데이터 리스트 저장)

for M 개수 만큼 반복:
	target(찾아야 하는 수)
    # 이진 탐색 시작
    start(시작 인덱스)
    end(종료 인덱스)
    while 시작 인덱스 <= 종료 인덱스:
    	midi(중간 인덱스)
        midv(중앙값)
        if 중앙값 > target:
        	종료 인덱스 = 중간 인덱스 - 1
        elif 중앙값 < target:
        	시작 인덱스 = 중간 인덱스 + 1
        else:
        	찾았음, 반복문 종료
    if(찾았음) 1 출력
    else 0 출력

3단계 코드 구현

N = int(input())
A = list(map(int, input().split()))
A.sort()
M = int(input())
target_list = list(map(int, input().split()))

for i in range(M):
    find = False
    target = target_list[i]
    # 이진 탐색 시작
    start = 0
    end = len(A) - 1
    while start <= end:
        midi = int((start + end) / 2)
        midv = A[midi]
        if midv > target:
            end = midi - 1
        elif midv < target:
            start = midi + 1
        else:
            find = True
            break
    if find:
        print(1)
    else:
        print(0)

📌 문제 030) 블루레이 만들기

시간 제한 2초, 실버 I, 백준 2343번

강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.
강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.
강토의 각 강의의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다.

9 3 # 레슨 수, 블루레이 개수
1 2 3 4 5 6 7 8 9

출력

첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.

17

1단계 문제 분석

• 이진 탐색의 시작 인덱스는 최대 길이의 레슨이고 종료 인덱스는 모든 레슨 길이의 합이다.
• 총 9개로 구성된 레슨의 시간은 각각 1, 2, 3, 4, 5, 6, 7, 8, 9이므로 이진 탐색의 시작 인덱스는 최대 레슨 시간인 9, 종료 인덱스는 레슨 시간을 모두 합한 45이다.
• 블루레이 개수가 3일 때, 9~45 사이에서 블루레이 크기의 최솟값을 이진 탐색으로 찾으면 된다.
• 9~45 사이에서 이진 탐색을 다음과 같이 수행한다.
• 이진 탐색은 시작 인덱스 > 종료 인덱스일 때까지 수행한다.

[이진 탐색 수행]

• 중앙값 크기로 모든 레슨을 저장할 수 있으면 종료 인덱스 = 중앙값 - 1 # 왼쪽 데이터셋
• 중앙값 크기로 모든 레슨을 저장할 수 없으면 시작 인덱스 = 중앙값 + 1 # 오른쪽 데이터셋

2단계 슈도 코드

N(레슨 개수 저장) M(블루레이 개수 저장)
A(기타 레슨 데이터 저장 리스트)
start(시작 인덱스)
end(종료 인덱스)

for A 리스트 탐색:
	시작 인덱스 저장(A 리스트 중 최댓값)
    종료 인덱스 저장(A 리스트의 총합)

while 시작 인덱스 <= 종료 인덱스:
	middle(중간 인덱스)
    sum(레슨 합)
    count(현재 사용한 블루레이 개수)
    for N의 개수만큼 반복:
    	if sum + 현재 레슨 시간 > 중간 인덱스:
        	count 값을 올리고 sum을 0으로 리셋하기
            # 현재 블루레이에 저장할 수 없어 새로운 블루레이로 교체한다는 의미
        sum에 현재 레슨 시간값 더하기
    sum이 0이 아니면 마지막 블루레이가 필요하므로 count값 올리기
    
    if count > M: # 중간 인덱스 값으로 모든 레슨 저장 불가능
    	시작 인덱스 = 중앙 인덱스 + 1
    else: # 중간 인덱스 값으로 모든 레슨 저장 가능
    	종료 인덱스 = 중앙 인덱스 - 1

시작 인덱스 출력

3단계 코드 구현

N, M = map(int, input().split())
A = list(map(int, input().split()))
start = 0
end = 0

for i in A:
    if start < i:
        start = i # 레슨 최댓값을 시작 인덱스로 저장
    end += i # 모든 레슨의 총합을 종료 인덱스

while start <= end:
    middle = int((start + end) / 2)
    sum = 0
    count = 0
    for i in range(N): # 중간값으로 모든 레슨을 저장할 수 있는지 확인
        if sum + A[i] > middle:
            count += 1
            sum = 0
        sum += A[i]
    if sum != 0:
        count += 1
    if count > M:
        start = middle + 1
    else:
        end = middle - 1

print(start)

📌 문제 031) 배열에서 K번째 수 찾기

시간 제한 2초, 골드 II, 백준 1300번

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.
배열 A와 B의 인덱스는 1부터 시작한다.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 10^5보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(10^9, N^2)보다 작거나 같은 자연수이다.

3
7

출력

B[k]를 출력한다.

6

1단계 문제 분석

• k의 범위가 1~min(10^9, N^2)이므로 시간 복잡도가 N^2인 알고리즘은 사용할 수 없다. 여기서는 이진 탐색을 사용한다.
• 이진 탐색으로 중앙값보다 작은 수의 개수를 세면서 범위를 절반씩 줄이는 방법을 B[k] 값을 구한다.
• 다시 말해, 작은 수의 개수가 k-1개인 중앙값이 정답이다.
• 작은 수의 개수를 세는 아이디어가 이 문제를 푸는 열쇠이다.
• 2차원 리스트는 N행이 N의 배수로 구성되어 있으므로 2차원 리스트에서의 k번째 수는 k를 넘지 않는다. 즉, 2차원 리스트의 1~k번째 안에 정답이 있다.
• 이진 탐색의 시작 인덱스를 1, 종료 인덱스를 k로 정한다.

2단계 슈도 코드

N(리스트의 크기) K(구하고자 하는 index)
start(시작 인덱스 = 1)
end(종료 인덱스 = K)

# 이진 탐색 수행
while 시작 인덱스 <= 종료 인덱스:
	middle(중간 인덱스)
    cnt(중앙값보다 작은 수)
    # 중앙값보다 작은 수 계산
    for i는 1~N:
    	cnt에 중앙 인덱스를 i로 나눈 값과 N 중 작은 값을 더함
    if cnt < K: # 현재 중앙값보다 작은 수의 개수가 K보다 작음
    	시작 인덱스 = 중앙 인덱스 + 1
    else: # 현재 중앙값보다 작은 수의 개수가 K보다 크거나 같음
    	종료 인덱스 = 중앙 인덱스 - 1
        정답 변수에 중앙값 저장

정답 출력

3단계 코드 구현

N = int(input())
K = int(input())
start = 1
end = K
ans = 0

# 이진 탐색 수행
while start <= end:
    middle = int((start + end) / 2)
    cnt = 0

    # 중앙값보다 작은 수 계산
    for i in range(1, N+1):
        cnt += min(int(middle / i), N) # 작은 수 카운트 핵심 로직
    if cnt < K:
        start = middle + 1
    else:
        ans = middle
        end = middle - 1

print(ans)