(Swift) – 힙(Heap) – 자료구조에 대해

heap은 일종의 바이너리 트리를 단일 배열을 이용해서 구현한 구조로,  부모 자식 간의 직접적인 참조를 갖지 않고 배열의 인덱스에 의해서 위치 관계를 파악한다. 특히 내부 배열의 상태는 부분적으로 정렬되는 것과 비슷한데, 항상 “맨 앞의 원소를 꺼내었을 때 그 값이 최대 혹은 최소가 된다”는 특성을 가진다. 힙은 흔히 최대힙과 최소힙으로 구분하는데 이는 동일한 것이며 단지 정렬 순서만 다르다. 주로 자료 구조에서는 최대/최소 힙, 바이너리 힙, 힙 큐 혹은 우선순위 큐와 같은 이름으로 불린다.

참고로 이 자료 구조의 파이썬 구현은 [우선순위 큐 혹은 최소/최대힙]에서 한 번 설명한 바 있다.

힙으로 할 수 있는 일은 다음과 같다.

  1. 우선순위 큐를 만든다.
  2. 힙 정렬 수행
  3. 변경가능한 집합의 최소값(혹은 최대값)을 빈번히 계산해야 할 때 유용하다. (특히 최단거리 탐색 시)

(Swift) – 힙(Heap) – 자료구조에 대해 더보기

정수 배열의 최대 부분합 (연습문제)

배열의 연속된 부분집합의 최대합

정수 배열이 주어질 때 배열내의 연속된 원소를 더한 부분합의 최대값을 구하는 문제이다. 구간이 아닌 최대값 자체를 구하면 되는 문제이다.

간단히 생각하면 0부터 1, 2, 3 … n 까지의 합 중 최대인 값, 그 다음은 1부터 2, 3, 4 .. n 까지의 값 중 최대인값 이렇게 비교해나갈 수 있는데 그러면 반복계산이 너무 많다. 따라서 DP를 이용한다.

  1. 0번 인덱스까지의 최대합은 0번 값 그 자체이다.
  2. i번 인덱스까지의 최대 부분합은, (i-1) 번 까지의 최대 부분합과 i번 값의 합이다. 이 때 이전인덱스까지의 최대부분합이 0보다 작으면 더하지 않는다.

이렇게 하면 되지롱


func maxSubsum(arr: [Int]) -> Int {
    var result = Array(count: arr.count, repeatedValue: 0)
    result[0] = arr[0]
    for i in 1..<arr.count {
        result[i] = (result[i-1] > 0 ? result[i-1] : 0) + arr[i]
    }
    return result.reduce(result[0], combine: max)
}

참고로 swift3에서는 Array(count:repeatedValue:)Array(repeating:count:)로 인자의 위치가 뒤집어 졌으니 참고.

오일러프로젝트78

동전 100개를 나누는 방법

이 문제는 오일러 프로젝트 76번 문제와 같은 문제로 볼 수 있는데…. 처음 작성한 시점부터 너무 오래된 글이라, 진도를 기다리지 못하고 미리 발행한다.

5개의 동전이 있다.  이 동전들을 나누는 방법을 생각해 보자. 동전 5개는 아래와 같이 총 7가지 방법으로 나눌 수 있다.

ooooo  # 5개짜리 그룹 1개
oooo o  # 4개 + 1개
ooo oo  # 3개 + 2개
ooo o o # 3개 + 1개 + 1개
oo oo o # 2개 + 2개 + 1개
oo o o o # 2개 + 1개 + 1개 + 1개
o o o o o # 1개 + 1개 + 1개 + 1개

이렇게 동전 n개를 나눌 때의 나누는 방법의 가짓수를 p(n)이라 할 때, p(n)이 백만으로 나누어 떨어지는 최소의 n은 얼마인가?

접근

동전을 나누는 문제에 대해서 나눠진 각 그룹을 해당 그룹의 동전수로 치환하면  n을 n이하의 자연수의 합으로 나타내는 가지수와 같은 문제가 된다. 따라서 위의 도식은 아래와 같이 표현할 수 있게 된다.

5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

이는 동전의 종류가 1, 2, 3, 4, 5원이 있을 때 5원을 만드는 방법의 가지수와 동일하므로 결국 영국화폐조합1의 문제로 귀결된다. 따라서 n에 대해서 p(n)을 구하는 방법은 동적프로그래밍을 사용하여 풀 수 있고, 이는 아래의 코드로 표현할 수 있다.

def getWays(target):
    ways = [1] + [0] * target
    values = range(1, target+1)
    for value in values:
        for i in range(value, target+1):
            ways[i] += ways[i-value]
    return ways[-1]

