0. 개요

현재까지 대학교 4년 다니면서 알고리즘을 제대로 공부해본 적이 없었다. 이번에 싸피에 입과하게 되면서 알고리즘에 대한 이론과 실습들을 경험한 지 벌써 2주차가 되었다.

처음에 재귀 함수 배울 때 문제를 플랫(Flat)하게 보아라는 교수님의 말씀이 조금 어려웠는데 이제는 조금 이해가 가는 것 같기도 하다. 어쨌든 그래서 처음으로 재귀 함수를 이용해서 구현해본 알고리즘인 순열과 조합에 대해서 정리해보고자 한다~~

1. 순열

1-1. 순열의 정의와 특성

위키백과(https://ko.wikipedia.org/wiki/순열)에 따르면 순열 또는 치환은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞은 연산이다 라고 말한다.

우리가 보통 순열 기호를 ${}_n{\rm P}_r$로 표현하는데 이 기호는 서로 다른 $n$개의 원소에서 $r$개를 순서에 상관 있게!! 선택하는 것을 말한다. 여기서 $P$는 Permutation의 첫 알파벳이다.

그리고 ${}_n{\rm P}_r$ = $n * (n-1) * (n-2) * ... * (n-r+1)$과 같은 식이 성립하는데 이 요소의 개수는 별로 중요하지 않고 보통 우리가 원하는건 $n$개 중 $r$개를 뽑은 요소들 하나하나가 궁금하다.

재귀 호출을 통해서 순열을 생성하는 방법을 알아보자!

1-2. 순열 알고리즘 (재귀 호출)

numbers[] : 순열 저장 배열
visit[] : 인덱스에 해당하는 숫자가 사용 중인지 저장하는 배열

permutation(cnt)
	if cnt == r
		순열 생성 완료
	else
		for i from 1 to n - 1
			if select[i] == true then continue
			numbers[cnt] = i
			visit[i] = true
			permutation(cnt + 1)
			visit[i] = false
		end for
end permutation()

해당 알고리즘은 다음과 같다.

1. 이미 선택된 원소이면 다음 원소를 탐색한다.
2. 그게 아니라면 배열에 현재 원소를 저장하고, 현재 원소를 사용중이라는 뜻인 true로 표시한다.
3. permutation() 메서드를 다시 호출한다. cnt에 1을 더한 값을 파라미터로 보낸다.
4. 이것을 반복하다보면 cnt가 r이 된다. 이때 원하는 알고리즘을 구현한 후 메서드를 리턴한다.
5. 바깥 메서드로 빠져나온 뒤 사용하지 않는 숫자를 다시 false로 표시해준다.

순열 알고리즘은 순서가 있기 때문에 중복을 방지하기 위해 방문 정보를 저장했다면 빠져나온 후에는 방문 정보를 초기화 시켜주어야 [1, 2, 3], [3, 2, 1]과 같이 순서만 다른 원소를 뽑아낼 수 있다는 것이 key point이다!!

2. 조합(Combination)

2-1. 조합의 정의와 특성

이것도 위키백과(https://ko.wikipedia.org/wiki/조합)에서 퍼왔다! 조합은 서로 다른 $n$개의 원소를 가지는 어떤 집합에서 순서에 상관없이 $r$개의 원소를 선택하는 것이라고 말한다. 기호는 ${}_n{\rm C}_r$로 표현한다.

그럼 재귀 호출을 통해서 조합 알고리즘을 구현해보자.

numbers[] : 조합 저장 배열

combination(cnt, start)
	if cnt == r
		조합 생성 완료
	else
		for i from start to n - 1
			numbers[cnt] = i
			comb(cnt + 1, i + 1);
		end for
end combination()

해당 알고리즘은 다음과 같다

1. numbers에 현재 원소를 저장한다.
2. combination() 메서드를 다시 호출한다. 이 때 파라미터로 cnt에 1을 더해준 값과 i에 1을 더한 값을 보내 현재 배열에 저장된 원소 개수와 인덱스 정보를 넘겨준다.
3. 이것을 반복하다보면 cnt가 r이 된다. 이때 원하는 알고리즘을 구현한 후 메서드를 리턴한다.

조합 알고리즘은 순열 알고리즘에 비해 훨씬 간단하다! 왜냐하면 순서가 없기 때문에 인덱스와 현재 저장된 원소의 개수만 관리해주면 되기 때문이다 ㅎㅎ,, (이렇게 하면 중복 방지도 된다)

3. 고찰

재귀 호출은 내부적으로 어떻게 돌아가는지 코드로 쉽게 알아보기가 힘들어서 사실 나한테 너무 어려웠다. 그래도 이렇게 한번 글로 정리를 해보니까 조금이나마 이해에 도움이 된 것 같기는 하다. 아직도 재귀 함수를 사용하기 위해서 문제를 플랫하게 보는 시야는 좁지만 싸피를 진행하면서 열심히 알고리즘 스터디도 참여하고 또 지금처럼 개인적으로 정리를 하다보면 언젠간 알고리즘의 신이 될 수 있지 않을까,,??