강의로 돌아가기
faul2chris

[이진 탐색] 커스텀?? 핵심 가이드 (파이썬 코드 포함)

(2014.2.15 수정되었습니다. 맨 아래 요약 있습니다.)
  
이분 탐색은 문제상황이 어떻든지 핵심만 파악되면 즉각적으로 간단히 커스텀 할 수 있습니다.
제가 이분 탐색을 적용하는 방식을 적어볼께요.
누군가에게는 도움이 될지도 모르겠습니다.
 

[이진 탐색] 커스텀 핵심 요약

 
수직선을 좌, 우로 나누었을 때,

1) 좌측구역A, 우측구역B —> 조건 성립 여부가 서로 달라야 함

  이 문제는 심사완료 가능한 시간의 최솟값을 구해야 합니다.
 
  —> 좌측 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)

 
 

2) a, b의 평균 m을 지정하는 방법 --> 매 iter마다 반드시 길이 축소

   (반드시 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를 반드시 올리기
 

작성중인 코드―solution.py
1
2
3
4
5
6
7
8
9
10
11
def solution(n, times):
    a,b = 0,1
    while not is_ok(n, times, b):
        a,b = b, 2*b        
    while a<b:
        m = (a+b)//2
        a,b = (a,m) if is_ok(n, times, m) else (m+1,b)
    return a

def is_ok(n, times, x):
    return n <= sum(x//i for i in times)
  • 부추

    감사합니다!

    부추―2023.10.16 08:54
  • 람람이

    감사합니다

    람람이―2024.02.14 22:24
  • 박현수

    감사합니다 ..

    박현수―2025.05.25 19:52
2 개의 답변
faul2chris

위 방식대로 이분탐색 연습을 위한 코드를 짜면 아래처럼 나옵니다
 
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
tsulocalizing@gmail.com

감사합니다 도움됐습니다

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다.