[Python] 알아두면 좋을 기타 알고리즘

🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의 '이것이 취업을 위한 코딩 테스트다 with 파이썬'이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다.

 

이번 포스팅에서는 책 속 이론의 마지막 부분인 평소에 알아두면 코딩 테스트나 기타 상황에 잘 사용할 수 있는 기타 알고리즘들에 대해 소개하려고 한다. 소개할 알고리즘 종류들은 소수의 판별, 에라토스테네스의 체, 투 포인터, 구간 합 계산, 순열과 조합으로 총 5가지 알고리즘들에 대해 소개한다.

 

문제 풀이에 반짝 아이디어로 사용될 기타 알고리즘에 대해 알아보자.

---

1. 소수의 판별

먼저 소수란, 2 이상의 값들 중 약수가 자신과 1밖에 없는 수를 의미한다. 예를 들면, 2, 3, 7, ... 977, 983, 991, 997 등이 있다. 이렇게 소수를 판별하기 위한 알고리즘은 어떻게 짤까? 특정한 값 X가 주어졌을 때, X가 소수인지 아닌지 판별하는 알고리즘 코드이다. 단순한 방법은 2부터 X-1까지 X에서 하나씩 나누어보면서 모두 나누어 떨어지지 않으면 소수, 한 번이라도 나누어 떨어지면 소수가 아니라고 판별할 수 있다. 소스코드는 다음과 같다.(참고로 1은 소수가 아니며 소수의 범위는 2부터 임을 잊지 말자!)

 

def is_prime_number(x):
    for i in range(2, x):
        if x % i == 0:
            return '소수X'
    return '소수'

 

하지만 위와 같은 단순한 방법은 X값이 커질수록 시간복잡도가 매우 커진다는 문제를 발생시킨다.(시간복잡도 $O(X)$) 그래서 개선된 소수 판별 방법이 있다. 바로 2부터 주어진 X값의 제곱근까지만 X와 나누어떨어지는지 까지만 확인하면 된다. 왜냐하면 X값이 주어졌을 때, 약수를 일일이 나열하고 나면 X의 제곱근 값을 기준으로 양쪽으로 대칭을 이룬다는 것을 알 수 있다. 예를 들어, X = 16 이라면, 1 X 16, 2 X 8, 4 X 4, 8 X 2, 16 X 1 이 된다. 즉, 16의 제곱근인 4를 기준으로 대칭이다. 만약 X가 홀수인 X = 15 라고 가정해보자. 1 X 15, 3 X 5, 5 X 3, 1 X 15 이다. 15의 제곱근은 3.87... 이지만 여기에 내림을 적용해 3까지만 확인하면 된다. 따라서 개선된 소수 판별 소스코드는 아래와 같다.

 

import math

def is_prime_number(x):
    for i in range(2, int(math.sqrt(x))+1):
        if x % i == 0:
            return '소수X'
    return '소수'

 

위와 같이 수행하면 시간복잡도가 $O(X^{1/2})$ 로 줄어드는 것을 볼 수 있다. 그런데 만약 문제에서 특정 수의 범위가 주어지고 그 범위 안에 있는 소수들을 모두 출력하라면 어떻게 할까? 위의 알고리즘을 그대로 사용하면 위 함수를 주어진 범위만큼 반복해야 할 것이기 때문에 문제가 발생한다. 그 때는 에라토스테네스의 체 라는 알고리즘을 활용하자.

2. 에라토스테네스의 체

위에서 말했다시피 해당 알고리즘은 문제에서 특정한 범위, 예를 들어 1~N 까지의 범위가 주어졌을 때, 범위 안에 드는 소수들을 출력하는 알고리즘이다. 에라토스테네스의 체 알고리즘은 다음과 같은 단계로 작동한다.

 

1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 처리하지 않은 가장 작은 수 $i$ 를 선택한다.
3. 남은 수 중에서 $i$의 배수들을 모두 제거한다. 이 때, $i$는 제거하지 않는다.
4. 더 이상 반복할 수 없을 때까지 위 과정을 반복한다.

