[코테] 코딩테스트 준비 (7)

julian·2025년 8월 6일
algorithmcoding testpython

python

목록 보기
74/74

📌 공부할 때 참고한 영상은 나동빈님의 이코테 2021 강의 입니다.

1. 정렬 알고리즘

정렬,Sorting정렬, Sorting

  • 데이터를 특정한 기준에 따라 순서대로 나열하는 것

  • 데이터가 적을 때, 데이터가 많은데 범위가 특정하게 한정되어 있을 때 등 다양한 상황이 많은데 상황에 맞게 적절한 정렬 알고리즘이 공식처럼 사용된다.

1.1. 선택 정렬

  • 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 자리를 바꾸는 것 반복한다.

  • 동작 예시

    1. 첫 상태는 모두 처리되지 않은 데이터
      이 상황에서 가장 작은 0을 가장 앞의 7과 자리를 바꾼다.
    2. 이제 0은 처리 되었으니 제외하고 남은 데이터들을 다시 확인해 가장 작은 1을 5와 바꾼다.
    3. 이 과정을 반복하면 전체 원소가 정렬된다.

      반복을 진행하다보면 탐색 범위는 갈수록 줄어들게 되고 매번 가장 작은 데이터를 찾기위해서 탐색 범위만큼 데이터를 하나씩 확인해서 가장 작은 데이터를 찾아야하기 때문에 매번 선형 탐색을 수행하는 것과 동일하다.
      그렇기 때문에 이중 반복문을 활용해서 이러한 선택 정렬을 구현할 수 있다.

  • 코드로 확인

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

# 0부터 데이터의 전체 수 -1까지 반복
# i: 가장 작은 데이터와 바뀔 가장 앞쪽 인덱스 위치
for i in range(len(array)):
    # 가장 작은 원소의 인덱스
    min_index = i
    # 선형 탐색 -> 가장 작은 값 찾기
    for j in range(i+1, len(array)):
        # 가장 작은 원소보다 더 작은 원소가 있다면 그 값이 min_index가 되도록함
        if array[min_index] > array[j]:
            min_index = j
    # 자리 변경
    array[i], array[min_index] = array[min_index], array[i]

print(array)
  • 이러한 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 하기 때문에 구현 방식에 따라 작은 오차는 있을 수 있지만 전체 연산 횟수는 아래와 같다.
    • N+(N−1)+(N−2)+...+2N+(N-1)+(N-2)+...+2
      가장 마지막 원소는 정렬을 수행해주지 않아도 되기때문에 +2 까지 등차수열 형태다.
    • 등차수열: (N2+N−2)/2(N^2+N-2)/2
    • 시간 복잡도: O(N2)O(N^2)
      연산횟수에 대한 공식이 빅오 표기법에 따라 시간 복잡도를 나타내면 계수에 해당하는 /2/2는 생략되고 가장 차수가 높은 항만 고려하기 때문에 O(N2)O(N^2)

1.2. 삽입 정렬

  • 처리되지 않은 데이터를 하나씩 확인하면서 골라 매번 계산해서 적절한 위치에 삽입

  • 선택 정렬보다 복잡하지만 더 빠르고 효율적

  • 동작 예시

    1. 앞쪽에 있는 원소들이 이미 정렬되어 있다고 가정하고 뒤쪽에 있는 원소를 앞쪽에 있는 원소들 중 한 곳을 골라서 들어가도록 한다.
    2. 이제 7은 정렬이 되어있다고 판단하고, 두 번째 데이터인 5가 어떤 위치로 들어갈지 판단한다.
      7에 비해서 더 작은지 큰지를 비교하고 앞과 뒤에 맞도록 삽입한다.
    3. 이어서 9는 자신의 앞 7과 비교하여 더 크기 때문에 자리를 유지하며
    4. 이어서 0은 앞 9, 7, 5 순서대로 다 비교하여 가장 앞으로 이동한다.

  • 코드로 확인

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

# 가장 앞은 정렬되어 있다고 생각하기 때문에 1부터 데이터의 전체 수 -1까지 반복
# 왼쪽으로 이동하면서 위치를 바꿔가는 거
for i in range(1, len(array)):
    # i부터 1까지 -1씩 감소하며 반복
    # j: 삽입하고자하는 원소의 현재 위치
    for j in range(i, 0, -1):
        # 자리 변경
        if array[j] < array[j-1]:
            array[j], array[j-1]=array[j-1], array[j]
        else:
            break

