[알고리즘] 완전검색 : 순열, 조합, 부분집합

완전검색(Exhaustive Search)

가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법으로 "Brute Force"라고도 부르며, 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다. 완전검색에는 순열, 조합, 부분집합이 있다.

완전검색 : 순열

서로 다른 것들 중에서 몇개를 뽑아 한줄로 나열하는 것으로 서로 다른 n개 중에 r개를 택할 때
nPr로 표현한다.
그리고 nPr은 다음과 같은 식이 성립한다.

nPr = n(n-1)(n-2)...(n-r+1)

nPn = n!은 팩토리얼이라 부르고 다음과 같은 식이 성립한다.

n! = n(n-1)(n-2)..2*1

순열 재귀 함수 의사코드

// nPr 일 때 순열 의사코드

numbers[] // 순열 저장 배열
isSelected[] // 인덱스에 해당하는 숫자가 선택 되었는지 저장하는 배열
permutation(cnt) // cnt : 현재까지 선택한 순열의 개수

	// 재귀함수 base case
	if cnt == r // r개 뽑았을 때 순열 생성 완료
    else

    	// 순열 재귀함수 inductive part
    	for i from 1 to r
        	if isSelected[i] == true then continue
            numbers[cnt] <- i
            isSelected[i] <- true
            permutation(cnt+1) // 재귀
            isSelected[i] <- false
        end for

완전검색 : 조합

서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것을 조합(combination)이라고 부른다.
nCr로 표현한다.
nCr을 재귀적으로 표현하면 nCr=n-1Cr-1 + n-1Cr로 표현할 수 있다.

조합 재귀 함수 의사코드

// nCr 일 때 조합 의사코드

numbers[] // n개의 숫자 배열
comb[] // r개의 크기의 배열, 조합이 저장될 배열

// cnt : 현재까지 선택한 순열의 개수
// start : 조합 시도할 원소의 시작 인덱스
combination(cnt, start) 

	// 재귀함수 base case
	if cnt == r // r개 뽑았을 때 조합 생성 완료
    else

    	// 조합 재귀함수 inductive part
    	for i from start to n-1
            comb[cnt] <- numbers[i]
            combination(cnt+1, i+1) // 재귀
        end for

완전검색 : 부분집합

집합에 포함된 원소들을 선택하는 것으로 다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분 집합을 찾는 것이다.

• 부분집합의 수
  집합의 원수가 n개일 때, 공집합을 포함한 부분집합의 개수는 2^n개이다.

부분집합 재귀 함수 의사코드

// nCr 일 때 조합 의사코드

numbers[] // n개의 숫자 배열
isSelected[] // 부분집합에 포함/비포함 여부를 저장한 배열

subSet(cnt) // cnt : 현재까지 처리한 원소 개수

	// 재귀함수 base case
	if cnt == N // 부분집합 완성
    else

    	// 부분집합 재귀함수 inductive part
        isSelected[cnt] <- true
    	subSet(cnt+1)
        isSelected[cnt] <- false
    	subSet(cnt+1)
end subSet()