위 과정을 모두 수행하고 난 뒤, 남은 수들이 소수임을 알 수 있다. 이 때, 가장 작은 수 $i$를 매 단계마다 설정할 때, 2부터 N까지 모두 할 필요 없이 이 때도 N의 제곱근까지만 수행해주면 된다. 소스코드는 아래와 같다.

 

import math

n = 1000
array = [True for _ in range(n+1)]  # 또는 [True] * (n+1)

def find_prime_number_range(n, array):
    # 2 ~ N제곱근까지 반복
    for i in range(2, int(math.sqrt(n))+1):
        if array[i] == True:
            j = 2
            # i의 배수들 모두 제거
            while i * j <= n:
                array[i * j] = False
                j += 1
    # 에라토스테네스 알고리즘 후 다수의 소수 출력
    for i in range(2, n+1):
        if array[i]:
            print(i, end=' ')

find_prime_number_range(n, array)

 

위 알고리즘은 시간 복잡도가 $O(NloglogN)$으로 매우 빠르게 동작한다. 하지만 주어진 데이터 범위가 억 단위로 넘어가면 메모리 측면에서 문제가 발생한다. 왜냐하면 위 소스코드를 잘 보면 array 변수로 주어진 데이터 범위만큼의 빈 리스트를 할당한다. 따라서 데이터 범위가 억 단위로 크다면 빈 리스트를 할 당하는 데 메모리 이슈가 발생한다. 그래서 보통 에라토스테네스의 체를 이용해야 하는 문제라면 데이터 범위가 1,000,000(백만) 이하로 주어진다고 한다.

3. 투 포인터

3-1. 특정한 합을 갖는 부분 연속 수열 찾기

투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때, 2개의 점의 위치를 기록해서 처리하는 알고리즘이다. 예를 들어서, 40명의 학생 중 2,3,4,5,6,7 번 학생을 불러내고 싶을 때, 한 번에 '2번 부터 7번 까지' 라고 부를 수도 있다. 이처럼 리스트에 담긴 데이터에 순차(연속)적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. 투 포인터를 사용할 수 있는 대표적인 예시로는 어떠한 주어진 수열에서 특정한 합(M)을 갖는 부분 연속 수열 찾기 문제를 해결할 수 있다. 예를 들어서, [1, 2, 3, 2, 5] 라는 수열이 주어졌을 때, 특정한 합(M)이 5인 부분 연속 수열을 찾는다고 해보자. 그렇다면 [2, 3], [3, 2], [5]가 될 것이다. 이렇게 부분 연속 수열을 찾기 위해 투 포인터 알고리즘을 활용해보자. 알고리즘 단계는 다음과 같다.

 

1. 시작점(start)와 끝점(end) 둘다 첫 번째 원소 인덱스(0)을 가리키도록 한다.
2. 현재 시작점, 끝점이 가리키는 수열의 부분합(이를 S라고 하자) < M 이면, end + 1을 시킨다. 즉, 현재 수열의 부분합 S가 M보다 작으니 원소가 더 필요한 시점이다. 따라서 오른쪽으로 가서 원소를 더 포함시켜야 하므로 끝점을 +1 해준다.
3. 현재 부분합 S >= M 이라면 start + 1을 시킨다. 즉, 현재 S가 M보다 크다면 현재 부분합에서 특정 값을 빼주어 M이랑 맞춰주어야 하기 때문에 시작점에 있는 원소를 빼주기 위해 start + 1 해준다. 이 때, S = M 일때는 우리가 찾고자하는 부분 연속 수열을 찾았다는 카운트를 +1 해주고 start + 1을 해주어야 한다.
4. 시작점이 주어진 수열의 마지막 인덱스로 갈 때까지 위 과정을 반복한다.

단, 투 포인터는 주어진 리스트 내 원소가 음수 데이터가 포함되어 있지 않을 때 해결이 가능함을 잊지말자! 소스코드는 다음과 같다.

 

import sys

