수학에서, 수열(數列) 또는 열(列, sequence)은 수 또는 다른 대상의 순서 있는 나열이다. 나열 순서를 생각해야 하고 중복이 허용된다는 점에서 집합과 구분된다. ... 수열은 자연수의 집합에 정의된 함수라고 할 수 있다.
백트래킹에 대해서 제대로 짚고 넘어가지 않으면 더이상 풀수 없을 거 같고, 이해도 안 될거 같아서 공부를 먼저 시작하고 백준 풀이에 들어가기로 했다.
📄참고하며 공부한 사이트 : https://blog.encrypted.gg/945
[실전 알고리즘] 0x0C강 - 백트래킹
이번에는 백트래킹을 배워보도록 하겠습니다. 백트래킹도 재귀와 더불어 많은 사람들이 고통을 호소하는 알고리즘 중 하나이지만 의외로 그 재귀적인 구조에 매료되어서 참재미를 알아버리는
blog.encrypted.gg
- 백트래킹이란? 문제를 풀 때 최적의 경로를 아는 경우엔 그 경로대로 진행을 하면 문제가 없지만 최적의 경로를 모두가 쉽게 알 수 있을 수는 없다. 이때 주어진 문제의 답을 구하기 위해 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘을 백트래킹(BackTracking)이라고 한다.
📄참고하며 공부한 사이트 : https://youtu.be/HRwFgtiqHH0
- 백트래킹과 DFS는 비슷하지만 다르다.
- 백트래킹은 : 불필요한 탐색을 하지 않고, 이전 단계로 돌아와 다른 후보해를 탐색해 나가는 방법이다.
- DFS는(깊이 우선 탐색 DFS(Depth-First Search)):완전 탐색을 기본으로 하는 그래프 순회 기법으로,모든 노드를 방문하는 것을 목표로 한다. 이때, DFS는 자원 소모가 굉장히 심하기 때문에 어떤 제약 조건에 맞는 해답을 차기 위해서 DFS와 백트래킹 기법을 혼용해서 사용한다.
📌출처: https://gamedevlog.tistory.com/49
- 이 사진을 간단한 예시로 들어보자면 AIR라는 단어를 찾기 위해서 A -> N으로 갔을 때 맞지 않아서 다시 A로 돌아가고 또 A -> I -> M이 아닐 때 다시 I로 BackTrack한뒤 I -> R로간다.
- DFS를 수행하며 모든 노드를 방문하는 것은 자원 낭비이기 때문에 다 돌지 않고 가지치기(Pruning)를 통해서 적합하지 않은 부분을 제거해준다.
이것이 전체적인 DFS와 백트래킹에 대한 개괄이다.
<백트래킹에 관련된 것들>
- 상태공간트리 (State Space Tree)
- 상태 공간: 해답을 탐색하기 위한 탐색 공간
- 상태공간트리: 탐색 공간을 트리 형태의 구조로 암묵적으로 해석 이때, 우리는 트리의 순회를 알아야 한다. 상태공간 트리는 preorder로 진행이 되며 루트 -> left -> right 순으로 진행된다.
전위 순회(preorder): F, B, A, D, C, E, G, I, H (root, left, right)
중위 순회(inorder): A, B, C, D, E, F, G, H, I (left, root, right)
후위 순회(postorder): A, C, E, D, B, H, I, G, F (left, right, root)
레벨 순서 순회: F, B, G, A, D, I, C, E, H
📌출처:
https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C
<백트래킹 기법>
- 상태공간트리를 깊이우선탐색(DFS)로 탐색한다.
- 방문중인 노드에서 더 하위 노드로 가면 해답이 없을 경우(=>해당 노드의 하위 트리를 방문하지 않고 부모 노드로 되돌아 간다.(backtrack))
<유망함(promising)>
- 방문 중인 노드에서 하위 노드가 해답을 발견할 가능성이 있으면 유망하다고 본다. (promising)
- 하위 노드에서 해답을 발견할 가능성이 없으면 유망하지 않다고 본다. (nonpromising)
<백트래킹과 가지치기(Pruning)>
- 백드래킹: 상태공간트리를 DFS로 탐색
- 방문 중인 노드가 유망한지 체크
- 만약 유망하지 않으면, 부모 노드로 되돌아감(Backtrack)
<가지치기(pruning)>
- 유망하지 않으면 하위 트리를 가지치기함
- 가지치기한 상태: 방문한 노드의 방문하지 않은 하위 트리(Pruned state)
https://www.acmicpc.net/problem/15649
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
N, M = map(int, input().split())
visited = [False] * N # 탐사 여부 check
out = [] # 출력 내용
def solve(depth, N, M):
if depth == M:
print(' '.join(map(str, out)))
return
for i in range(len(visited)):
if not visited[i]:
visited[i] = True
out.append(i+1)
solve(depth+1, N, M)
visited[i] = False
out.pop()
solve(0, N, M)📌출처: https://wlstyql.tistory.com/56
백트래킹에 대한 기본 지식이 없어 코드를 보며 무작정 이해를 하려 했다. 오늘의 내가 못하면 내일의 나라도 할 수 있을 거란 생각으로 오늘 이렇게 들여다 보고 내일도 들여다 볼 예정이다.
n,m = list(map(int,input().split())) #1
s = [] #2
def dfs():
if len(s)==m: #3
print(' '.join(map(str,s))) #3
return
for i in range(1,n+1): #4
if i not in s: #5
s.append(i) #6
dfs() #7
s.pop() #8
dfs()📌출처: https://jiwon-coding.tistory.com/21
#1. 1부터 N까지의 수를 중복 없이 M개를 고른다.
#2. 빈 리스트 선언을 하여 여기에 1~N까지의 수를 M개 담을 공간을 마련해준다.
#3. dfs라는 이름의 함수를 선언해주고 리스트의 길이가 M개일 때 M개 만큼 골라준 것이기 때문에 리스트에 담겨있는 요소를 출력시켜준다. (이때 M개를 고른 것이 아니라면 if 문은 무시하고 아래 for문 진행이 된다.)
#4. 1부터 n까지의 수를 고르기 위한 것 (1, n+1)이 범위인 이유는 0부터 시작이 기본인데 1부터 진행을 하니까 n+1이 된다.
#5. 중복이 아니라면 s에 넣어준다.
#6, 7, 8 현재 s=[1]인 상태에서 다음숫자를 넣기위하여 가지치기하기(재귀함수)
-> 만약 n=4, m=2라면 밑과 같은 형태로 진행될 것이다.
s : [1] -> [1,2] -> [1] -> [1,3] -> [1] -> [1,4]
출력 pop(2) 출력 pop(3) 출력