JeroCaller

쌓여만 가는 빈 캔

4 분 소요

주어진 입력값들 중 최대(또는 최소)값을 찾는 알고리즘 중 하나로 토너먼트 알고리즘이 있다. 말 그대로 마치 스포츠나 게임 등의 대진 경기에서처럼 토너먼트 식으로 여러 입력값들을 둘 씩 묶어 각자 비교 연산을 하여 더 큰 숫자가 다음 라운드에 진출하여 위로 올라가는 방식으로 최대값을 찾는 알고리즘이다. (두 숫자가 똑같으면 한 숫자를 다음 라운드에 진출시킨다) 보통 입력값들의 크기 N은 2의 제곱수를 택한다.

8개의 숫자들 중 최대값을 찾기 위한 토너먼트 알고리즘. [1] 참조.

8개의 숫자들 중 최대값을 찾기 위한 토너먼트 알고리즘. [1] 참조.

위 사진에서는 총 8개의 문제 인스턴스에 대해 최대값을 찾는 과정을 묘사하고 있다. 둘 씩 묶여 대진할 때마다 비교 연산이 적용되어 더 큰 숫자가 위로 올라간다. 이러한 과정을 반복하여 최종적으로 가장 큰 숫자 하나가 맨 위에 떠오르게 된다.

N=8개의 문제 인스턴스에 대해, 총 N-1 = 7번의 비교 연산이 실행되었다. 또한, 맨 위에 존재하는 9라는 숫자를 제외하고 총 3개층이 존재함을 알 수 있다. 그런데 이 3층이란 숫자는 N=8=2^3의 지수 부분인 3과 일치한다.

만약, 입력값들 중 두 번째로 가장 큰 수도 찾고자 한다면 어떻게 해야 할까? 위 사진을 예로 들면, 9와의 경쟁에서 진 4가 후보에 들 수 있다. 하지만 정말로 4가 두 번째로 큰 수인지 확인하려면 먼저 9와의 싸움에서 진 이전 층의 6과 비교 연산을 거쳐야 한다. 4와 6중 6이 더 크므로 6이 후보에 들었다. 여기서 또 한 번 9와의 경쟁에서 진 이전 층의 5와 비교해야 한다. 5보다 6이 크므로 최종적으로 주어진 입력값들 중 두 번째로 큰 수는 6임을 알 수 있다. 이를 구하기 위해 필요했던 추가 비교 연산 횟수는 3 - 1 = 2번이다(4와 6, 6과 5)

위에서 언급한 점들을 좀 더 일반화하면 토너먼트 알고리즘에 대해서 우린 다음의 사실들을 알 수 있다.

  1. 크기 \(N=2^K\) (K는 1 이상의 정수)를 갖는 입력값들에 대해 최대값을 찾기 위한 비교 연산은 총 N-1번 일어난다.
  2. 크기 \(N=2^K\)의 입력값들에 대해, 결과값을 도출하기 위해 거쳐야 하는 토너먼트의 층 수는 \(K = log_2 N\)이다. 위 사진을 예로 들면, \(N=2^3\) 개의 입력값들에 대해 최대값을 추출하기 위해 거쳐야하는 토너먼트 층 수는 \(K=log_2(8) = 3\)층임을 알 수 있다. 컴퓨터 과학에서는 log() 연산자를 사용하며, 해당 연산자는 base가 2임을 기본으로 한다. 대부분의 경우에 자연 로그 log의 밑을 10으로 하는 것과 대비되는 점이다. (10을 밑으로 하는 상용 로그 또는 자연 상수 e를 밑으로 하는 자연 로그만 취급하는 계산기를 사용해야한다면 \(log_2(N) = log(N)/log(2)\) 라는 사실을 이용한다) 앞으로 log(N)이라고 하면 밑이 2라고 생각하면 되겠다.
  3. 만약 두 번째로 큰 수를 찾고자 한다면 필요한 추가 비교 연산의 횟수는 \(K-1 = log_2(N) - 1\) 과 같다. 위 사진에서 두 번째로 큰 수를 찾으려면 필요한 추가 연산 횟수는 3-1=2번이다. 따라서 만약 최대값과 두 번째로 큰 수까지 구한다면 이에 필요한 비교 연산은 \((N-1)+(K-1)=N+log(N)-2\) 번이다.

