[Swift 이코테] DP / Dynamic Programming / 동적 계획법 /

이전에 정리해둔 글이 있지만 이코테 책을 읽고 다시 정리합니다.

[종만북] Dynamic Programming / DP / 동적 계획법

 

---

 

이책에서는 DP의 첫 분단의 제목을 [중복되는 연산을 줄이자]를 메인으로 설명하고 있다.

컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다. 그래서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 다이나믹 프로그래밍의 2가지 방식(탑다운과 보텀업)에 대해 설명을 한다. DP를 위한 메모이제이션 기법도 소개한다.

대표적 예시로는 피보나치 수열이 있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 피보나치 수열은 다음과 같은 형태로 끝없이 이어진다.

1

1

2

3

5

8

13

21

34

55

 

피보나치 점화식

프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 있다. 수열 자체가 여러 개의 수가 규칙에 따라서 배열된 형태를 의미하는 것이기 때문.

다음과 같이 작성할 수 있다.

func fibo(_ x: Int) -> Int {
	if x == 1 || x == 2 {
		return 1
	}
	return fibo(x - 1) + fibo(x - 2)
}

print(fibo(45))

이런식으로 작성하면 수행시간이 기하급수적으로 늘어나기 때문에 심각한 문제가 일어날 수 있다. 현재 이코드의 수행시간은 O(2^N)이다. N이 30이 되면 10억 의 연산을 수행해야한다. 2^45 = 35184372088832이며 이를 수행하기위해 14초가 걸림을 알 수 있다.

피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없다. 이러한 문제는 다이나믹 프로그래밍을 사용하여 효율적으로 해결할 수 있다. 다만 항상 다이나믹 프로그래밍을 사용할 수는 없으며, 다음 조건을 만족할 때 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

피보나치 수열은 이러한 조건을 만족하는 대표 문제이다. 이 문제를 메모이제이션(Memoization) 기법을 사용해서 해결해보자. 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 메모이제이션은 값을 저장하는 방법이므로 캐싱(Caching)이라고도 한다. 

var d = Array(repeating: 0, count: 100)

func fibo(_ x: Int) -> Int {
	if x == 1 || x == 2 {
		return 1
	}
	if d[x] != 0 {
		return d[x]
	}
	d[x] = fibo(x - 1) + fibo(x - 2)
	return d[x]
}

print(fibo(92))

Swift에서는 92가 넘어가면 오버플로우가 나므로 그 이상은 Int 타입으로 사용할 수 없다. 메모이제이션 기법을 통하여 92의 값을 가져오는데도 1.85초 밖에 걸리지 않았음을 확인할 수 있다.

---

여기서 정리하자면 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 다이나믹 프로그래밍은 한 번 해결했던 문제를 다시금 해결한다는 점이 특징이다. 이미 해결된 부분 문제에 대한 답을 저장해 놓고, 이문제는 이미 해결 됐던 것이니까 다시 해결할 필요가 없다고 반환하는 것. 

다이나믹 프로그래밍을 적용했을 때의 피보나치 수열 알고리즘의 시간 복잡도는 어떻게 될까 ? 바로 O(N)이다. 왜냐하면 f(1)을 구한 다음 그 값이 f(2)를 푸는데 사용되고, f(2)의 값이 f(3)을 푸는데 사용되는 방식으로 이어지기 때문에다. 한 번 구한 결과는 다시 구해지지 않는다. 따라서 실제로 호출되는 함수에 대해서만 확인해보면 아래와 같은 답을 얻을 수 있다.

var d = Array(repeating: 0, count: 100)

func fibo(_ x: Int) -> Int {
	print("f(\(x))")
	if x == 1 || x == 2 {
		return 1
	}
	if d[x] != 0 {
		return d[x]
	}
	d[x] = fibo(x - 1) + fibo(x - 2)
	return d[x]
}

print(fibo(6))

이처럼 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 Top Down (탑다운 방식) 이라고 한다. 반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 Bottom Up (보텀업 방식)이라고 한다. 

var d = Array(repeating: 0, count: 100)
d[1] = 1
d[2] = 1

for i in 3...92 {
	d[i] = d[i - 1] + d[i - 2]
}

func fibo(_ x: Int) -> Int {
	return d[x]
}

print(fibo(92))

bottom up 방식을 이용한 피보나치의 코드이다.

탑다운(메모이제이션) 방식은 하향식이라고도 하며, 보텀업 방식은 상향식이라고도 한다. 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다. 보텀업 방식에서 사용되는 결과 저장용 리스트는 DP 테이블이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용하는 표현이다. 다이나믹 프로그래밍과 메모이제이션의 개념을 혼용해서 사용하는 경우도 있는데, 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하므로, 다이나믹 프로그래밍과는 별도의 개념이다. 한 번 계산된 결과를 어딘가에 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다.

---

메모이제이션은 때에 따라서 다른 자료형, 예를 들어 사전(dict) 자료형을 이용할 수도 있다. 사전 자료형은 수열처럼 연속적이지 않은 경우에 유용. 예를들어 an을 계산하고자 할 때 a0~an-1 모두가 아닌 일부의 작은 문제에 대한 해답만 필요한 경우가 존재할 수 있다. 이럴 때는 사전 자료형을 사용하는게 더 효과적이다. 

문제를 푸는 첫 번째 단게는 주어진 문제가 DP 유형임을 파악하는 것이다. 특정한 문제를 완탐 알고리즘으로 접근 했을 때 시간이 매우 오래걸리면 DP를 적용할 수 잇는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자.

재귀로 비효율적인 프로그램을 작성한 뒤 탑다운 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있다면, 즉 메모이제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 아이디어다. 

가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는 것을 권장한다. 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문이다. 실제로 앞에서 제시한 재귀적인 피보나치 수열의 소스코드에서 오천 번째 이상 큰 피보나치 수를 구하도록 하면 'reculsion depth' 재귀 깊이와 관련된 오류가 발생할 수 있다. 

---

Swift에서는 Python의 sys.setrecursionlimit과 같은 직접적인 함수로 재귀 깊이 한계를 설정하는 기능이 없습니다. Swift와 iOS 앱 개발 환경에서는 스택 사이즈에 기반한 재귀 깊이의 한계가 결정됩니다. 이는 하드웨어와 운영 체제, 그리고 앱이 실행되는 특정 조건에 따라 다를 수 있습니다.

Swift 또는 Objective-C로 작성된 iOS 앱에서는 메인 스레드의 스택 사이즈가 일반적으로 1MB 정도로 설정되어 있습니다. 하지만, 별도로 생성된 스레드의 경우 스택 사이즈를 개발자가 지정할 수 있으며, 이는 재귀 함수의 최대 깊이에 영향을 줍니다.

iOS 개발에서 재귀 깊이의 정확한 한계값을 제공하기는 어렵습니다. 이는 실행 중인 코드, 컴파일러의 최적화, 사용하는 하드웨어의 스펙 등 다양한 요소에 의해 영향을 받기 때문입니다. 재귀 호출이 필수적인 경우에는 Tail Call Optimization(TCO)을 고려하는 것도 하나의 방법입니다. Swift 컴파일러는 특정 조건 하에서 꼬리 재귀 최적화를 수행할 수 있으므로, 이를 활용하여 스택 오버플로의 위험을 줄일 수 있습니다.

Tail Call Optimization 은 다음에 추가적으로 자세하게 다룹니다. 

 

[Swift] Tail Call Optimization / TCO