[Python] 순열과 동적계획법

 

💟 문제 : 입력 길이 n일 때 n 이하의 수에 대해서 모든 순열의 경우를 나열해보시오.

 

def combinations(s):
	if len(s) < 2:
    	return s
    res = []
    for i,c in enumerate(s):
    	res.append(c)
        for j in combinations(s[:i]+s[i+1:1]):
        	res.append(c+j)
    return res

 

코드 분석 :

순열의 문제를 재귀함수로 풀어낸 코드이다.

 

재귀함수하니까 떠오른 것이 동적계획법이기 때문에 동적계획법에 대해 공부하도록 하겠다.

 

동적 계획법 이란 복잡한 문제를 간단한 여러 하위 문제들로 나눠서 푸는 것으로 하위 문제가 서로 종속성을 가질 때 사용된다.

(Divide and Conquer과 매우 유사하다)

동적 계획법은 모든 하위 문제를 풀고 그 결과를 저장해 두면서 다음 단계의 문제를 푸는데 사용한다.

-> 문제를 다시 풀지 않고 table에 저장된 값을 이용하므로 시간복잡도가 줄어든다!

그리고 마지막으로 동적계획법은 모든 경우를 따져 보기 때문에 항상 optimal한 solution을 얻는다.

 

이처럼 동적계획법을 활용하면 더 간단하게 문제를 해결할 수 있다.

그렇다면 동적계획법이 뭔지 더 자세히 알아보겠다!

 

 

동적계획법

앞서 간략하게 설명한 것처럼 동적계획법은 메모리를 적절하게 사용해 수행 시간을 단축시키는 방법이다.

 

동적계획법은 보통 두가지 방식 (탑다운과 보텀업)으로 구현한다.

 

동적계획법은 문제가 아래 조건을 만족할 때 사용할 수 있다.

1. 최적 부분 구조(Optimal Substructure)

: 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제들의 답을 모아 큰 문제를 해결할 수 있다.

2. 중복되는 부분 문제 (Overlapping Subproblem)

: 동일한 작은 문제를 반복적으로 해결해야 한다.

 

(1) 피보나치 수열

 

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

 

n번째 피보나치 수를 f(n)이라고 할때, 4번째 피보나치 수 f(4)를 구하는 과정은 다음과 같다.

f(4) = f(3) + f(2) = f(2) + f(1) + f(2)

 

이러한 점화식은 재귀함수를 이용해 간단하게 풀 수 있다. 이때 수열은 배열이나 리스트를 이용해 표현한다.

def fibo(x):
	if x==1 or x==2:
    	return 1
    return fibo(x-1) + fibo(x-2)

-> 재귀 함수가 무한루프를 돌지 않고 특정 지점에서 멈출 수 있도록 하는 것이 핵심!!

하지만 단순 재귀 함수로 피보나치 수열을 해결하면 지수 시간 복잡도(O(2^n))를 지니게 된다. (중복되는 f값이 여러번 다시 계산될 수 있기 때문)

-> 이 경우 n이 조금만 커지더라도 연산량이 급격하게 증가한다.

-> 따라서 별도의 메모리 공간에 우리가 해결한 f값을 저장해야 중복해서 계산하지 않게 된다.

 

그렇다면 피보나치를 동적계획법을 사용해 풀어보자!!

먼저 동적계획법을 구현하는 방법들을 한번씩 설명하고 넘어가겠다.

 

◎ Memoization

메모이제이션은 동적계획법을 구현하는 방법 중 하나이다.

한번 계산한 결과를 메모리 공간에 메모하기 때문에 같은 문제를 다시 호출할 경우 메모했던 결과를 그대로 가져온다.

 

◎ 탑다운 (하향식)

큰문제를 해결하기 위해 작은 문제들을 재귀적으로 호출하며 (구현 과정에서 재귀함수를 이용한다.) 작은 문제들이 모두 해결되었을 때 실제로 큰 문제에 대한 답까지 얻을 수 있도록 코드를 작성한다. 

이때 메모이제이션 방식을 사용한다.

 

◎ 보텀업 (상향식)

아래쪽에서부터 작은 문제를 하나씩 해결하며 먼저 계산했던 문제들의 값을 활용해 그 다음의 문제들까지 활용한다. 

반복문을 사용해서 구현

 

- 보통 동적계획법으로 많이 활용하는 방식은 보텀업 방식이다.

# 한번 계산한 결과를 메모이제이션 하기 위한 리스트의 초기화
d = [0]*100    # 총 100개의 원소를 가지는 하나의 리스트 초기화

# 탑다운 동적계획법
def fibo(x):
	if x==1 or x==2    # 종료 조건 명시
    	return 1
    if d[x] != 0:
    	return d[x]    # 이미 계산한 적 있는 문제면 그대로 반환
    d[x] = fibo(x-1) + fibo(x-2) # 아직 계산하지 않은 문제라면 점화식에 따라 피보나치 결과 반환
    return d[x]

위 탑다운 코드를 보면 기존의 점화식을 이용해서 문제를 푸는 것은 같지만, d라는 리스트를 생성하면서 메모이제이션을 해준 것을 볼 수 있다!!

# 보텀업 방식의 동적계획법 코드
# 앞서 계산된 결과를 저장하기 위해 DP 테이블 초기화
d = [0]*100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1]=1
d[2]=1

#피보나치 함수 반복문으로 구현
for i in range(3,n+1):
	d[i] = d[i-1]+d[i-2]
    
print(d[n])

보텀업 방식은 재귀함수가 아니라 반복문을 사용하기 때문에 점화식에서 쓰이는 종료조건을 사용하는 것이 아니라, 반복문 시작 전에 먼저 초기화한다. 작은 문제부터 해결한 다음, 그 작은 문제를 조합해 큰 문제들을 차례로 해결해나가는 것을 볼 수 있다.

 

메모이제이션을 이용하는 경우, 피보나치 수열 함수의 시간 복잡도는 O(N)이다.