print getWays(5)

문제는 이걸 가지고 값이 100만으로 나눠떨어지는 시점을 계산해야 한다는 점이다. n의 범위를 알 수 없기 때문에 좀 골치가 아픈 문제이다. 일단 무식하게 i = 2 부터 시작해서 1백만으로 나눠떨어지는 지점까지 찾아서 실행해보자.

i = 2
while True:
    w = getWays(i)
    if w % 1000000 == 0:
        print i, w
        break
    i += 1

뭐 이렇게 해놓고 마냥 기다렸을 때 언제 끝날지 모를 정도로 오래 걸린다. 동적 프로그래밍의 특성상 n에 대해서 P(n)을 구할 때는 재귀적인 방법들보다는 빠르게 계산할 수 있지만, 여기서는 n이 계속 바뀌기 때문이다. 따라서 n보다 작은 케이스부터 차례대로 계산하기 때문에 n이 커지면 커질수록 전체 계산시간은 지수적으로 증가하고, 이 루프에 있어서는 부분 문제를 중첩하는 방법을 찾기가 까다롭다.

찾을 수 있을지도 모르겠다. 이 부분은 더 고민이 필요할 듯 하다.

충분히 큰 수 M에 대해 계산한다면, M보다 작은 값 중에서 답이 있다면 오랜 시간이 걸리지 않을 수 있다. 하지만 M이 얼마가 될지 모르기 때문에 여기서 막히게 된다.

대안

그렇다면 작은 n에 대해서 P(n)을 계산해 나가면서 이전에 계산했던 값을 재활용할 수 있는 방법이 있는지 살펴보자. 어쨌거나 반복계산을 엄청나게 수행하는 것 보다는 이게 나을 것 같다. 동적 프로그래밍에 의해 값을 계산하는 과정을 추적해보면, 모종의 규칙을 발견하게 될지도 모르겠다.

이를 위해서 내가 세워본 룰은 다음과 같다.

  1. 각 n에 대해 가지수를 저장하는 배열 ways는 첫 원소가 1이고 나머지는 0으로 채워진 target + 1 만큼의 길이를 가지고 있다.
  2. 그리고 n 번째 항을 계산할 때는 n 보다 작은 자연수인 values의 각 value 값에 대해서 value 값 만큼 적은 인덱스의 값을 누적해서 더해주게 된다.

0   1   2   3   4   5   6 .... N
---------------------------------
1   0   0   0   0   0   0 .... 0

초기 값은 이런 형태가 된다. 자 그래서 1개짜리 그룹을 포함하는 경우는 각 n에 대해서 (n-1)번째의 현재값을 더한 것이 된다. 물론 이는 중간 과정이며, n=1,2,3… 의 순으로 각각 더해준다. 여기까지의 결과는 아래와 같고, 따라서 P(1) = 1 이 된다.

value: 1
0   1   2   3   4   5   6 .... N
---------------------------------
1   0   0   0   0   0   0 .... 0
    1   1   1   1   1   1 .... 1

계속해보자. 이번엔 2개짜리 그룹을 사용하느냐의 여부다. 이는 각 n에 대해서 (n-2)위치의 값을 더해주는 계산을 한다.  2의 맨 아래에는 0번의 값을 더했고, 4의 맨 아래에는 2에서 계산된 결과를 더했다.

value: 2
0   1   2   3   4   5   6 .... N
---------------------------------
1   0   0   0   0   0   0 .... 0
    1   1   1   1   1   1 .... 1
        1   1   2   2   2 .... ?

이제 P(2)=2로 계산됐다. 3부터 계속 채워나가 보자.

0   1   2   3   4   5   6 .... N
---------------------------------
1   0   0   0   0   0   0 .... 0
    1   1   1   1   1   1 .... 1
        1   1   2   2   3 .... ?
            1   1   2   3
                1   1   2
                    1   1
                        1

그래서 p(4) = 4, p(5) = 7, p(6) = 11 이 나오게 된다. (각 n에 대해서 해당 열의 세로로 나열된 숫자들의 합이 된다.) 그럼 이 값에서 p(7)을 계산할 수 있을까?  만약 아래와 같이 p(n)을 구하는 과정에서 총 합만을 남기는 것이 아니라, 모든 단계의 값을 분리해서 보관한다면 가능할 것 같다.

0   1   2   3   4   5   6 .... 7
---------------------------------
1   0   0   0   0   0   0 .... 0
    1   1   1   1   1   1 .... 1 --> p(6)중 0, 1 의 합
        1   1   2   2   3 .... 3 --> p(5)중 0, 1, 2 의 합 
            1   1   2   3 .... 4 --> p(4)중 0, 1, 2, 1 의 합
                1   1   2 .... 3 --> p(3)중 0, 1, 1, 1 의 합
                    1   1 .... 2 --> p(2)중 0, 1, 1 의 합
                        1 .... 1 --> p(1)중 0, 1의 합 
                               1 --> p(0)중 1의 합 