다음은 최대값과 두 번째로 큰 수를 구하는 토너먼트 알고리즘을 구현하는 원리를 그림으로 표현한 자료이다.

[1] 참조.

[1] 참조.

토너먼트 알고리즘 구현 과정.

  1. 토너먼트를 하면 “승리”한 숫자와 “패배”한 숫자가 나올 것이다. 이 모든 과정을 기록하기 위해, “승리”한 숫자들을 저장하는 리스트와 “패배”한 숫자들을 저장하는 N-1 크기의 리스트를 준비한다.
  2. 입력값들을 왼쪽부터 2개씩 한 팀으로 묶고, 팀끼리 비교 연산을 한다. 그 결과로 “승리”한 숫자와 “패배”한 숫자를 같은 인덱스에 위치시켜 저장한다. 저장은 리스트의 왼쪽부터 저장한다.
  3. 이제 2라운드 경기 시작이다. 인덱스 0과 1, 1과 2에 위치한 숫자끼리 비교 연산을 수행한다. 그리고 그 결과를 차례대로 리스트 내 빈 공간 왼쪽부터 기록한다. 위 예제에서는 4번째 인덱스부터 그 결과를 저장하면 된다.
  4. 위 과정을 최대값 하나가 나올 때까지 반복한다.
  5. 최대값을 얻은 후에는 두 번째로 큰 수를 찾을 차례이다. 두 번째로 큰 수를 찾으려면 오른쪽부터 최대값(9)과 같은 인덱스에 위치한 “패배” 리스트의 숫자들과 비교 연산을 진행한다.

다음은 토너먼트 알고리즘을 구현한 코드이다.

def tournament(num_list: list[int]) -> tuple[int, int]:
    N = len(num_list)
    winners = [None] * (N-1)
    losers = [None] * (N-1)

    # 토너먼트 시작
    # 1라운드
    idx = 0  # 빈 공간 중 가장 왼쪽 위치의 인덱스
    for i in range(0, N, 2):
        if num_list[i] < num_list[i+1]:
            winners[idx] = num_list[i+1]
            losers[idx] = num_list[i]
        else:
            winners[idx] = num_list[i]
            losers[idx] = num_list[i+1]
        idx += 1

    i = 0
    # 2라운드 ~ K라운드 진행
    while idx < N-1:
        if winners[i] < winners[i+1]:
            winners[idx] = winners[i+1]
            losers[idx] = winners[i]
        else:
            winners[idx] = winners[i]
            losers[idx] = winners[i+1]
        i += 2
        idx += 1

    # 두 번째로 큰 수 찾기
    first = winners[-1]  # 첫 번째로 큰 수 
    second = losers[-1]  # 두 번째로 큰 수
    for j, value in enumerate(winners[::-1]):
        if value == first:
            if second < losers[j]:
                second = losers[j]
    
    return (first, second)

if __name__ == '__main__':
    data = [3, 1, 4, 1, 5, 9, 2, 6]
    result = tournament(data)
    print(result)

    data2 = [3, 1, 4, 2, 9, 6, 12, 5, 23, 45, 3, 8, 14, 20, 44, 1]
    result2 = tournament(data2)
    print(result2)

(9, 4)
(45, 23)

앞서 이론대로 비교 연산 사용 횟수를 계산하면 N=8에 대해 N+log(N)-2= 8 + 3 - 2 = 9일 것이다. 그런데 위 알고리즘의 실제 수행 시간은 생각보다 더 걸릴 수 있다. 이것은 알고리즘에 비교 연산 뿐만 아니라, winners, losers 와 같이 추가 메모리를 사용하고, 해당 리스트의 각 위치마다 값들을 할당해야 하기 때문이다. (그리고 두 번째로 큰 수를 찾는 과정에서 for문에서 “==” 연산을 N-1번 더 한 것도 작업 시간에 영향을 미칠 것이다)

Reference

[1] George T. Heineman, “Learning Algorithms: A Programmer’s Guide to Writing Better Code”, (O’Reilly, 2021)

This content is licensed under CC BY-NC 4.0

댓글남기기

참고