[ 이것이 코딩테스트다 ] 21일차

안영우·2021년 1월 25일

나동빈 코딩테스트

[ 이것이 취업을 위한 코딩 테스트다. with 파이썬 ]

목록 보기

21/39

✏️ 서론

오늘은 저번에 배웠던 순차탐색과 이진탐색을 이용한 문제를 풀어보려 한다.
교재에 수록된 문제와 백준에서 단계별 알고리즘 - 이분탐색 파트를 풀어보자.

✏️ 본론

📍 [ 문제 1 ] 부품 찾기(교재 수록)

이 문제는 선언된 리스트 중 찾고 싶은 값이 존재하는지 존재하지 않는지를 판별하는 문제이다.

해결방법은 여러가지이나, 가장 기초가 되는 이진 탐색 알고리즘으로 풀어보자.

먼저, 선언된 리스트를 번호로 기준으로 정렬하고 나서 찾고자 하는 부품이 각각 매장에 존재하는지 검사하면 된다.

이때, 매장의 부품들은 정렬이 되어있기 때문에 이진 탐색을 수행하며 찾을 수 있다.

정렬이 되지 않은 값은 이진탐색을 수행 할 수 없기때문에 정렬 후 사용하자.

'''
5
8 3 7 9 2
3
5 7 9
'''

import sys

def binary_search(array, target, start, end):
    if start > end:
        return False
    mid = (start + end) // 2
    if array[mid] == target:
        return True
    if array[mid] > target:
        return binary_search(array, target, start, mid-1)
    else:
        return binary_search(array, target, mid+1, end)

n = int(input())
array = list(map(int, sys.stdin.readline().split()))

m = int(input())
target = list(map(int, sys.stdin.readline().split()))

for i in target:
    if binary_search(array, i, 0, n-1):
        print("yes", end=' ')
    else:
        print("no", end=' ')
👉🏽 no yes yes

