초급 7회차 이분탐색 & 분할정복

이분탐색과 분할정복 모두 문제를 쪼개어 해결하는 방식임.

쪼갠다는 것은 무엇인가

문제의 크기가 크면 어렵다.
문제를 작은 부분 문제들로 나누어 풀면 쉬워진다.

문제를 쪼개고,
부분 문제들을 풀고,
그 결과를 병합한다.

문제를 쪼개는 것 & 결과를 병합하는 것의 비용이 크지 않다면 쪼개어 푸는 게 이득이다.

이분탐색의 간단한 설명

주어진 값들을 오름차순으로 정렬했다고 하자.
이 정렬된 리스트 내에서 특정 값 N의 위치를 이분탐색법으로 찾아보자.

1. 중앙값을 콕 찝는다.
2. 중앙값이 N보다 큰지 작은지 확인한다.
3. 중앙값이 N보다 작다면 중앙값의 다음부터 리스트 끝까지의 범위에 N이 있다. 반대로 중앙값이 N보다 크다면 리스트의 처음부터 중앙값 이전까지의 범위에 N이 있다.
4. 이러한 점검을 반복해나가면서 N이 있을 수 있는 범위를 좁혀나간다.

이렇게 범위를 반씩 쪼개가며 값을 찾는 방식이 이분탐색이다.

Lower Bound와 Upper Bound

이분탐색법을 이용하면
오름차순으로 정렬된 길이가 N인 리스트 상에서
lower_bound와 upper_bound를
$\log_2 N$ 의 시간복잡도 내에 구할 수 있다.

lower_bound란,
오름차순으로 정렬된 리스트와 특정 값 target에 대하여,
리스트 내에서 target 이상의 값이 처음으로 등장하는 위치의 인덱스를 가리킨다.
만약 target 이상의 값이 리스트에 없다면 가장 마지막 인덱스를 가리킨다.

target = 11일 때, 아래 리스트에서 lower_bound는 4이다. (인덱스가 0부터 8까지일 때)

2

3

3

7

11 lower_ bound

11

11

13

17

upper_bound란,
오름차순으로 정렬된 리스트와 특정 값 target에 대하여,
리스트 내에서 target 초과의 값이 처음으로 등장하는 위치의 인덱스를 가리킨다.
만약 target 이상의 값이 리스트에 없다면 가장 마지막 인덱스를 가리킨다.

target = 11일 때, 아래 리스트에서 upper_bound는 7이다. (인덱스가 0부터 8까지일 때)

2

3

3

7

11

11

11

13 upper_ bound

17

그럼 위 리스트에서 11의 개수는
upper_bound 값에서 lower_bound 값을 빼준 3이다.

lower_bound와 upper_bound를 코드로 구현하는 법은 아래의 백준 10816번 문제풀이에 적어두었다.

C++의 경우 algorithm.h 라는 헤더에 lower_bound와 upper_bound가 미리 구현되어있다는데 java에는 없다.

코딩테스트 주류언어인 C++을 선택하지 않은 사람에게 주어지는 벌인가...? 킹받는다.

그래서 직접 구현해주어야 한다. 구현하기 어렵지는 않다.

#10816 : 숫자 카드 2

좌표압축이란?

간격 또는 중복 정보를 제거하여 많은 점 집합을 더 작은 범위에 mapping하는 기법

언제 사용하는가?

• 실제 간격의 정보가 덜 중요할 때
• 중복값이 많고 상대적인 순서만 알아도 될 때
• 좌표 상에서 range는 크지만 실제 점 개수(좌표 정보의 개수)는 적을 때

예를 들어, 엄청나게 넓은 운동장 안에 4명의 사람이 서 있는데, 그 4명의 x좌표를 기준으로 순서를 매겨야 한다고 하자. 이럴 때는 사람들 사이의 실제 간격의 크기는 중요하지 않다. 좌표 압축을 해서 상대적 순서만 알아내면 된다.

좌표압축을 하려면 이분탐색을 통하여 1차원 배열 상에서 특정 값의 위치를 알아내야 하기 때문에 이번 챕터에 포함되었다.

좌표압축 예제

좌표압축이 쓰이는 문제의 예시로 백준 2370번 시장 선거 포스터 문제가 있다.

2370번: 시장 선거 포스터

각 포스터가 겹치는지 안 겹치는지의 여부가 중요하지, 정확히 몇 바이트만큼 겹치고 몇 바이트만큼 드러나는지는 중요하지 않다. 그리고 좌표의 최댓값이 $10^8$ 즉 1억이나 된다. 좌표압축을 하지 않고 그대로 1억짜리 1차원 배열을 선언하는 것은 공간적 효율 측면에서 매우 부적절하다.
따라서 좌표압축이 필수인 문제이다.