print(array)
  • 선택 정렬과 마찬가지로 이중 중첩 반목문에서 비교연산과 삽입연산이 수행되기 때문에 시간 복잡도는 O(N2)O(N^2)이다.
  • 특히 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태에서는 더 빠르게 동작한다.
    이미 모든 데이터가 다 정렬되어 있다고 한다면 자신의 앞과 비교하기만 하면 되기 때문에 O(N)O(N) 의 시간 복잡도만 가지게 된다.

1.3. 퀵 정렬

  • 데이터의 특성과 관련없이 표준적으로 사용할 수 있는 정렬 알고리즘 중 하나다.

  • 기준 데이터를 고른 뒤에 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.

  • 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘

  • 병합 정렬과 더불어 대부분의 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다.

  • 정렬을 수행하는 과정에서 기준 데이터, pivot이라는 것을 설정하게 되는데, 가장 기본적인 퀵 정렬에서는 첫 번째 데이터를 pivot으로 설정하게 된다.

  • 동작 예시

    1. 가장 첫번째 5를 pivot으로 설정하고

    2. 왼쪽에서부터는 pivot보다 큰 데이터를 선택하여 7
      오른쪽에서부터는 pivot보다 작은 데이터를 선택하여 4
      그래서 이 7과 4 두 값의 위치를 바꿔준다.

    3. 다음으로 다시 왼쪽부터는 pivot보다 큰 9, 오른쪽부터는 pivot보다 작은 2를 선택하고 바꾼다.

    4. 똑같이 진행하는데 만약 이와 같이 위치가 넘어가서 엇갈리게 되는 경우에는
      pivot과 자신보다 작은 데이터(1)의 위치를 서로 바꿔주게 된다.

    5. 그렇게 되면 기존의 pivot인 5를 기준으로 왼쪽은 모두 5보다 작고, 오른쪽은 5보다 크게 된다.
      이렇게 pivot을 기준으로 데이터 묶음을 나누는 작업을 분할(divide)이라고 한다.

    6. 그렇다면 이제 왼쪽의 5보다 작은 묶음과, 오른쪽의 5보다 큰 묶음 각각을 하나의 배열로 판단을 해서 각 배열에서 다시 퀵 정렬을 반복해서 정렬될때 까지 재귀적으로 수행하게 된다.
      왼쪽은 가장 앞인 1이 pivot이 되고

      오른쪽은 가장 앞인 6이 pivot이 된다.

  • 그렇다면 이 퀵은 왜 빠르다고 할까?
    이상적인 경우, 분할이 절반씩 일어난다면 전체 연산 횟수는 O(NlogN)O(NlogN)이 된다.

    아래 그림을 보자.
    실제로는 pivot을 기준으로 해서 왼쪽 오른쪽으로 분할이 이루어진다고 봐야하겠지만 일단은 절반씩 나뉜다고 가정하고 보자.
    그렇다면 이렇게 분할이 이루어질 때마다 데이터의 범위가 절반씩 줄어들게 되기 때문에 전체 높이를 확인했을 때 logNlogN 이라고 볼 수 있다.

    그 중에서도 데이터의 범위가 절반씩 줄어들기 때문에 log2Nlog_2N 이라고 표현할 수 있겠다.
    그래서 이러한 연산 과정을 직관적으로 이해하고자 한다면,
    전체 연산 횟수, 너비(데이터의 수, NN) X 높이(logNlogN) = NlogNNlogN 이라고 할 수 있다.

  • 그래서 이 퀵 정렬의 시간 복잡도는 O(NlogN)O(NlogN) 이라고 할 수 있는데, 하지만 최악의 경우 O(N2)O(N^2)이 될 수도 있다.
    만약 첫 번째 원소를 pivot으로 삼았는데, 이미 정렬된 배열에 대해 퀵 정렬을 수행하게 되면 어떻게 될까?

    앞서 퀵정렬을 수행했던 것을 생각해보면 0, 1, 2, ... 이런식으로 하나씩 계속 왼쪽은 분리되어 나가고 오른쪽 배열들이 똑같은 과정을 반복하게 될 것이다.
    그렇다면 분할이 일어나는 횟수가 NN과 비례하게 되고 분할을 하기 위해서 매번 선형탐색을 해야하기 때문에 전체 시간 복잡도가 O(N2)O(N^2)가 되는 것이다.
    이러한 이유 때문에 다양한 언어에서 제공하는 표준 정렬 라이브러리에서는 항상 O(NlogN)O(NlogN)을 보장할 수 있는 형태로 구현해놓았다.

  • 코드로 확인

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    # 원소가 1개인 경우 종료
    if start >= end:
        return
    # 첫번째 원소를 pivot으로 설정 
    pivot = start
    # pivot을 제외한 데이터 중 가장 왼쪽을 left
    left = start + 1
    # 가장 오른쪽을 right로 설정
    right = end
    
    # 엇갈릴때까지 반복
    # left가 가리키는 인덱스의 값 보다 right가 가리키는 인덱스의 값이 작다면 엇갈린 것
    while(left <= right):
        # 왼쪽 -> 오른쪽 (while pivot 보다 큰 데이터를 찾을 때 까지)
        while(left <= end and array[left] <= array[pivot]):
            left += 1
        # 오른쪽 -> 왼쪽 (while pivot 보다 작은 데이터를 찾을 때 까지)
        while(right > start and array[right] >= array[pivot]):
            right -= 1
        
        # 만약 위치가 엇갈렸다면 "작은 데이터"와 "pivot" 바꿔줌
        if(left > right):
            array[right], array[pivot] = array[pivot], array[right]
        # 엇갈리지 않았다면 "작은 데이터"와 "큰 데이터" 바꿔줌
        else:
            array[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 재귀적으로 quick_sort 호출
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)