따라서 이렇게 문제를 풀면, 최악의 경우 시간 복잡도 O(M x logN의 연산이 필요하므로 이론상 최대 약 2,000,000번의 연산이 이루어진다고 분석할 수 있다.

오히려, N개의 부품을 정렬하기 위해 요구되는 시간 복잡도 O(N x logN)이 이론적으로 최대 약 20,000,000으로 더욱 많은 연산이 필요한 것을 알 수 있다.

결과적으로 이진탐색을 사용하는 문제 풀이 방법의 경우 시간복잡도는 정렬의 수까지 포함하여 O((M+N) x logN)이다.

또한 이 문제는 이진탐색 외에 계수정렬, 집합자료형을 이용하여 문제를 풀 수 있다.

계수정렬은 모든 원소의 번호를 포함할 수 있는 크기의 리스트를 만든 뒤에, 리스트의 인덱스에 접근하여 특정한 번호의 부품이 매장에 존재하는지 확인하면 된다.

이때, 모든 원소는 n+1의 범위로 잡아주자.

'''
5
8 3 7 9 2
3
5 7 9
'''
import sys

n = int(input())
array = [0] * 100001

for i in input().split():
    array[int(i)] = 1

m = int(input())
target = list(map(int, sys.stdin.readline().split()))

for i in target:
    if array[i] == 1:
        print('yes', end=' ')
    else:
        print('no', end=' ')

👉🏽 no yes yes

또, 집합자료형을 이용 할 수있는데 단순히 특정한 수가 한 번이라도 등장했는지를 검사하면되기 때문이다.

이러한 집합 자료형은 단순히 특정한 데이터가 존재하는지 검사할 때에 매우 효과적으로 사용할 수 있다.

'''
5
8 3 7 9 2
3
5 7 9
'''
import sys

n = int(input())
array = set(map(int, sys.stdin.readline().split()))

m = int(input())
target = list(map(int, sys.stdin.readline().split()))

for i in target:
    if i in array:
        print('yes', end=' ')
    else:
        print('no', end=' ')

👉🏽 no yes yes

하지만 이진탐색으로도 충분히 풀 수 있으며, 알고리즘 문제에 따라 시간과 메모리가 극히 제한되면 다른 알고리즘으로도 풀 수 있다는 점을 염두해두자.

📍 [ 문제 2 ] 떡볶이 떡 만들기(교재 수록)

전형적인 이진 탐색 문제이자, 파라메트릭 서치(Parametric Search) 유형의 문제이다.
파라메트릭 서치(Parametric Search)는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다.

자세한 내용은 강의를 참고하자.

예를 들어, 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다.

코딩 테스트나 프로그래밍 대회에서 보통 파라메트릭 서치 유형은 이진 탐색을 이용하여 해결한다.

이 문제의 아이디어는 다음과 같다.

적절한 높이를 찾을 때까지 절단기 높이 H를 반복해 조정한다.

현재 H 높이로 자르면 조건을 만족하는가?

조건 만족여부 (예, 아니오)에 따라 탐색범위를 좁혀간다.

이때, 이진탐색의 원리를 이용하여 절반씩 좁혀나간다.

절단기의 높이는 1부터 10억까지의 정수인데, 이처럼 큰 수를 보면 당연하다는듯이 가장 먼저 이진 탐색을 떠올리자.

'''
4 6
19 15 10 17
'''
n, m = list(map(int, input().split()))
array = list(map(int, input().split()))

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
            
    if total < m:
            end = mid - 1
    else:
            result = mid
            start = mid + 1

print(result)
👉🏽 15

또한, 이 문제는 현재 얻을 수 있는 떡볶이의 양에 따라서 자를 위치를 결정해야하기 때문에 이를 재귀적으로 구현하는것은 귀찮은 작업이 될 수 있다.

따라서, 이 문제와 같은 파라메트릭 서치 문제 유형은 이진탐색을 재귀적인 알고리즘 대신 반복문을 이용해 구현하면 더 간결하게 문제를 풀 수 있다.

📍 [ 문제 3 ] 백준 - 1920(수 찾기)

문제

단순하게 주어진 수에 해당하는 정수가 존재하는지 찾으면 되는 문제이다.
이진탐색과 set 자료형을 통해 문제를 풀었다.

# 이진탐색(재귀)
'''
5
4 1 5 2 3
5
1 3 7 9 5
'''
import sys

def find_number(array, target, start, end):
    if start > end:
        return False
    mid = (start + end) // 2

    if array[mid] == target:
        return True
    elif array[mid] > target:
        return find_number(array, target, start, mid-1)
    else:
        return find_number(array, target, mid+1, end)

n = int(input())
array = sorted(list(map(int, sys.stdin.readline().split())))

m = int(input())
target = list(map(int, sys.stdin.readline().split()))

for i in target:
    if find_number(array, i, 0, n-1):
        print(1)
    else:
        print(0)
👉🏽 
1
1
0
0
0
1

# set 자료형
'''
5
4 1 5 2 3
5
1 3 7 9 5
'''
import sys

n = int(input())
array = set(map(int, sys.stdin.readline().split()))

m = int(input())
target = list(map(int, sys.stdin.readline().split()))

for i in target:
    if i in array:
        print(1)
    else:
        print(0)
👉🏽 
1
1
0
0
0
1

결론적으로 둘 다 정답판정을 받았지만, set자료형을 이용한 풀이가 이진탐색(재귀)의 경우보다 3.8배 정도 시간이 단축된 것을 확인할 수 있었다.

📍 [ 문제 4 ] 백준 - 10816(숫자 카드 2)

문제

이 문제는 구현하는데 조금 어려웠다.
분명 이진탐색 단계에 있는 문제인데, 실제로 문제를 풀 때는 이진탐색을 이용하지않고, 딕셔너리, Counter을 이용해 문제를 풀었다.

첫번째 풀이는 n_dict이라는 딕셔너리를 array와 비교해 만약 array안에 n_dict값이 없으면 1을 추가해 n이 몇 번 추가되었는지 알 수 있게 작성했다.

예를들면 {'6': 1, '3': 2, '2': 1, '10': 3, '-10': 2, '7': 1} 처럼 말이다.

마지막에 target값을 n_dict와 비교해 해당 값이 존재하면 n_dict[i] 값 출력, 그렇지 않으면 0을 출력하게 설정했다.

'''
10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10
'''

# 딕셔너리 선언 후 값 비교
import sys

n = int(input())
array = sys.stdin.readline().split()
n_dict = {}

for i in array:
    if i in n_dict:
        n_dict[i] = n_dict[i] + 1
    else:
        n_dict[i] = 1

m = int(input())
target = sys.stdin.readline().split()

for i in target:
    if i in n_dict:
        print(n_dict[i], end=' ')
    else:
        print(0, end=' ')
👉🏽 3 0 0 1 2 0 0 2

두번째는 Counter함수를 사용했는데, 이를 target값과 비교해 해당 값이 count안에 존재하면 몇 개나 있는지 출력해주는 과정이다.

'''
10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10
'''
# Counter 함수 사용
import sys
from collections import Counter

n = int(input())
array = sys.stdin.readline().split()

m = int(input())
target = sys.stdin.readline().split()

count = Counter(array)

for i in target:
    if i in count:
        print(count[i], end=' ')
    else:
        print(0, end=' ')
👉🏽 3 0 0 1 2 0 0 2