그렇다면 각 ways[n] 의 각 항이 단일 정수값이 아니라 리스트라면, p[n] = [ p[n-1][:2], p[n-2][:3], p[n-3][:4] ... p[0][:n]]  이 된다.

그럼 계산 과정의 수열들을 보존하고, 다음 항을 계산할 때 값을 추가해나가는 식으로 계산하는 코드를 짜보자.

class Dist(object):
    def __init__(self):
        self.n = 0
        self.ways = [[1]]

    def expand(self):
        self.n += 1
        self.ways.append([0])
        for value in range(1, self.n+1):
            self.ways[self.n].append(sum(self.ways[self.n-value][:value+1]))
        return sum(self.ways[self.n])

d = Dist()
for i in range(1, 11):
    print i, d.expand()

이를 실행해서 돌려보면 1~10 사이의 값에 대해서는 P(n)을 잘 구해준다. 하지만 이렇게 돌려서 구현한 목적은 “계산을 빠르게”하기 위한 것이었는데, n이 커지면 커질 수록 계산에는 여전히 많은 시간이 소요된다. (리스트에 대한 append 라든지 하는 부분들이 비용이 꽤나 큰 연산이다.) 실제로 계산해보면 이 방식도 너무나 느리다. 게다가 이 문제는 그 값 역시 엄청나게 커지기 때문에 큰 정수 연산이 들어가면서 계속 문제가 된다. 실제로는 백만으로 나눈 나머지만 확인하면 되기 때문에 백만 이상의 값은 버리도록 튜닝을 해 보아도 이렇게 풀어서는 답이 안나온다. 다른 접근법이 필요하다.

또다른 접근 : 분할수에 관련된 정리

특정 수를 다른 수의 합으로 표시하는 것을 분할수라고 한다. 분할수 관련해서 구글링을 해보면 오각수정리라는 것을 만날 수 있다. 이 정리는 보통 아래와 같은 수식으로 표현된다.

 p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + \cdots

이 때 1, 2, 5, 7은 오각수의 수열이며, 이 수열이 n보다 작을 때까지   P(n-k)들의 값을 더하거나 빼서  P(n)을 만들 수 있다는 것이다.  즉, 이를 정리하면 아래의 식이 된다.

 p(n) = \sum _{k} (-1)^{k-1}p(n-g_{k})  

이 때 g_{k}는 1, -1, 2, -2, 3, -3… 의 수열의 각 항을 이용해서 오각수 공식에 대입하여 얻은 수이다. 다음과 같이 정의한 함수를 통해서 얻을 수 있다.

def getPenta(k):
    # n: 1, -1, 2, -2, 3, -3 ...
    n = (k/2 + 1 if k % 2 == 0 else (k / 2)* -1 - 1)
    return n*(3*n - 1) / 2

이 수열은 다음과 같이 나온다.

1
2
5
7
12
15
22
26
35
40

그럼 이제 일반항을 구하는 생성함수를 보자.

 p[n] = p[n-1] + p[n-2] - p[n-5] - p[n-7] + p[n-12] ....

이런 식으로 이어지며, 이 때 p[0] = 1, p[음수] = 0 으로 처리된다. 즉 g_{k}가 n 보다 작아지는 상황이 오면 계산이 종료된다고 보면 된다. 또한 각 항의 부호는 +, +, -, – 의 패턴으로 반복된다. 따라서 일반항을 구하는 함수를 다시 써보면 아래와 같이 정리할 수 있다. (역시 동적계획법이지만 연산의 수가 훨씬 적다)

def getP(n):
    signs = (1, 1, -1, -1)
    p = [1] + [0] * n
    for k in range(1, n+1):
        pk = 0 # p[k]의 항이 될 값
        i = 0 # 점화식 내의 부분 수열의 인덱스
        penta = getPenta(i) # gk
        while penta <= k:
            pk += signs[i%4] * p[k-penta]
            i += 1
            penta = getPenta(i)
        p[k] = pk
    return p[-1]

최종장

이제 이 문제의 답 구하는 작업에 다시 도전해보도록 하자. 위의 함수는 n 번까지만 루트를 돌지만 무한루프를 돌면서 조건을 만족할 때까지 100만으로 나눠지는 항이 있는지 찾는다. . 또한 큰 정수 연산에 대한 부담을 줄여서 연산 속도를 빠르게 하기 위해서 p[k] 항에는 100만으로 나눈 나머지만 저장하도록 하겠다.

