이제 본격적인 알고리즘의 출발점을 지나봅시다. 지금까지 우리는 프로그램의 표준 입출력 처리 방법과 데이터 타입(자료형), 조건과 반복, 데이터 구조(선형, 비선형)를 배웠습니다. 이것을 토대로 어떤 문제를 해결하기 위한 정형화된 작업 절차, 알고리즘을 다룰 수 있습니다. 가장 먼저 해볼 것은 구조화된 데이터에서 원하는 값을 찾는 "탐색(search)"입니다.
1. 선형 탐색(linear search)
선형 탐색은 가장 기본적이고 직관적인 탐색 방법입니다. 이 알고리즘을 좀 더 쉽게 풀어 쓴다면 "하나씩 다 꺼내보기"라고 할 수 있습니다. 정말 말 그대로 원하는 정보가 나타날 때까지 모든 데이터를 확인해보는 것이기 때문입니다. 그래서 작업 자체가 "비교"와 "반복"의 두 단계로 매우 단순하게 구성되어 있습니다. 바로 코드를 살펴볼까요?
IATA_kor = ["ICN", "GMP", "PUS", "CJU", "TAE", "CJJ", "MWX", "YNY"]
find = input("공항의 IATA 코드를 입력해주세요.\n")
for airport in IATA_kor:
if find == airport:
print(f"{find}은(는) 대한민국의 국제공항입니다.")
break
else:
print(f"{find}은(는) 대한민국의 국제공항이 아닙니다.")IATA_kor 배열은 우리나라의 국제공항 IATA 코드 목록입니다. 입력받은 find가 이 중에 있는지 확인합니다. 배열에 저장된 값을 하나하나 꺼내와서 비교해보고 맞는지 찾아보면 끝입니다. 너무 간단하죠? 하지만 단점도 존재합니다. 지금은 8개 공항의 IATA 코드를 관리하고 있기 때문에 검색할 때 최악의 경우 8개를 모두 확인해보면 됩니다. 한국의 국제공항만이 아니라 세계에 있는 모든 IATA 코드를 관리한다면 꽤 오래 걸리게 될지도 모릅니다.
이미 지난 번에 풀어본 문제지만 다시 풀어봅시다. 지난 번에는 집합을 사용했었습니다. 이번에는 선형 탐색으로 도전해봅시다.
아마 시간 초과가 나올 겁니다. 이제 "시간복잡도"라는 개념을 익혀서 왜 시간 초과라는 결과가 나온 건지 알아봅시다.
0. 시간 복잡도(Big-O)
프로그램은 많은 연산을 빠르게 처리하는데, 아무리 빨라도 연산의 양이 그만큼 많다면 걸리는 시간은 늘어나기 마련입니다. 우리가 도전하고 있는 문제들에는 모두 시간 제한이 있습니다. 보통 2초의 제한이 많이 걸려있고, 어떤 문제는 1초, 또는 더 짧거나 길기도 합니다. 우리가 작성한 코드의 프로그램이 작업을 수행하는데 걸리는 시간은 실제로 채점 서버에서 테스트 케이스를 입력으로 주었을 때 출력을 반환하고 프로그램이 종료되기까지 걸리는 시간으로 측정됩니다. 그래서 같은 코드라도 테스트 케이스에 따라 걸리는 시간이 달라지기도 합니다. 하지만 우리가 고려해야 하는 것은 최악의 경우에도 시간 제한을 넘기지 않는 것입니다.
1번의 연산(덧셈)을 수행할 때 1이라는 시간이 소모된다고 해봅시다. 1억번의 연산을 수행하면 1억이겠죠? 1억의 시간이 1초로 환산된다고 생각하면 대강 맞습니다. 따라서 2초의 시간 제한이 걸린 문제는 연산 횟수가 2억을 넘어서면 안되겠죠. "1920 수 찾기" 문제의 입력 범위를 다시 살펴봅시다. N은 10만 이하, M도 10만 이하의 자연수로 주어집니다. 그렇다면 최악의 경우, 10만 개의 A에 대해 10만 번의 비교가 필요합니다. 10,000,000,000번의 연산, 초로 환산해보면 100초 정도 걸리게 됩니다. 시간 제한이 1초인 것을 보면 이제 당연한 결과입니다. 이 문제에서 예상되는 최악의 연산 횟수는 N*M이라고 할 수 있습니다. 이걸 O라는 함수로 나타내면 O(N*M)으로 표현됩니다. 이게 바로 시간 복잡도를 나타내는 빅-오 함수입니다.
알고리즘마다 예상되는 시간 복잡도가 다릅니다. 방금 알아본 선형 탐색의 경우, N개를 탐색할 때 시간 복잡도가 O(N)입니다. N이 커질수록 시간도 증가한다는 의미입니다. 어떤 문제는 O(N2)의 시간 복잡도를 갖습니다. 이 경우는 N이 증가함에 따라 걸리는 시간이 더 크게 증가하겠죠. 연산이 얼마나 반복되고 있는지를 안다면 어느 정도 예상할 수 있습니다.
2. 이분 탐색(binary search)
선형 탐색의 압도적인 편리함의 이면에 있는 시간 자원의 효율 문제를 살펴봤습니다. 이걸 해결 할 수 있는 더 빠른 방법은 없을까요? 업 앤 다운이라는 게임이 있습니다. 술래가 마음 속으로 정한 숫자를 다른 사람들이 맞히는데, 사람들이 추측한 숫자가 술래가 정한 숫자보다 크다면 "다운", 작다면 "업"을 외칩니다. 1부터 100까지의 숫자 중 하나를 정했을 때 가장 빠르게 맞히려면 처음으로 추측해야 하는 숫자는 뭘까요? 1과 100의 한 가운데 있는 50입니다. 만약 술래가 "다운"이라고 한다면 다음 숫자는 25를, 다시 "다운"이라면 12를 말해야 합니다. 이런 식으로 범위를 반씩 줄여가며 찾아가는 탐색을 "이분 탐색"이라고 합니다. 먼저 코드를 보면서 과정을 알아봅시다.
arr = sorted(list(map(int,input().split())))
t = int(input())
l,r = 0, len(arr)
while l < r:
m = (l+r)//2
if arr[m] < t:
l = m+1
else:
r = m
print(r)이분 탐색은 2개의 변수로 탐색 범위를 좁혀나가며 이뤄집니다. 탐색 범위의 왼쪽 끝을 l, 오른쪽 끝을 r이라고 지정했습니다. 반복문은 탐색 범위의 왼쪽 끝이 오른쪽 끝보다 작을 때만 실시합니다. 그리고 매 반복마다 m을 l과 r의 중간 지점으로 정하고 arr[m]의 결과가 원하는 값보다 작은 경우는 탐색 범위의 왼쪽(l)을 m보다 1큰 값으로 당겨오고, 반대의 경우는 탐색 범위의 오른쪽(r)을 m으로 당겨옵니다. 아래 그림을 볼까요?
이렇게 탐색 범위의 양 끝을 t가 포함되도록 반토막씩 당겨온다는 이미지를 기억해두시면 됩니다. 그런데 이분 탐색을 실시하기 위해서는 매우 중요한 선제 조건이 하나 있습니다. 탐색하려는 데이터가 "정렬"되어 있어야 합니다. 탐색 범위의 가운데를 봐서 원하는 값과 비교해 양쪽 중 한 부분을 버리는 것이기 때문에 정렬되어 있지 않으면 사용할 수 없습니다. 배열을 정렬시킬 수 있는 sort() 함수를 사용하면 파이썬에서 가장 편리하고 빠른 정렬이 가능합니다.
이제 아까 시간 초과로 실패했던 문제를 이분 탐색으로 다시 도전해볼까요? 참고로 이분 탐색의 시간 복잡도는 O(logN)입니다. 이 문제의 경우는 O(log(N*M))이 되겠죠? 최악의 경우라도 약 160만 번의 반복으로 충분히 시간 제한 내에 해결할 수 있게 되었습니다.
힌트
N = int(input())
l,r = 0,N
while # < #:
m = (#+#)//2
if m*m < #:
# = m+1
else:
# = m
print(r)
#예제?) 백준 15641 SUPER SUPER BINARY SEARCH...
이 문제는 번외 문제인데 이분 탐색의 과정을 직접 수행하는 재밌는 문제입니다. 동시에 풀어볼 수는 없으니 시간이 되실 때 도전해보면 좋습니다.
3. 투 포인터(two-pointer)
C언어를 배워보신 분은 "포인터"라는 개념을 들어보셨을 거예요. 접근할 저장 공간의 위치를 특정하는 매우 중요한 요소인데 투 포인터의 포인터는 비슷하지만 조금은 다릅니다. 일단 어딘가를 지목한다는 점에서는 같습니다. 투 포인터 알고리즘은 순차적으로 이루어져야 하는 작업이지만 서로 다른 두 지점에서 동시에 순차적 작업을 각각 진행해야 하는 경우 사용합니다. 말로 풀어 설명하면 또 복잡하니 예시를 들어볼게요.
이런 숫자 배열이 있습니다. 여기서 두 수를 골라 "26"을 만들 수 있는지 알아보려고 해요. 다양한 방법이 가능하겠지만 투 포인터로 해결한다면 우선 두 개의 포인터가 배열의 맨 처음 3과 마지막 19를 가리키도록 합니다. 그리고 이 두 개의 포인터가 가리키는 숫자의 합에 따라 각 포인터의 위치를 바꿔줍니다.
3과 19의 합은 22입니다. 아직 26이 되려면 조금 부족합니다. 파란 포인터를 다음 칸으로 옮기면 포인터의 합이 커집니다.
6+19=25 아직도 부족하니 파란 포인터를 다시 한 칸 옮깁니다. 8+19=27 이제 26을 넘었으니 줄여야 합니다. 빨간 포인터를 앞으로 당기면 합이 줄어듭니다. 8+18=26 원하는 답을 찾았습니다!
투 포인터의 활용 방법은 매우 다양합니다. 보여드린 예시처럼 정렬되어있는 수의 양 끝에서 출발하는 문제도 있고, 둘 다 앞에서 출발해 구간의 합을 구하는 문제도 있습니다. 또는 완전히 다른 두 배열에서 각각 움직이는 포인터를 둘 수도 있습니다. 당연히 세 포인터도 가능하겠죠? 이건 문제를 보고 적절히 설계하면 될 것 같습니다. 한 가지 주의할 점은 포인터가 두 개나 되니 배열의 범위를 벗어나는 것이 언제인지 면밀히 따져봐야 한다는 것입니다. 저도 이 부분에서 실수를 많이 하곤 합니다. 그럼 문제를 풀어봅시다.
힌트
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
i,j = 0,0
C = []
while # < # and # < #:
if A[i] < B[j]:
C.append(#[#])
# += 1
else:
C.append(#[#])
# += 1
while # < #:
C.append(#[#])
# += 1
while # < #:
C.append(#[#])
# += 1
print(*C)4. 슬라이딩 윈도우(sliding window)
투 포인터 문제 중, 어떤 문제는 두 개의 포인터 사이 간격이 일정하게 유지되는 경우가 있습니다. 이렇게 두 개의 포인터가 동시에 같은 방향으로 움직이는 문제는 포인터가 마치 창틀 위를 움직이는 창문 같다고 하여 "슬라이딩 윈도우"라는 이름이 붙습니다. 투 포인터를 이미 배웠으니 어떻게 보면 더 쉬운 테크닉입니다. 바로 문제를 살펴봅시다.
힌트
N,K = map(int,input().split())
temp = list(map(int,input().split()))
s = 0
for i in range(K):
s += temp[i]
high = s
l,r = #,#
while # < N:
s = # - temp[#] + temp[#]
# += 1
# += 1
if # < #:
# = #
print(high)슬라이딩 윈도우에서 주의할 점은 투 포인터와 마찬가지로 탐색하는 배열의 범위를 벗어나는 게 언제인지, 반복의 탈출 조건을 잘 세워놓는 것입니다. 그리고 일반적인 투 포인터와는 달리 포인터가 동시에 움직이기 때문에 포인터로 감싸지는 범위에 새로운 값을 추가하는 것과 마지막 값을 제외하는 작업을 함께 진행해야 한다는 것도 실수하기 쉬운 부분입니다.
