좋은 개발자가 되기 위해서는 문제 해결 능력이 필수적입니다. 제가 쓴 책 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"에서는 다양한 문제 해결 기법과 예제들을 소개합니다.

가장 가까운 원소 찾기

[처음으로] [모든 글 보기] [같은 카테고리의 글 보기: 알고리즘]


며칠 전, 시카고 파이썬 사용자 메일링 리스트에 다음과 같은 질문이 올라왔다:

340만개 쯤 되는 정렬된 자연수 배열 A랑, 30만개쯤 되는 자연수 배열 B가 있는데, B의 각 원소에 대해서 A중 가장 가까운 원소를 찾고 싶어요. 이런 데이터가 여러 개 있어서 가능한 빠르게 짰으면 좋겠는데 어떻게 하면 좋을까요?

예를 들어 A가 [1, 4, 7, 12, 18]이고 B가 [3, 10, 17]이라면 답은 [4, 12, 18]이란 얘기다.

(문제와는 별 상관 없지만 자연수 배열 A은 유전자 염기서열에서 특정 부분이 출현하는 위치의 목록이었다고 한다.)

이렇게 간단한 문제이지만 푸는 여러 가지 방법이 있다. 메일링 리스트에 답신을 쓴 김에 여기에도 다양한 방법들을 소개해 보도록 하겠다.

무식하게 풀기

내 책을 보신 분들은 알겠지만, 내게 있어 항상 가장 좋은 방법은 시간 안에 돌아가면서 가장 간단한 방법이다. 무식하게 풀면 어떨까? B의 각 원소에 대해 A의 각 원소들을 순회하면서 가장 가까운 원소들을 찾는다.

def closer(a1, a2, b):
    "a1 과 a2 중 b에 더 가까운 값을 반환한다."
    if a1 is None: return a2
    if a2 is None: return a1
    return a1 if abs(a1 - b) < abs(a2 - b) else a2

def brute_force(A, B):
    C = []
    for b in B:
        closest = None
        for a in A:
            closest = closer(closest, a, b)
        C.append(closest)
    return C

별 특이한 것은 없지만, 두 원소 중 어느 쪽이 b와 더 가까운지 확인하는 closer() 함수를 따로 만든 것을 눈여겨 보자. 물론 if문 내에 이것을 풀어 쓸 수도 있지만, closest는 처음에 None일 수 있기 때문에 if문 내용이 복잡해지게 된다. 이렇게 if문 내용이 길어질 경우 이렇게 함수로 만들어 뽑아내면 간결하고 알아보기도 쉬워진다.

이 알고리즘의 시간 복잡도는 $O(|A|\cdot|B|)$임을 쉽게 알 수 있다. (시간 복잡도 분석이란 말만 나와도 골치가 아프다면, 제 책을 사세요... 쿨럭) A와 B의 크기를 여기에 대입해 보면 대략 1조 정도 된다. 아무리 반복문의 내부가 단순함을 감안하더라도 죽기 전에 답을 얻을 가능성이 없다는 것을 몇 시간은 족히 걸릴 거라는 것을 알 수 있다.

이진 탐색

물론 이보다 훨씬 나은 방법이 있다. B에 포함된 숫자 b가 주어질 때, A에서 답이 될 수 있는 수를 쉽게 줄이는 방법이 있다. 이진 탐색을 쓰는 방법이다.

이진 탐색은 A에 b가 포함되어 있을 경우 이것을 쉽게 찾아낼 수 있지만, A에 포함되어 있지 않은 경우엔 어떨까? 이 경우 어떤 값을 반환해야 할까? 표준 라이브러리에 포함된 이진 탐색 알고리즘들은 대개 다음과 같이 정의된다:

$binsearch(A[], x)$: $A[i-1] < x \le A[i]$인 $i$를 반환한다.

다시 말해 배열에서 $x$를 삽입할 수 있는 첫 번째 위치를 반환한다는 뜻이다. 배열에 $x$가 포함되어 있을 경우 반환값은 첫 번째 $x$의 위치고, 없는 경우 $x$보다 큰 첫 번째 원소의 위치가 된다.

(이진 탐색 얘기할 때 빼놓을 수 없는 이야기가 생각하는 프로그래밍에 소개된 일화이다. 저자인 벤틀리가 수많은 직업 프로그래머들에게 이진 탐색을 짜라고 시켰는데, 그 중 10%만이 제대로 짰다는 충격 스토리!)

따라서 이 반환값이 있으면 결과값은 둘 중의 하나로 좁혀진다. 파이썬 표준 라이브러리의 bisect.bisect를 이용하면 다음과 같이 짤 수 있다:

import bisect
def binary_search(A, B):
    clip = lambda idx: max(min(len(A) - 1, idx), 0)
    C = []
    for b in B:
        idx = bisect.bisect(A, b)
        # A[idx-1] < b <= A[idx]
        C.append(closer(A[clip(idx - 1)], A[clip(idx)], b))
    return C