quick_sort(array, 0, len(array)-1)

print(array)
  • 코드로 확인 (간결 ver)
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    # 원소가 1개인 경우 종료
    if len(array) <= 1:
        return array
    # 리스트 슬라이싱 이용
    # 첫번째 원소를 pivot으로, 나머지를 tail로
    pivot = array[0]
    tail = array[1:]
    
    # 컴프리핸션 이용하여 간결하게 바꾸기
    # left: tail 안의 원소중 pivot보다 작으면 left에 담도록 하고
    left=[x for x in tail if x <= pivot]
    # right: tail 안의 원소중 pivot보다 작으면 right에 담도록 하고
    right=[x for x in tail if x > pivot]
    
    """
    분할 이후
    왼쪽 부분에 대해서 퀵정렬을 수행한 결과 리스트에
    현재 pivot 값을 포함하고 있는 리스트를 이어서 붙여주고
    다시 오른쪽 부분에 대해서 퀵정렬을 수행한 결과 리스트를 붙여주게 되면
    전체 리스트는 모든 원소에 대해서 정렬을 수행한 결과와 같게 된다. 
    """
    return quick_sort(left) + [pivot] + quick_sort(right)

print(quick_sort(array))

1.4. 계수 정렬

  • 특정한 조건이 부합할 때 사용할 수 있는 매우 빠르게 동작하는 정렬 알고리즘

  • 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다.

  • 데이터의 개수 NN, 데이터(양수) 중 최댓값이 KK일 때, 최악의 경우에도 수행 시간 O(N+K)O(N+K)를 보장한다.

  • 동작 예시

    1. 정렬한 데이터: 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
    2. 먼저 주어진 정렬한 데이터에서 가장 작은 데이터부터 가장 큰 데이터가 담길 수 있는 범위의 리스트를 초기화하여 생성한다.
      그렇다면 주어진 데이터는 0~9까지의 범위이기 때문에 인덱스는 아래와 같이 0~9까지 구성되며, 이때 각 인덱스가 각 값에 해당한다.
      그래서 각각의 데이터가 몇번 등장했는지를 count한다.
      기본적으로 배열에서 특정한 인덱스에 접근할 때 알고리즘 상으로 상수시간에 접근이 가능하다고 보기 때문에 그래서 결과적으로 데이터를 하나씩 확인하면서 그 데이터와 동일한 인덱스에 그 count 값을 +1씩 증가시키면서 해당 데이터가 몇번 등장했는지 체크할 수 있게 된다.

    3. 각 원소의 count를 다 구한 후 실제 정렬 수행 결과를 확인할 수 있다.
      결과를 확인할 때는 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스 값을 출력하도록 만들면 된다.

  • 이처럼 데이터의 크기 범위만큼 배열을 만들어줘야 하기 때문에 공간 복잡도가 높지만 조건만 만족한다면 퀵정렬보다 더 빠르게 동작하게 된다.

  • 코드로 확인

array=[7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

# 모든 범위를 포함하는 리스트를 만들기 위해 max(array) -> 9 + 1(0포함)
# 모든 값을 0으로 초기화
count=[0]*(max(array)+1)

for i in range(len(array)):
    # 각 데이터에 해당하는 인덱스의 값 증가
    count[array[i]] += 1

# 정렬 정보 확인
# 각 인덱스를 확인하면서 해당 인덱스를 값으로 가지는 데이터가 몇번 등장하는지를 출력하도록
for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=" ")  # 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9
  • 계수 정렬의 시간 복잡도는
    먼저 데이터의 개수만큼 데이터를 확인하면서 count를 체크하기 때문에 O(N)O(N)이며, 또한 데이터 중에서 가장 큰 값을 의미하는 K는 각 인덱스를 확인하며 그 인덱스에 기록되어 있는 값만큼 출력을 수행한다. 다만 앞선 코드에서 아래와 같은 반복문은 전체 횟수를 N이라고 할 수 있다. 
