바구니에 있는 여러 개의 공을 꺼내는 순서의 조합을 찾는 것은 대표적인 순열 문제입니다. 그리고 확률과 통계를 얘기할 때도 순열 문제는 자주 등장합니다.
바구니에서 공을 꺼내는 문제에서는 바구니에 남아있는 공과 꺼낸 공의 조합이 경험정보입니다. 이러한 경험 정보를 스택을 이용하여 동적 알고리즘으로 해결하면 어렵지 않게 문제를 해결할 수 있습니다.
다음은 이처럼 여러 단계로 나누어 문제를 해결하고 이전 단계에서 다음 단계로 진행할 수 있는 모든 경우의 수를 경험하는 방법으로 해결하는 동적 프로그래밍의 의사 코드입니다.
초기 경험 정보를 생성
스택에 보관
반복(스택이 비어 있지 않다면)
스택에서 경험 정보 꺼내옮
스택에서 꺼내온 경험 정보에서 다음 경험 목록 조사
반복(다음 경험 목록을 순차적으로 반복)
목적에 도달하면
솔루션에 추가
그렇지 않다면
스택에 보관
하지만 순열 문제에서 모든 경험을 수행해야 하기 때문에 단계가 많고 현재 단계에서 다음 단계로 진행할 수 있는 가지 수가 많을 때 수행 속도가 무리하게 커질 수 있는 문제점도 갖고 있습니다.
여기에서 구현할 예는 바구니에 서로 다른 숫자가 써 있는 공이 있을 때 n개의 공을 하나씩 꺼내는 예로 할게요. 이 때 꺼낸 순서를 포함하여 나올 수 있는 모든 경우를 조사하기로 합시다.
먼저 바구니에는 0부터 9까지 숫자가 쓰여있는 공이 있습니다. 그리고 이 상태에서 발생할 수 있는 다음 상태는 0번 공을 꺼냈을 때부터 9번 공을 꺼냈을 때까지 10가지 경우가 발생합니다. 만약 0번 공을 꺼냈다면 바구니에는 1에서 9번 공이 들어있겠죠. 이렇게 초기 상태에서 발생할 수 있는 10개의 다음 상태를 스택에 보관합니다.
다음은 바구니 순열 문제의 의사 코드입니다.
0~9까지 공을 보관한 초기 경험 정보를 생성
스택에 보관
반복(스택이 비어 있지 않다면)
스택에서 경험 정보 꺼내옮
스택에서 꺼내온 경험 정보에서 다음 경험(공을 하나 더 꺼내는) 목록 조사
반복(다음 경험 목록을 순차적으로 반복)
바구니에 공이 비면
결과 출력
그렇지 않다면
스택에 보관
이러한 동적 프로그래밍에서는 경험 정보를 설계하는 것이 제일 중요합니다. 참고로 동적 프로그래밍에서 경험 정보를 Heuristic 정보라고 부릅니다.