N = 5  # 주어진 수열 길이
M = 5  # 찾고자 하는 부분 합
data = [1, 2, 3, 2, 5]  # 주어진 수열

count = 0  # 부분 연속 수열 개수 셀 변수
interval_sum = 0  # M값과 비교할 현재 부분합(S)
end = 0    # 끝점 인덱스

# 시작점 인덱스를 증가시키면서 end를 맞춤
for start in range(N):
    # S >= M될 때까지 끝점을 하나씩 증가시키기
    while interval_sum < M and end < N: # end <= N 등호넣으면 out of range index
        interval_sum += data[end]
        end += 1
    # S == M된 순간, 부분 연속 수열 발견!
    if interval_sum == M:
        count += 1
    # S >= M인 경우, 시작점 +1을 해야하는데, 기존 시작점에 있는 값을 부분합에서 빼면 됨
    interval_sum -= data[start]

print(count)

3-2. 정렬되어 있는 두 리스트의 합집합

투 포인터는 이미 각자 정렬되어 있는 두 리스트의 원소를 합쳐서 정렬한 결과를 만드는 데에도 활용이 된다. 예를 들어, A = [1 ,3 ,5], B = [2, 4, 6 ,8]이 있을 때, 투 포인터를 활용하면 A, B 두 리스트를 합친 리스트를 Z라고 할 때, Z = [1, 2, 3, 4, 5, 6, 8] 의 결과를 출력시킨다. 참고로 이러한 투 포인터를 활용한 알고리즘은 병합 정렬(Merge Sort)같은 알고리즘에 사용된다고 한다. 어쨌건 투 포인터를 활용해 정렬되어 있는 각 두 리스트를 합집합 하여 정렬하는 단계를 알아보자.

 

1. 정렬된 리스트 A, B를 입력받는다.
2. 리스트 A에서 처리되지 않은 원소들 중 가장 작은 원소를 인덱스 번호 $i$가 가리키도록 한다.
3. 리스트 B에서 처리되지 않은 원소들 중 가장 작은 원소를 인덱스 번호 $j$가 가리키도록 한다.
4. A[$i$], B[$j$] 값 간의 대소 비교를 수행하고 더 작은 값을 결과 리스트 Z에 넣는다.
5. 그리고 Z에 넣은 더 작은 값을 갖고 있던 인덱스($i$ 또는 $j$)를 +1 시켜준다(인덱스를 오른쪽으로 이동)
6. 위 과정을 리스트 A와 B가 처리할 원소가 없을 때까지 반복한다.

만약 두 리스트 A, B 중에 리스트 A의 모든 원소들이 결과 리스트 Z에 먼저 다 들어갔다면, 그 이후부터는 B 리스트에 아직 처리하지 않은 남은 원소들을 결과 리스트 Z에 차례로 넣어주면 된다.(차례로 넣어줄 수 있는 이유는 A, B가 이미 정렬되어 있는 리스트이기 때문!)

 

이런 투 포인터를 이용한 알고리즘은 리스트 A의 길이를 $N$, 리스트 B의 길이를 $M$이라고 했을 때, 총 시간 복잡도는 $O(N+M)$이 된다. 왜냐하면 A, B의 각 인덱스인 $i$, $j$는 각각 리스트의 모든 원소를 한번씩 지나치기 때문이다. 이를 구현한 소스코드는 아래와 같다.

 

import sys

n, m = 3, 4  # a의 길이, b의 길이
a = [1, 3, 5]
b = [2, 4, 6, 8]

i, j = 0, 0   # 리스트 a, b의 초기 인덱스
# 합집합한 결과 리스트
result = [0] * (n+m)
k = 0  # 결과 리스트의 초기 인덱스

# i, j가 각 리스트 a, b를 모두 탐색할 때까지 반복
while i < n or j < m:
    # b 리스트를 모두 탐색했거나, a[i] < b[j] 이라면, a[i] 값을 모두 결과 리스트에 넣기
    if j > m or (i < n and a[i] < b[j]):
        result[k] = a[i]
        i += 1
    else:                     # a[i] == b[j] 일 경우, 아무거나 넣어도 상관 없음
        result[k] = b[j]
        j += 1
    k += 1  # 결과 리스트 인덱스 증가

