알고리즘 문제를 풀면서 이게 뭔 소리야🤔 했던 유형이 두가지가 있었는데,
하나는 이분탐색 그리고 나머지 하나가 백트래킹 이었다!
이분탐색은 지난번에 파라메트릭 서치와 묶어서 포스팅을 했기 때문에 오늘은 백트래킹에 대해 알아보려고 한다😊
🏷 백트래킹
값을 찾는 도중에 값이 아니라면, 되돌아가서 다시 값을 찾아가는 기법이다.
반복문의 횟수까지 줄일 수 있으므로 효율적이고, 불필요한 경로를 사전에 걸러낼 수 있으므로 경우의 수가 줄어든다.
그러나 N! 의 경우의 수를 가진 문제에서 최악의 경우에서는 처리라 불가능할 수도 있다.
이는 가지치기 기법을 사용해 효율성을 조절함으로써 해결할 수 있다!
가지치기란, 유망하지(promising) 않는 노드가 포함된 경로는 더 이상 고려하지 않는 것을 말한다.
어떤 노드의 유망성, 즉 해가 될 만 한지 판단한 후 유망하지 않다고 판단되면 그 노드의 이전(부모)으로 돌아가 다음 자식노드로 간다.
해가 될 가능성이 있는 것을 유망하다라고 하며, 유망하지 않는 노드에 가는 것을 가지치기 한다고 표현한다.
정리하자면 백트래킹이란 모든 가능한 경우의 수 중 특정 조건을 만족하는 경우만 살펴보는 것이다❗️
문제 풀이에서, DFS 등으로 모든 경우를 탐색하는 과정에서 조건문 등을 걸어 답이 될 수 없는 상황을 정의하고,
답이 될 수 없는 상황인 경우 탐색을 중지한 뒤 그 이전으로 돌아가 다른 경우를 탐색하는 방식으로 구현할 수 있다.
📌 DFS와 백트래킹
비슷하다고 생각될 수 있다!
그러나 DFS는 가능한 모든 경로를 탐색하는 것으로, 불필요한 경로를 사전에 차단하지 못하므로 경우의 수를 줄이지 못한다.
🏷 백트래킹 알고리즘 매커니즘
1️⃣ 상태 공간 트리의 깊이 우선 탐색(DFS)를 실시한다.
2️⃣ 각 노드가 유망한지를 점검한다.
3️⃣ 유망하지 않다면, 부모노드로 돌아가 탐색을 계속한다.
🏷 백트래킹 알고리즘 예시
📌 백준 N과 M(1)텍스트
대표적인 백트래킹 알고리즘 예시로는 백준의 N-Queen 과 N과 M 시리즈가 있다.
스윽 보니 N-Queen 문제는 사알짝 어려운 감이 없지 않아 있어서^^ 다음 시간에 따로 문제풀이 포스팅을 작성하기로 하고,
이번에는 N과 M 시리즈의 첫번째 문제를 풀이하도록 하겠다!
from sys import stdin
N, M = list(map(int, stdin.readline().split()))
res = []
def find():
if len(res) == M:
print(' '.join(map(str, res)))
return
for i in range(1, N+1):
if i not in res:
res.append(i)
dfs()
res.pop()
find()🌟문제 풀이🌟
M개의 수열을 저장하기 위한 리스트인res를 선언한다 (재귀함수 사용)
find() 함수
res리스트에 들어간 수열들이M개가 되면 리스트에 들어있는 숫자들을 모두 출력하고 함수를 나온다.for문을 이용하여 1부터 N까지의 숫자들을 모두 확인한다.- 리스트
res안의 중복여부 확인한다. - 중복이 아니라면 숫자
i를 리스트res에 넣는다. - 현재
res=[1]인 상태에서 다음 숫자를 넣기 위한 가지치기를 진행한다. (재귀함수)
➡️ 만약n=4,m=2라면 아과 같은 형태로 진행될 것이다.
s : [1] -> [1,2] -> [1] -> [1,3] -> [1] -> [1,4]
출력 pop(2) 출력 pop(3) 출력
📌 참고 자료