clip은 인덱스가 주어질 때 [0, len(A) - 1] 범위 내로 옮겨준다. 이진 탐색의 결과값인 idxlen(A)이거나 0일 경우를 해결하는 것이다. (언제 이런 값이 반환될까?)

이 방법의 시간 복잡도는 $O\left( |B|\cdot \lg |A| \right)$ 임을 쉽게 알 수 있다. A와 B의 크기를 대입해 보면 6백만 정도가 된다. 내 책에서 언급했지만 (책 광고 하려고 만든 블로그니 이해하시길.. ㅠ.ㅠ) 현대의 컴퓨터에서 1초에 수행할 수 있는 연산량은 대~~충 잡아도 충분히 1억 이상이므로, 눈 깜짝할 사이에 문제를 해결할 수 있다.

스위핑

하지만 이보다 빠른 방법은 따로 있다. 이진 탐색도 쓰지 않고 선형 탐색을 하는데, 이진 탐색보다 빠르다! 어떻게? 바로 우리가 가지고 있는 정보를 버리지 않으면 가능하다.

우선 B의 원소가 오름차순으로 정렬되어 있다고 가정해 보자. 이 때 B의 첫 번째 원소에 대해 가장 가까운 원소를 선형 탐색으로 찾는다. 그리고 나서 두 번째 원소에 대해 다시 문제를 풀자. 그런데 이 때 A의 맨 처음부터 찾아나갈 필요가 없을까?

물론 없다. B가 정렬되어 있다면 B[1] > B[0]이고 B[1]의 답이 B[0]의 답 이전에 있을 가능성은 없기 때문이다. 따라서 마지막에 가장 가까운 원소를 찾은 위치를 저장해 두고, 여기에서부터 시작하면 된다.

이것을 여러 가지 방법으로 구현할 수 있지만 내가 좋아하는 방법은 다음과 같다.

def sweeping(A, B):
    # assume B is sorted
    clip = lambda idx: max(min(len(A) - 1, idx), 0)
    C = []
    idx_a = 0
    for b in B:
        while idx_a + 1 < len(A) and A[idx_a + 1] < b:
            idx_a += 1
        C.append(closer(A[clip(idx_a)], A[clip(idx_a + 1)], b))
    return C

이 함수는 각 b에 대해 위에서 이진 검색의 결과에 해당하는 위치를 선형 탐색으로 찾는다.

이 알고리즘의 수행 시간을 분석하는 방법은 멋있게는 분할 상환 분석(amortized analysis)이라고 부르는데, 별건 아니다. idx_a += 1은 최대 몇 번이나 실행될까? idx_a가 A의 크기에 도달하면 더 이상 실행될 수 없다. C.append()는 B의 각 원소마다 한 번씩만 수행된다. 따라서 반복문 안의 모든 문장들이 실행되는 회수를 합하면 $O(|A|+|B|)$가 된다!

입력의 크기에 따라 다르지만 (예를 들어, A의 크기가 B에 비해 훠얼씬 훨씬 크다면 이진 탐색이 더 빨라질 수도 있을 것이다) 이 경우 이 방법은 이진 탐색보다도 더 빠르다.

numpy를 이용한 이진 탐색

하지만 나라면 두 구현 모두 쓰지 않을 것이다. 대신 numpy의 배열을 사용할 것이다. numpy는 파이썬을 위한 행렬/벡터 구현 등을 제공하는 라이브러리인데, 여기에서 그치지 않고 다양한 연산들의 "벡터화"된 버전을 제공한다. 예를 들어 numpy.minimum()은 두 개 이상의 크기가 같은 벡터를 입력받아 각 원소별로 최소값을 구해 주는 셈이다.

numpy에도 searchsorted라는 이진 탐색 함수가 있는데, bisect와 달리 찾는 값이 배열인 경우 배열을 반환한다!

이를 이용하면 다음과 같이 간결하게 (.. 사실 길이 차이는 별로 나지 않는 것 같군..) 이진 탐색을 이용한 답안을 짤 수 있다.

import numpy as np
def binary_search_np(A, B):
    # assume A and B are numpy arrays
    idx2 = np.minimum(len(A) - 1, np.searchsorted(A, B)) 
    idx1 = np.maximum(0, idx2 - 1)
    idx2_is_better = np.abs(A[idx1] - B) > np.abs(A[idx2] - B)
    np.putmask(idx1, idx2_is_better, idx2)
    return A[idx1]

이 함수가 어떻게 동작하는지 numpy reference를 보면서 확인해 보자. :-)

아마도 이 함수는 스위핑 버전보다도 빨리 동작할 것이다. numpy의 함수들은 모두 C나 포트란으로 작성되어 있어 무지하게 빠르기 때문이다.


[처음으로] [모든 글 보기] [같은 카테고리의 글 보기: 알고리즘]

2012 구종만