def main():
    signs = (1, 1, -1, -1)
    p = [1]
    while True:
        k = 1
        pk = 0
        i = 0
        penta = getPenta(i)
        while penta <= k:
            pk += signs[i%4] * p[k-penta]
            i += 1
            penta = getPenta(i)
        pk = pk % 1000000
        if pk == 0:
            print k
            return
        p.append(pk)

 

기대와 달리 엄청 빠르게 답이 나오지 않지만 (대략 10~13초 가량 소요된다) 그럼에도 불구하고 처음 몇 번의 시도에 비해서는 상당한 발전이다.

Fast Fibonacci Transform

빠른 피보나치 항 구하기

피보나치 수열은 0, 1, 1, 2, 3, 5, 8,… 과 같이 앞의 두 항의 합이 그 앞의 항이 되는 수열이다. 피보나츼 수열의 n 항을 구하는 함수는 보통 이렇게 많이 작성한다.

def fib(n):
    if n < 3:
        return (0, 1)[n]
    return fib(n-1) + fib(n-2)

하지만 이 함수는 지극히 비효율적이라

%time fib(35)
Wall time: 7.05 s
Out[7]: 9227465

이런 처참한 성능이 나온다. 이는 한 번 계산했던 값을 계속 재계산하기 때문인데, 이런 문제를 피하기위해서는 메모이제인션이라는 캐싱 기법을 쓴다.

# 메모이제이션을 위한 데코레이터 함수
def memoize(f):
    cache = {}
    def inner(arg):
        if arg in cache:
            return arg
        return cache.setdefault(arg, f(arg))
    return inner

# 메모이제이션을 적용한 피보나치 항 구하기
@memoize
def fib_cached(n):
    if n < 2:
        return (0, 1)[n]
    return fib(n-2) + fib(n-1)


# 그 결과는
%time fib_cached(300)
Wall time: 1 ms
Out[6]: 44552

상당히 준수하다. 하지만 이 방법은 치명적인 약점이 있는데, 그만큼 많은 메모리 공간을 캐시로 쓴다는 점과, 재귀에 기반하기 때문에 처음부터 너무 큰 값을 계산하는 경우 재귀 깊이의 한계에 빠지게 된다. (n = 30,000 일 때를 처음부터 계산할 수 없음)

dp 기법을 이용하는 방법도 있다. 이 역시 메모리를 부가적으로 쓰긴하지만, 캐싱보다도 더 빠르며, 재귀 한계에 대한 위험이 없다.

def fib_dp(n):
    ns = [1, 1] + [0] * (n - 1)
    for i in range(2, n+1):
        ns[i] = ns[i-2] + ns[i-1]
    return ns[n]

# 1000 loops, best of 3: 279 µs per loop

피보나치 수열은 단순히 앞의 두 값을 더한 값이 그 다음항이 되기 때문에 dp 대신 값을 바꿔나가는 방법으로 다음과 같이 구현해도 된다. 이는 추가적인 메모리를 더 쓰지 않는다.

def fib_f(n):
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a

%timeit fib_f(1000)
10000 loops, best of 3: 108 µs per loop

되려 메모이제이션을 쓰는 것보다 빠르다.

하지만 이보다도 더 빠른 방법이 있으니, 그것은 빠른 피보나치 변환을 쓰는 것이다.

def multiply(x, y):
    a, b = x
    c, d = y
    return (a*c + b*d, a*d + b*c + b*d)

def power(x, n):
    if n is 0:
        return (1, 0)
    if n % 2 == 0:
        return power(multiply(x, x), n // 2)
    return multiply(power(multiply(x, x), n // 2), x)

def fib_fast(n):
    return power((1, 1), n)[0]

백만번째 항을 계산하는데, 빠른 피보나치 변환을 계산한 결과는 1.5초 가량이며, 앞에서부터 계산한 결과는 14초가 넘어간다. 거의 10배의 결과인데, 이는 큰 값에서는 빠른 피보나치 변환 알고리즘이 강력함을 발휘한다고 볼 수 있다. 하지만 어느정도 규모 이하의 값에서는 앞에서부터 계산하는 방식이 좀 더 간편하고 빠르게 써먹을 수 있을 것 같다.

오일러 프로젝트 001

오일러 프로젝트 1번

10보다 작은 자연수 중에서 3 또는 5의 배수는 3, 5, 6, 9 이고, 이것을 모두 더하면 23입니다. 1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면 얼마일까요?(http://euler.synap.co.kr/prob_detail.php?id=1) 오일러 프로젝트 001 더보기