(2014.2.15 수정되었습니다. 맨 아래 요약 있습니다.)
이분 탐색은 문제상황이 어떻든지 핵심만 파악되면 즉각적으로 간단히 커스텀 할 수 있습니다.
제가 이분 탐색을 적용하는 방식을 적어볼께요.
누군가에게는 도움이 될지도 모르겠습니다.
수직선을 좌, 우로 나누었을 때,
이 문제는 심사완료 가능한 시간의 최솟값을 구해야 합니다.
—> 좌측 A구역(a포함): 조건을 성립시키지 못하는 수들로 설정
—> a: 절대 심사 완료를 못할 시간 0으로 초기화
—> 우측 B구역(b포함): 조건을 성립시킬 수 있는 수들로 설정
—> b: n명 이상을 심사 완료 시킬 수 있도록 충분히 큰 수로 초기화
Q) 범위 최대값인 b를 모르겠다??
—> 방법 1) b를 엄청나게 크게 잡는다.. (어차피 O(logN)..)
—> 방법 2) (a,b)=(0,1) 설정 후 —> a,b를 2배씩 늘려가는 코드 추가
(첫 번째 방법에 비해서 범위구하는데 O(logN) 만큼 소요되지만,
대신 이따가 while 줄여나갈 때 횟수를 절약 가능하므로 도찐 개찐..
def solution(n, times):
a,b = 0,1
while not is_ok(n, times, b):
a,b = b, 2*b
########################### 여기까지 코드 작성시 탐색범위 a,b까지 설정 완료
def is_ok(n, times, x): ####### 조건 만족 여부(n명 이상 심사 완료 가능)
return n <= sum(x//i for i in times)
(반드시 a값이 1칸이상 올라가든지, b값이 1칸이상 내려와야 합니다)
조건만족 여부가 서로 다른 a, b에 대해서 수직선상 선분 [a, b]는
while 진행시마다 --> 평균값 m을 통해서 길이가 대략 절반씩 줄어듭니다.
a, b가 어떤 값이든, 절반씩 줄어들다 보면 while 끝머리에서 반드시 구간 길이가 1이 됩니다.
--> 이 때, 구간의 평균값 m을 어떻게 정의하느냐에 따라
즉, 소수점 내림 적용의 m=(a+b)//2, 또는 소수점 올림 적용의 m=(a+b+1)//2
선택에 따라 마지막 체크에서 m은 a를 가리키거나 b를 가리킵니다. (예) [0,1]
while 초반 a,b 차이가 클 경우에는 항상 a
마지막에 a+1=b 상황이 되었을 때는 m이 a 또는 b와 같아질 수밖에 없는데...
평균을 m=(a+b)//2 로 정의하면 m은 중앙 또는 좌측을 가리키므로
--> 적어도 m는 마지막까지 항상 보장 되고,
평균을 m=(a+b+1)//2 로 정의하면 m은 중앙 또는 우측을 가리키므로
--> 적어도 a
3) while 결과는 반드시 1개의 값으로 출력 시키기
—> 첫 줄 무조건 while a —> 최종 결과가 a==b가 되므로 a, b 아무거나 return 하면 됨
이제 생각해봐야 할 것이 있습니다.
앞서, a, b는 조건 성립 여부가 서로 달랐습니다.
지금 이 문제를 예로 들면, 매 iter마다 b는 항상 심사완료 가능한 시각일 테고,
a는 매 iter마다 심사완료 불가능한 시각이다가, 마지막 1차이 나는 a,b 일 때만
a가 심사가능한 b로 넘어와서 포개져야만
--> a,b 어느것을 출력하든 a==b 이고 원하던 최솟값이 되게 됩니다.
정리해 보면..
ㄱ) 조건 만족하는 최소값 구할 때(이 문제 여기 해당)
—> 좌측A구역: 조건 불만족 구간 / 우측B구역: 조건 만족 구간
—> 포인터m: 우측B구역 진입후 최대한 좌측으로 내려오다가 멈추면 그 값이 정답 (return)
※ 중간 포인터 m이 소수점시 최대한 좌측을 가리키도록 m=(a+b)//2 으로 설정
※ m이 조건 만족시 b=m으로 b를 내리고,
--> (평균을 m=(a+b)//2 이렇게 잡으면 항상 m를 만족하기에 무조건 b는 작아집니다)
※ m이 조건 불만족시 a=m+1 로 a를 올림.
--> (이 때는 새로 지정된 a가 조건 만족 할 수도 아닐 수도 --> 그래야 마지막에 B구역에 포개진다)
ㄴ) 조건 만족하는 최대값 구할 때
—> 좌측A구역: 조건 만족 구간 / 우측B구역: 조건 불만족 구간
—> 포인터m: 좌측A구역 진입후 최대한 우측으로 올라가다가 멈추면 그 값이 정답 (return)
※ 중간 포인터 m이 우측을 가리키도록 m=(a+b+1)//2 으로 설정
※ m이 조건 만족시 a=m으로 a를 올리고,
--> (평균을 m=(a+b+1)//2 이렇게 잡으면 항상a를 만족하기에 무조건 a는 커집니다)
※ m이 조건 불만족시 b=m-1 로 b를 내림.
--> (이 때는 새로 지정된 b가 조건 만족 할 수도 아닐 수도 --> 그래야 마지막에 A구역에 포개진다)
이제 이분 탐색 핵심 알고리즘인 위의 내용을 적용하면 아래와 같음
while a<b:
m = (a+b)//2
if is_ok(n, times, m):
b = m
else:
a = m+1
코드를 조금 더 간단히 쓰고 싶으면
while a<b:
m = (a+b)//2
a,b = (a,m) if is_ok(n, times, m) else (m+1,b)
따라서 최종 전체 코드는 아래과 같고,
이 방식을 적용해서 다른 문제도 같은 방식으로 만들면 됩니다.
요약
1) 탐색 범위 양 끝 값 a,b는 조건 만족 여부 서로 다르게 충분히 확실한 수로 초기화.
2) 무조건 while a 로 설정 --> 구간 아닌 한 점 으로 축소되어 a==b 되므로
—> return 값 고민 없이 a든 b든 아무거나 쓰면 됨
3) 조건 만족하는 최대값 구할 때
—> A구역: 조건 만족하는 구역 —> m=(a+b+1)//2 로 최대한 우측 지목
—> m 만족시 a=m 으로 a를 반드시 올리고, (m의 정의에 따라 항상 a이므로 a는 반드시 상승)
—> m 불만족시 b=m-1 로 b를 반드시 낮추기
4) 조건 만족하는 최소값 구할 때
—> B구역: 조건 만족하는 구역 —> m=(a+b)//2 로 최대한 좌측 지목
—> m 만족시 b=m 로 b를 반드시 낮추고, (m의 정의에 따라 항상 m이므로 b는 반드시 하강)
—> m 불만족시 a=m+1 으로 a를 반드시 올리기
감사합니다!
감사합니다
감사합니다 ..
위 방식대로 이분탐색 연습을 위한 코드를 짜면 아래처럼 나옵니다
1) n보다 큰 최소의 자연수 찾기
def solution(n):
a,b = 0,1
while not is_ok(n, b):
a,b = b, 2*b
while a<b:
m = (a+b)//2
a,b = (a,m) if is_ok(n, m) else (m+1,b)
return a
def is_ok(n, x):
return True if x>n else False
2) n보다 작은 최대의 자연수 찾기
def solution(n):
a,b = 0,1
while is_ok(n, b):
a,b = b, 2*b
while a<b:
m = (a+b+1)//2
a,b = (m,b) if is_ok(n, m) else (a,m-1)
return a
def is_ok(n, x):
return True if x<n else False
감사합니다 도움됐습니다