for j in range(count[i]):
        print(i, end=" ")

그렇기 때문에 이중 중첩 반복문의 시간 복잡도는 O(N+K)O(N+K)다.
따라서 전체 코드의 시간 복잡도는 O(N+K)O(N+K) 라고 할 수 있다.

  • 공간 복잡도 또한 정렬을 수행할 데이터의 개수 N과 데이터 중에서 가장 큰 값만큼의 크기를 가진 K 만큼의 공간이 필요하기 때문에 공간 복잡도 또한 O(N+K)O(N+K)다.
  • 그렇기 때문에 이런 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다.
    예를 들어 데이터가 단순히 0과 999로 두개만 존재한다고 해보자. 데이터는 2개만 존재하지만 총 1000개 만큼의 데이터가 담길 수 있는 배열을 만들어야 한다. 따라서 데이터의 범위가 크다면 이러한 계수 정렬을 사용하기 어렵다.
  • 반대로 성적과 같이 0~100점의 범위가 좁고 동일한 값을 가지는 데이터가 여러 개 등장할 때는 효과적으로 사용할 수 있다.

1.5. 정렬 알고리즘 비교

  • 선택 정렬은 매우 간단하며 구현 또한 쉽다.

  • 삽입 정렬의 경우 일반적으로 선택 정렬에 비해서 조금 더 빠르게 동작한다.

  • 퀵 정렬은 구현 방식에 따라서 최악의 경우 시간 복잡도가 O(N2)O(N^2)이 나올 수도 있다.

  • 계수 정렬은 조건만 만족한다면 매우 빠르게 동작한다.

  • 대부분의 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설게되어 있기 때문에 별도로 문제에서 정렬 함수를 구현하라고 만들지 않는다면 일반적으로 정렬 기능을 위해서 호출해서 수행하는 것이 낫다.

  • 이 선택 정렬과 기본 정렬 라이브러리의 수행 시간을 비교하는 코드를 살펴보면 다음과 같다. 

from random import randint
import time

# 10,000개 정수 삽입
array=[]
for _ in range(10000):
    # 1부터 100 사이 랜덤한 정수
    array.append(randint(1, 100))

# 선택 정렬 성능 측정 시작
start_time = time.time()

# 선택 정렬
for i in range(len(array)):
    min_index=i
    for j in range(i+1, len(array)):
        if array[min_index] > array[j]:
            min_index=j
    array[i], array[min_index] = array[min_index], array[i]
    
# 선택 정렬 성능 측정 종료
end_time=time.time()
print(f"선택 정렬: {end_time - start_time}")

# ===============================================

# 배열 다시 무작위 초기화
array = []
for _ in range(10000):
    array.append(randint(1, 100))

start_time = time.time()

# 기본 정렬 라이브러리
array.sort()

end_time=time.time()
print(f"기본 정렬 라이브러리: {(end_time - start_time):.10f}")

파이썬의 경우 병합 정렬을 기반으로 하는 하이브리드 방식의 알고리즘을 사용하기 때문에 최악의 경우에도 O(NlogN)O(NlogN) 의 시간복잡도를 보장한다.

1.6 기초 문제 풀이

1.6.1. 문제 1 - 두 배열의 원소 교체 문제

  • 두 개의 배열 A와 B가 있다.
  • 두 배열은 N개의 원소로 구성되어 있으며 모든 원소는 자연수다.
  • 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 일명 "바꿔치기 연산" 이라는 것을 최대 K번 수행할 수 있다.
  • 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이다.
  • N, K 그리고 배열 A와 B의 정보가 주어졌을 때,
    최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하라.
  • 예를 들면 다음과 같다.
    • N=5, K=3
      A=[1, 2, 5, 4, 3], B=[5, 5, 6, 6, 5]
    • 세 번의 연산을 수행할 수 있다.
      1. 배열 A의 원소 1과 배열 B의 원소 6 바꾸기
      2. 배열 A의 원소 2와 배열 B의 원소 6 바꾸기
      3. 배열 A의 원소 3과 배열 B의 원소 5 바꾸기
    • A=[6, 6, 5, 4, 5], B=[3, 5, 1, 2, 5]
    • 이때 배열 A의 모든 원소의 합은 26이며, 이보다 더 합을 크게 만들 수는 없다.
  • 입력 조건
    • 첫 번째 줄에 N, K가 공백을 기준으로 구분되어 입력됨 (1<=N<=100,000, 0<=K<=N)
    • 두 번째 줄에 A의 원소들이 공백을 기준으로 구분되어 입력되며 모든 원소는 10,000,000보다 작은 자연수
    • 세 번째 줄에 B의 원소들이 공백을 기준으로 구분되어 입력되며 모든 원소는 10,000,000보다 작은 자연수
  • 출력 조건
    최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 A의 모든 원소의 합의 최댓값
  • 시간 제한 2초
  • 입력 예시