for r in result:
    print(r, end=' ')

4. 구간 합 계산

코딩 테스트에는 주로 '구간 합 계산' 문제 유형이 자주 출제된다. 연속적으로 N개의 나열된 수가 있을 때, 특정 구간의 모든 수를 합한 값을 구하는 문제이다. 예를 들어, A = [10, 20, 30, 50, 100] 이 있을 때, 3번째~5번째 구간의 합을 구하라고 한다면, 30 + 50 + 100인 180이 된다. 보통 문제에서는 여러개의 쿼리 형태로 주어지고 각 쿼리마다 구간의 합을 출력하라고 한다. 예를 들어, 3개의 쿼리 [1, 3], [2, 5], [3, 4] 라고 하면 1~3번째 구간의 합, 2~5번째 구간의 합, 3~4번째 구간의 합을 구하라는 것이다. 답은 각각 60, 200, 80이 될 것이다. 

 

그런데 위와 같은 여러개의 쿼리(M개)가 주어졌을 때, 매번 구간 합을 구하게 된다면 시간 복잡도가 $O(MN)$이 된다. 이는 주어진 데이터 범위와 쿼리 개수가 증가하면 시간 초과 문제가 발생한다. 따라서 우리는 0~1번째 구간 합, 1~2번째 구간합, 1~3번째 구간합, ... , 1~N번째 구간 합을 한 번 미리 계산해놓고 쿼리가 들어올 때마다 미리 계산한 합을 이용해서 시간 복잡도를 줄일 수 있다. 이를 접두사 합을 계산한다고 한다. 구간 합을 계산하는 알고리즘은 간단하다.

 

1. 주어진 배열에 대한 접두사 합 배열 P를 계산한다.
2. 매번 쿼리인 [Left, Right]가 들어왔을때, P[Right] - P[Left-1] 을 계산해서 출력한다.

예를 들어보자. 아까와 같이 주어진 데이터 A = [10, 20, 30, 50, 100]가 있다. 우리는 이에 대해 접두사 합 배열 P를 다음과 같이 계산할 수 있다. P = [0, 10, 30, 60, 110, 210] 이다. 이 때, 맨 앞의 0은 0번째 구간이니 아무것도 없으므로 0이다. 이 때, 쿼리 [Left, Right] = [2, 4]가 들어왔다. 그러면 접두사 테이블 P로 가서 P[4] - P[2-1] = P[4] - P[1]을 구하면 된다. 즉, 텍스트로 풀어내면 "0~4번째 구간의 합 - 0~1번째 구간의 합" 을 빼면 결국 구하고자 하는 "2~4번째 구간의 합"을 계산해낼 수 있다. 

 

이렇게 하면 시간복잡도가 매 쿼리당 $O(1)$이게 된다. 따라서 맨 처음에 접두사 합을 만드는 데 드는 시간 $O(N)$과 M개의 쿼리에 대한 처리 $O(M)$을 해서 총 시간 복잡도는 $O(N+M)$이 되게 된다. 소스코드는 아래와 같다.

 

import sys

n = 5
data = [10, 20, 30, 40, 50]

prefix = [0]
sum_value = 0

for d in data:
    sum_value += d
    prefix.append(sum_value)

# 쿼리가 주어짐 -> 2~3번째 구간의 합은?
left = 2
right = 3

result = prefix[right] - prefix[left-1]
print(result)

5. 순열과 조합

순열과 조합에 대해서는 Python3 이상에서 itertools 라이브러리로 기본적으로 제공이 된다. 사용 방법은 저번 포스팅에 자세히 기록해 놓았다. 기억해야 할 차이점은 순열은 순서가 서로 다른것도 다른 것으로 간주하지만 조합은 순서가 다른 것도 같은 것으로 간주한다는 것을 기억하자!