자세한 설명과 구현 방법은 다음의 문제풀이 게시글에 적어두었다.

#2370 : 시장 선거 포스터

참고로 좌표압축 시에
C++을 사용한다면 벡터의 erase와 unique를 사용하고 lower_bound를 사용하는 것이 좋다.
하지만 java에는 TreeSet이 있기 때문에 그냥 이분탐색으로 특정 값의 위치를 찾는 함수를 사용하면 된다.
나는 java를 사용하므로 java 입장에서의 풀이법만 정리했다. 위의 시장 선거 포스터 문제풀이 게시글에 적혀있다.

 

 

 

매개변수 탐색

매개변수 탐색이 뭔지 이야기하기 전에, 정보과학에서의 문제의 분류를 알아야 한다.

 

 

정보과학에서는 문제를 다음의 다섯 가지로 분류한다:

• 결정 문제(Decision Problem)
• 탐색 문제(Search Problem)
• 계산 문제(Counting Problem)
• 최적화 문제(Optimization Problem)
• 함수 문제(Function Problem)
  
  

이 중 결정 문제와 최적화 문제가 이번 챕터와 관련이 있다.

먼저 결정 문제란 True 혹은 False로 답하는 문제이다.

최적화 문제란 가장 ㅇㅇ한 것을 찾아내는 문제이다.

 

이 때 결정 문제는 최적화 문제보다 어려울 수 없다.

최적화 문제를 결정 문제로 바꾸거나 쪼개어서 여러 단계의 결정 문제로 만들면 본래보다 더 쉬워지는 경우가 많다.

 

 

 

매개변수 탐색이란, 최적화 문제를 결정 문제로 바꾸는 데에 사용하는 기법이다!

이분 탐색이 사용된다.

특정 파라미터를 기준으로, 조건을 만족하는 부분과 만족하지 않는 경계점을 찾는 것이다.

 

문제의 답이 될 수도 있는 값의 범위가 주어지고,

그 범위 중 한 지점을 기점으로 그 값보다 한쪽의 값들은 모두 조건을 만족하고 반대쪽 한쪽의 값들은 모두 조건을 만족하지 못하는 상황이라면

그리고 그 한 지점의 값이 바로 정답이라면

그 지점을 찾아내기 위해서

매개변수 탐색을 사용할 수 있다.

 

여기에 알맞는 예제로 백준 16564번 히오스 프로게이머 문제가 있다.

16564번: 히오스 프로게이머

 

이 문제는 위의 조건에 부합하는 문제이다.

 

캐릭터의 본래 레벨의 범위가 1부터 10억까지이고

올릴 수 있는 레벨의 범위고 1부터 10억까지이므로

정답이 될 수 있는 값의 범위는 최악의 경우 1부터 20억까지이다.

 

이 범위 내의 한 지점에 정답 값이 존재한다.

정답보다 작은 값들은 모두 성권이가 주어진 K 레벨 이내를 올려 달성할 수 있는 팀 레벨이다.

반대로, 정답보다 큰 값들은 모두 성권이가 K 레벨 가지고는 달성할 수 없는 팀 레벨이다.

 

범위의 중간값을 찝은 뒤에

그 중간값만큼의 팀 레벨을 성권이가 달성할 수 있는지 없는지를 따진다.

달성할 수 있다면 그 값 이상의 값들을 가지고 이분탐색을 계속한다.

달성할 수 없다면 그 값 미만의 값들을 가지고 이분탐색을 계속한다.

 

1부터 20억의 범위를 이분탐색하면

$log_2$20억

최악의 경우라도 대충 서른 번 정도의 탐색으로 정답을 찾아낼 수 있다.

 

 

 

 

 

 

 

분할정복의 간단한 설명

분할정복은 대개 다음의 세 단계로 이루어진다.

1. Divide: 문제를 둘 이상의 서로 비슷한 크기의 부분 문제로 나눈 뒤
2. Conquer: 각 부분을 해결하고
3. Merge: 해결한 결과들을 병합하여 전체 문제의 답을 구하기

 

분할정복과 동적 계획법의 차이

동적계획법도 문제를 부분 문제로 잘게 쪼개는 것인데 분할정복과 무엇이 다른가?

동적계획법에는 여러 번 반복해서 계산해야 하는, 즉 중복되는 부분문제가 있다. 분할정복에서는 부분 문제가 중복되지 않는다.

 

 

분할정복 예제

분할정복의 기본적인 예제로 백준 17829번 222-풀링이 있다.

17829번: 222-풀링

#17829 : 222-풀링