알고리즘 응용 - 완전 탐색

순열(nPm) - 서로 다른 n개의 원소 중 m개를 순서를 고려하여 중복 없이 골라낸 것

ex) 6P3

#nPm 구현
#used = num이 이미 사용되었는지 확인하는 리스트
#answer = 현재 조합된 원소들을 저장하는 리스트
answer = [0,0,0] #m개의 정답을 저장
used = [False,False,False,False,False,False] #n개의 원소 사용 여부
m=3
n=6
def permutation(idx):
    global n,m
    if(idx==m):
        print(answer[:m])
        return
    for num in range(n):
        if used[num]:
            continue
        answer[idx] = num
        used[num] = True
        permutation(idx+1)
        used[num] = False
        
permutation(0)

 

조합(nCr) - 서로 다른 n개의 원소 중 r개를 순서 없이 중복을 제외하고 골라낸 것

#nCr 구현
#used = num이 이미 사용되었는지 확인하는 리스트
#answer = 현재 조합된 원소들을 저장하는 리스트
answer = [0,0,0]
used = [False,False,False,False,False,False]
r=3
n=6
def combination(idx,start):
    global n,r
    if idx == r:
        print(answer)
        return
    for i in range(start,n):
        if used[i]:
            continue
        answer[idx] = i
        used[i] = True
        combination(idx+1, i+1)
        used[i] = False
combination(0,0)

중복 조합은 combination(idx+1, i)로 재귀호출을 하면 된다.

 

부분집합

원소 n개를 가지고 만들 수 있는 모든 집합(멱집합)

일반적으로 각 원소마다 r개의 선택지가 있을 때, O(n^r)이라는 매우 큰 수가 된다.

#1~4의 값이 있을 때, 모든 부분집합 만들기
nums = ["1","2","3","4"]
def allCase(idx,answer):
	#기저조건
    if idx == len(nums):
        print(answer)
        return
    #원소를 사용하는 경우
    allCase(idx+1,answer)
    #원소를 사용하지 않는 경우
    allCase(idx+1,answer+nums[idx])
allCase(0,"")
#결과

4
3
34
2
24
23
234
1
14
13
134
12
124
123
1234

 

비트연산

원소의 개수가 약 12개정도 이하일 경우 비트마스킹과 비트연산자를 이용해 최적화할 수 있다.

#nPm 구현
#used = num이 이미 사용되었는지 확인하는 리스트
#answer = 현재 조합된 원소들을 저장하는 비트마스크
answer = [0,0,0] #m개의 정답을 저장
used = 0 #n개의 원소 사용 여부
m=3
n=6
def permutation(idx):
    global n,m,used
    if(idx==m):
        print(answer[:m])
        return
    for num in range(n):
        if (1<<num)&used:
            continue
        answer[idx] = num
        used |= 1<<num
        permutation(idx+1)
        used &= ~(1<<num)
        
permutation(0)

 

 

 

DFS

트리 형태의 자료구조에서 가장 깊은 자식 노드부터 탐색하는 방법

재귀 함수 형태로 구현하는 방법과 stack 자료구조를 활용하는 방법이 있다.

#dfs의 경우 0-1-3-4-2-5 순서로 노드를 방문하면 된다
graph = {0:[1,2],1:[3,4],2:[5],3:[],4:[],5:[]}

def dfs(node):
    print(node)
    for n in graph[node]:
        dfs(n)
        
dfs(0)

stack = [0]
while stack:
    node = stack.pop()
    print(node)
    for n in graph[node][::-1]: #dfs()와 비교를 위해 reverse만 해줌
        stack.append(n)

 

BFS

트리 형태의 자료구조에서 depth 크기 별로 자식 노드들을 탐색하는 방법

queue 자료구조를 활용해 풀 수 있다.

#bfs의 경우 0-1-2-3-4-5 순서로 노드를 방문하면 된다
graph = {0:[1,2],1:[3,4],2:[5],3:[],4:[],5:[]}

queue = [0]
def bfs(queue):
    if not queue:
        return
    node = queue.pop(0)
    print(node)
    for n in graph[node]:
        queue.append(n)
    bfs(queue)
    
bfs(queue)
    
queue=[0]
while queue:
    node = queue.pop(0)
    print(node)
    for n in graph[node]:
        queue.append(n)

 

다만 DFS와 BFS는 문제의 형태에 따라 재귀함수나 자료구조 둘 중 하나를 이용해 표현하기 어려운 경우가 있다. 두 가지 방법을 모두 알아두고 필요에 따라 적용하는 것이 좋다.