7 4
4 3 3 2 5 1 7
3 3 5 2 1 6 7
  • 출력 예시
35

1.6.2. 해결 아이디어

  • 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체하면 된다.
  • 이를 위해 가장 먼저 해야할 것은 A 오름차순 정렬, B 내림차순 정렬이다.
  • 이후 두 배열의 원소를 첫 번쨰 인덱스부터 차례대로 확인하면서 A의 원소가 B의 원소보다 작을 때에만 교체를 수행한다.
  • 이 문제에서 두 배열의 원소가 최대 100,000개까지 입력될 수 있으므로, O(N2)O(N^2)이 소요되는 선택 또는 삽입 정렬은 시간 초과 판정을 받을 수 있다. 따라서 최악의 경우에도 O(NlogN)O(NlogN)을 보장하는 정렬 알고리즘을 이용해야 한다.
  • 먼저 표준 라이브러리를 사용할 수 있겠다.

1.6.3. ⭐ 코드로 확인

N, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# 배열 A 오름차순
A.sort()
# 배열 B 내림차순
B.sort(reverse=True)
print(f"\n교체전\nA: {A}\nB: {B}")

# 첫 번째 인덱스부터 확인하며 최대 K번 비교
for i in range(K):
    # 그래서 매번 A의 원소가 B보다 작은 경우에는 두 원소를 교체해서
    # 배열 A의 합이 더 커지게 만들고
    if A[i] < B[i]:
        A[i], B[i] = B[i], A[i]
    # A의 원소가 B보다 크거나 같으면 반복문 탈출함
    else:
        break

print(f"\n교체후\nA: {A}\nB: {B}")

# A의 모든 원소 합 출력
print(sum(A))

2. 이진 탐색 알고리즘

  • 순차 탐색: 가장 기본적인 데이터 탐색 알고리즘으로 리스트 안에 존재하는 특정한 데이터를 찾기위해 앞에서부터 단순히 데이터를 하나씩 확인하는 방법

    • 1.1. 선택 정렬 에서 다루었던 선택 정렬에서 매 단계마다 가장 작은 크기의 데이터를 찾는 과정도 이러한 순차 탐색을 이용했다고 볼 수 있다.
    • 리스트에서 특정 데이터가 존재하는지를 검사할때 별다른 말이 없다면 기본적으로는 순차 탐색을 이용한다고 보면 된다.

  • 이진 탐색: 정렬되어 있는 리스트에서 특정한 데이터를 빠르게 탐색할 수 있도록 해주는 탐색 알고리즘

    • 리스트가 정렬되어 있다는 조건을 만족한다면 탐색 범위를 빠르게 절반씩 좁혀 나가면서 데이터를 탐색해 나갈 수 있다는 점에서 log 시간의 시간 복잡도를 가질 수 있다.
    • 실제로 이진 탐색을 수행할 때는 탐색 범위를 지정해줘야하는데, 이때 탐색 범위를 명시하기 위해서 시작점과 끝점, 그리고 그 중간을 중간점이라고 하여 이 세가지 변수를 이용해 탐색 범위를 절반씩 좁혀 나가며 이진 탐색을 수행할 수 있다.

  • 동작 예시

    1. 이미 정렬된 10개의 데이터 중, 값이 4인 원소를 찾으려고 한다면,
    2. 시작점은 인덱스 0번, 끝점은 인덱스 9번, 중간점은 8과 10 사이인데 이렇게 둘일 경우는 소수점 이하를 제거해서 이전을 중간점으로 삼는다.
    3. 그렇다면 이제 중간점인 인덱스 4번인 8과 찾고자하는 값인 4를 비교하여 어떤 값이 더 큰지를 비교한 뒤
      찾고자 하는 값보다 현재 중간점 위치의 값이 더 크다면 중간점에서부터 오른쪽에 있는 값들은 전부 다 확인할 필요가 없어진다.
      따라서 중간점을 포함하여 오른쪽을 전부 버리고 끝점을 중간점 왼쪽으로 옮겨준다.
      그렇게 되면 다시 좁혀진 범위에서 다시 중간점을 구하고 다시 2와 4를 비교한다.
      이번에는 4보다 작기 때문에 또다시 중간점을 포함해서 왼쪽을 다 날려주고 시작점을 중간점 오른쪽으로 옮겨준다.
    4. 이제 다시 또 비교하기 위해 중간점 위치의 값을 확인해봤더니 4, 찾고자 하는 값도 4기 때문에 여기서 탐색을 멈춘다.

      이렇게 보면 총 3번의 스텝만에 빠르게 원하는 값의 위치(인덱스 2번)를 찾을 수 있었다.

  • 이는 단계마다 탐색 범위를 2로 나누는 것과 동일하기 때문에 연산 횟수는 log2Nlog_2N에 비례한다.

  • 예를들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개, 2단계는 8개, 3단계는 4개 정도만 남게 된다. 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)O(logN)을 보장한다.

  • 코드로 확인 (재귀함수 ver)

