이분탐색

  • 이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다.

  1. 이분 탐색을 하고자 할 때 이미 정렬이 되어있어야 합니다.

  2. left, right로 미드값을 잡아줍니다.

  3. mid 값과 구하고자 하는 값을 비교 합니다.

  4. 비교할시 mid 값보다 구하고자 하는 값이 높으면 left를 mid+1로 만들어주고 낮으면 right를 mid-1로 만들어 줍니다.

  5. left > right 가 될때까지 1~3번을 반복해서 구하고자 하는 값을 찾습니다.

이렇게 검색을 하면 전체를 검색하는 경우인 시간복잡도가 O(n) 인거에 비해서 O(log(n)) 으로 적다고 합니다.

입국심사

1차답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def solution(n, times):def solution(n, times):
    people = len(times)
    answer = 0
    min_times = [0] * people

    # 처음 사람 들어감
    n -= people

    while(n>0):
        answer += 1
        for i in range(people):
            # 시간이 times의 배수라면
            if answer % times[i] == 0:
                # 사람 감소
                if n - 1 == 0:
                    min_times = [x + (2*y) for x,y in zip(min_times,times)]
                    n -= 1
                    return min(min_times)

                min_times[i] += times[i]
                n -= 1

시간 초과

2차답안

이분 탐색 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def solution(n, times):
    # 최악의 경우 : 가장 비효율적인 심사관에게 모든 사람이 다 보는것
    left, right = 1, max(times) * n
    answer = 0
    
    while left <= right:
        mid = (left + right) // 2
        people = 0
        
        for i in times:
            
            people += mid // i
            
            if people >= n:
                answer = mid
                right = mid - 1
                break
            
            # 모든 사람을 심사할 수 없는 경우
            # 한심사관에게 주어진 시간을 늘려본다.
        if people < n:
            left = mid + 1
                
    return answer