1. 알고리즘 관련 공부
이번 주는 공부했던 알고리즘 지식을 정리하려 한다.
예제) 중복 순열 구하기(DFS)
1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열 하는 방법을 모두 출력합니다.
▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.
▣ 출력설명
첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다. 출력순서는 사전순으로 오름차순으로 출력합니다.
▣ 입력예제
1 32
▣ 출력예제
1 11
12
13
21 22 23 31 32 33 9
해설)
중복 순열, 순열도 결국 DFS로 풀 수 있다. 여기서는 중복이 허락되기 때문에 방문 리스트를 만들이 않고 해결이 가능하다. 다만 부분집합의 경우 상태 트리를 이진 트리로 구성이 가능하였지만 여기서는 3개 이상의 노드를 자식으로 두는 상태 트리를 작성해야한다. dfs함수를 기준으로 보자면 dfs(0)에서 dfs(1) 즉 1을 선택하는 경우, dfs(2) 즉 2를 선택하는 경우, dfs(3) 즉, 3을 선택하는 경우 이렇게 3가지의 상태 노드들이 만들어진다. 이는 곧 dfs()함수의 else: 파트에서 3개의 dfs()함수를 정의하는 것이 필요하다. 여기서는 결국 선택할 것이 2개가 되므로 크기가 2인 리스트를 출발점에서 생성해 선택할 가지들을 타고 원소들을 정해주어야한다. 다행히 파이썬에서 리스트는 글로벌 선언을 안 해도 된다. res 리스트에서 i를 인덱스로 받아 내려갈 삾을 넣어준다.
import sys
sys.stdin=open("input.txt","r")
# 부분집합은 이진트리로 DFS를 사용하여 판별했지만
# 중복 순열(중복을 허락하여 n번 뽑아 나열한다.)은 여러 가닥으로 dfs가 뻗어 나간다.
# dfs(0) -> dfs(1), dfs(2),dfs(3) 세 가닥으로 뻗어야한다.
# res라는 리스트를 생성해서 i를 인덱스로 받아서 내려갈 값을 넣어준다.
def DFS(l):
global cnt # 글로벌 선언
if l==m: # 하나의 중복 순열 완성 level이 끝에 다다를 때
for i in res:
print(i,end=" ")
print()
cnt+=1
else:
for i in range(1,n+1): # 1부터 3까지
res[l] = i # l레벨에서 1을 넣을건가 2를 넣을 건가 3을 넣을건가
DFS(l+1)
if __name__ == "__main__":
n,m = map(int, input().split())
res=[0]*m # m의 크기를 가진 중복순열을 담을 리스트
cnt = 0
DFS(0)
print(cnt)
예제) 순열 구하기(DFS)
1부터N까지번호가적힌구슬이있습니다.이중 M개를뽑아일렬로나열하는방법을모두 출력합니다.
▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.
▣ 출력설명
첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다. 출력순서는 사전순으로 오름차순으로 출력합니다.
▣ 입력예제
1 32
▣ 출력예제
1 12
13
21
23 31 32 6
해설)
순열은 기본적으로 위에서 했던 중복 허용 순열에서 체크리스트를 통해 백트래킹을 실시하는 DFS라 보면 된다. 여기서 핵심은 방문하지 않은 노드를 방문할 때 체크리스트에 방문하고 함수를 호출 후 다시 방문을 안 했다고 마킹을 하는 것이다. 사실 이러면 스택처럼 방문을 풀기전에 호출한 함수로 인해 마트료시카 인형과 같이 위 아래 사이에 함수들의 집합이 끼어있을 수 있다. 이러면 방문 체크 - 함수 - 방문 미체크로 백트래킹이 가능하다. 백트래킹 기법을 자세히 알아두자
import sys
sys.stdin=open("input.txt","r")
# 중복 불가면 체크리스트를 사용하자. 핵심!
# 순열 -> 체크리스트를 사용하는 DFS 문제
def DFS(l):
global cnt
# 호출이 들어오면 맨 처음 보는 곳
if l == m:
for i in lst: # 두 수
print(i,end=" ")
print()
cnt+=1
else:
for i in range(1,n+1):
if check[i] == 0:
# 호출 전
# 작업을 하고 호출이 일어난 것
check[i] = 1
lst[l] = i
# 호출, 스택이 쌓이는 것을 생각하자
DFS(l+1) # 체크가 안 되어 있으면 아래로 내려가라
# 호출 아래에 있는 것은 위쪽과 대칭이어야한다.
# 호출이 끝나고 되돌아온 것
# 스택으로 생각하자
# 호출의 밑 지접은 호출이 끝나고 백하고 돌아온 곳
# 트리의 아래 노드에서 다시 온 거다
check[i]=0