# 재귀함수
def binary_search(array, target, start, end):
    # 탐색하고자 하는 범위에 데이터가 존재하지 않는 것과 동일하니까 None반환시키고
    if start > end: return None
    
    # 2를 나눈 몫(소수점떨구기)
    mid = (start + end) // 2
    
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
        return mid
    # 중간점 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target:
        return binary_search(array, target, start, mid-1)
    # 중간점 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else:
        return binary_search(array, target, mid+1, end)

# N: 원소개수 / target: 찾고자하는 값
N, target = list(map(int, input().split()))
# 전체 원소
array = list(map(int,input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, start=0, end=N-1)
if result == None:
    print("원소가 존재하지 않습니다!")
else:
    print(f"찾고자 하는 값 \"{array[result]}\"은(는) \"{result+1}\"번째 위치에 존재합니다!")

  • 코드로 확인 (반복문 ver)
# 반복문
def binary_search(array, target, start, end):
    # 탐색하고자 하는 범위에 데이터가 존재할동안 while
    while start <= end:
        # 2를 나눈 몫(소수점떨구기)
        mid = (start + end) // 2
    
        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
            return mid
        # 중간점 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target:
            end = mid -1
        # 중간점 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else:
            start = mid + 1
    # 범위에 없으면 None 반환
    return None

# N: 원소개수 / target: 찾고자하는 값
N, target = list(map(int, input().split()))
# 전체 원소
array = list(map(int,input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, start=0, end=N-1)
if result == None:
    print("원소가 존재하지 않습니다!")
else:
    print(f"찾고자 하는 값 \"{array[result]}\"은(는) \"{result+1}\"번째 위치에 존재합니다!")

2.1. 이진 탐색 라이브러리

  • 코딩테스트에서 문제 풀이를 위해 알아두면 좋은 라이브러리가 있는데

    • bisect_left(a, x)
      • cpp에서의 lower_bound와 동일
      • 정렬된 순서를 유지하며 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환
    • bisect_right(a, x)
      • cpp에서의 upper_bound와 동일
      • 정렬된 순서를 유지하며 배열 a에 x를 삽입할 가장 오른쪽 인덱스 반환
    • 배열 a=[1, 2, 4, 4, 8] 이고 삽입하고자 하는 x=4 일때를 보면 다음과 같다.
    from bisect import bisect_left, bisect_right
a = [1, 2, 4, 4, 8]
x = 4
print(bisect_left(a, x))  # 2
print(bisect_right(a, x))  # 4

  • 따라서 이를 이용하면 값이 특정 범위에 속하는 데이터의 개수를 구할 수도 있다. 

from bisect import bisect_left, bisect_right
# a = [1, 2, 4, 4, 8]
# x = 4
# print(bisect_left(a, x))  # 2
# print(bisect_right(a, x))  # 4

def count_by_range(a, left_value, right_value):
    left_index = bisect_left(a, left_value)
    right_index = bisect_right(a, right_value)
    return right_index-left_index

a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]

# 값이 4인 데이터 개수 출력
print(count_by_range(a, 4, 4))  # 6 8 -> 2개

# 값이 [4, 8] 범위에 있는 데이터 개수 출력
print(count_by_range(a, 4, 8))  # 6 9 -> 3개

# 값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(count_by_range(a, -1, 3))  # 0 6 -> 6개
  • 이진 탐색 문제가 출제되는 경우 파라메트릭 서치 유형으로 문제가 출제되는 경우가 많음
  • 파라메트릭 서치는 최적화 문제를 결정 문제(Y/N)로 바꾸어서 해결하는 기법을 말하는데,
    최적화 문제란 어떤 함수의 값을 가능한 낮추거나 혹은 최대한 높이거나 하는 등의 문제를 의미한다.
  • 그러한 최적화 문제를 바로 해결하기 어려운 경우 그 문제를 여러번의 결정 문제(Y/N)를 이용해서 문제 형태를 바꾸어서 해결할 수 있는 그런 경우가 존재한다. 그런 기법이 파라메트릭 서치다.
  • 예를들어 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제가 나왔다고 하면, 탐색 범위를 좁혀가면서 현재 범위에서는 이 조건을 만족하는지 체크를 해서 여부에 따라서 탐색범위를 좁혀나가며 가장 알맞은 값을 찾을 수 있다.
  • 그래서 실제로 파라메트릭 서치 유형의 문제가 출제되는 경우 이진 탐색을 이용해서 효과적으로 해결할 수 있는 경우가 많다.

2.3. 문제 풀이

2.3.1. 문제 1 - 떡볶이 떡 만들기

  • 떡집에서 만드는 떡볶이 떡의 길이가 일정하지 않다.
  • 대신 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.
  • 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다.
    높이가 H보다 긴 떡은 H위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.
  • 예를 들어 높이가 19, 14, 10, 17cm 인 떡이 있고 높이를 15로 지정하면 자른 떡의 높이는 15, 14, 10, 15cm 가 될 것이다.
    잘린 떡의 길이는 차례대로 4, 0, 0, 2cm로 손님은 잘려 나온 6cm 만큼의 길이를 가져간다.
  • 손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하라.
  • 입력 조건
    • 첫째 줄에 떡의 개수 N과 요청한 떡의 길이(잘려 나온 떡의 길이) M이 주어진다. (1<=N<=1,000,000, 1<=M<=2,000,000,000)
    • 둘째 줄에 떡의 개별 높이가 주어진다.
    • 떡 높이의 총 합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다.
    • 높이는 10억보다 작거나 같은 양의 정수 또는 0이다.
  • 출력 조건
    적어도 M만큼의 떡을 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.
  • 시간 제한 2초
  • 입력 예시
4 6
19 15 10 17
  • 출력 예시
15

2.3.1.1. 해결 아이디어

  • 적절한 높이를 찾을 때까지 이진 탐색하여 높이 H를 반복 조정한다.

  • 절단기의 높이와 잘린 떡의 길이는 반비례하기 때문에 이진 탐색을 수행할 수 있다.

  • 현재 이 높이로 자르게 되면 조건을 만족하는지를 확인한 뒤에 조건의 만족 여부(Y/N)에 따라 탐색 범위를 좁혀서 해결할 수 있다.

  • 즉 최소한 M만큼의 떡을 얻을 수 있는가를 확인하고 조건 만족 여부를 확인하면서 탐색 범위를 좁혀 나가는 것이다. 만약 M만큼의 떡을 얻지 못한다면 절단기 높이를 더 낮출 것이다.

  • 절단기의 높이가 0부터 10억까지의 정수라고 했으니 단순히 선형 탐색과 같은 알고리즘을 이용하면 시간 초과 판정을 받을 수 있기 때문에 이렇게 큰 탐색 범위를 보면 가장 먼저 이진 탐색을 떠올려야 한다.

  • 동작 예시

    1. 필요한 떡의 길이 M=6 이라고 하자.
    2. 가장 긴 떡의 길이가 19이기 때문에 시작점: 0, 끝점: 19, 중간점: 9가 된다.

      여기서 중간점이 우리가 자르고자 하는 그 높이가 된다.
      그래서 9로 설정해서 떡을 자르게 되면 각 떡은 10, 6, 1, 8 만큼 잘려나오게 되고 이를 모두 더하면 25가 된다.
      따라서 손님이 요구하는 최소한의 떡의 길이는 만족할 수 있다. 따라서 일단 결과는 저장하고, 그렇다면 절단기의 높이를 더 높였을 때는 조건을 충족하는지 확인해야 한다.
    3. 시작점을 중간점의 오른쪽으로 옮기고, 다시 중간점을 구한다.
      시작점:10, 끝점: 19, 중간점: 14

      이번에는 5+1+0+3 = 9로 조건을 만족한다.
    4. 또 다시 결과를 저장하고 반복한다.
      시작점:15, 끝점: 19, 중간점:17

      2+0+0+0 = 2로 이번에는 6보다 낮기 때문에 이는 조건에 만족하지 않기에 결과를 저장하지 않는다.
    5. 그래서 이번에는 끝점을 중간점의 왼쪽으로 이동시키고 다시 진행한다.
      시작점:15, 끝점: 16, 중간점:15

      이번에는 4+0+0+2 = 6으로 조건에 만족한다. 따라서 이번 높이값 결과를 저장한다.

    이와 같이 이진 탐색을 수행하여 더 이상 탐색 범위를 줄어 들지 못할 때까지 시작점과 끝점의 위치를 바꾸어가며 높이 값을 바꾸어 가며 잘랐을 때 조건을 만족하는지를 체크하는 방식으로 문제에서 요구하는 최적의 해를 구할 수 있는 것이다.
    동작했던 과정을 본다면 중간점의 값이 시간이 지날수록 최적화된 값이 되기 때문에, 과정을 반복하며 중간점의 값을 기록하면 된다.

2.3.1.2. ⭐ 코드로 확인

# N: 떡의 개수 / M: 요청한 떡의 길이(M)
N, M = list(map(int, input().split(" ")))  # 4 6
# 각 떡의 개별 높이 정보
array = list(map(int, input().split()))  # 19 15 10 17

# 초기 시작점과 끝점
start = 0
end = max(array)

result = 0

# 시작점이 끝점보다 작거나 같을 때까지 반복
while(start <= end):
    total = 0
    
    # 중간점(절단기 높이)
    mid = (start+end) // 2
    
    for x in array:
        # 잘랐을 때의 떡의 길이
        if x > mid:
            total += x - mid
    
    # 자른 떡의 길이가 M보다 부족하면 -> 왼쪽 부분 탐색
    if total < M:
        print(f"자른 떡의 길이의 총합은 {total}(으)로, 요청한 떡의 길이인 {M}보다 작습니다.\n재조정...\n")
        end = mid-1
    # 자른 떡의 길이가 M과 비교해서 충분하면 -> 오른쪽 부분 탐색
    else:
        # 최대한 덜 잘른 최적의 때가 정답이므로, 여기서 result에 기록
        print(f"자른 떡의 길이의 총합은 {total}(으)로, 요청한 떡의 길이인 {M}을(를) 만족합니다.\n최적 높이 갱신: {mid}\n")
        result = mid
        start = mid+1

print(f"최적의 절단기 높이: {result}")

2.3.2. 문제 2 - 정렬된 배열에서 특정 수의 개수 구하기

  • N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있다.
  • 이 수열에서 x가 등장하는 횟수를 계산하라.
  • 예를 들면 수열 {1, 1, 2, 2, 2, 2, 3}이 있을 때 x=2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력한다.
  • 단 이 문제는 시간 복잡도 O(logN)O(logN)으로 설계하지 않으면 시간 초과 판정을 받는다.
  • 입력 조건
    • 첫째 줄에 N과 x가 정수가 공백으로 구분되어 입력된다. (1<=N<=1,000,000), (−109-10^9<=x<=10910^9)
    • 둘째 줄에 N개의 원소가 정수로 공백으로 구분되어 입력된다. (−109-10^9<=각 원소의 값<=10910^9)
  • 출력 조건
    • 수열의 원소 중에서 값이 x인 원소의 개수를 출력한다.
    • 단, 값이 x인 원소가 하나도 없다면 -1을 출력한다.
  • 또한 수열은 기본적으로 오름차순 정렬이 되어 있다는 점을 반드시 기억해야 한다.
  • 시간 제한 1초
  • 입력 예시
7 2
1 1 2 2 2 2 3
  • 출력 예시
4

2.3.2.1. 해결 아이디어

  • 시간 복잡도 O(logN)O(logN)으로 설계해야 한다고 했으니 일반 선형 탐색으로는 시간 초과 판정을 받는다.
  • 여기서 또 주목할 점은 지금 수열이기에 데이터가 정렬되어 있어서 이진 탐색을 수행할 수 있다.
  • 특정 값이 등장하는 첫 번째 위치와 마지막 위치를 이진 탐색을 통해 찾은 뒤에 위치 차이를 계산해서 문제를 해결할 수 있다.
  • 다시말해 처음 전체 탐색 범위에 대해서 이진 탐색을 2번 수행하여
    하나의 이진 탐색은 첫 위치를 찾도록 만들고
    다른 하나의 이진 탐색은 마지막 위치를 찾도록 만들면 된다.

2.3.2.2. ⭐ 코드로 확인

from bisect import bisect_left, bisect_right

def count_by_range(array, left_value, right_value):
    left_index = bisect_left(array, left_value)
    right_index = bisect_right(array, right_value)
    return right_index - left_index

# N: 데이터 개수 / x: 찾고자하는 값
N, x = map(int, input().split())
array = list(map(int, input().split()))

# [x, x] 범위에 있는 데이터의 개수 계산
count = count_by_range(array, x, x)

# x인 원소가 존재하지 않는다면
if count == 0:
    print(-1)
# 값이 x인 원소가 존재한다면
else:
    print(f"찾는 \"{x}\"는 현재 수열 {array}에 \"{count}\"개 존재합니다.")

profile
julian
AI Model Developer
이전 포스트

[코테] 코딩테스트 준비 (6)

0개의 댓글