백트래킹(Backtracking)
- 비선형으로 구성된 자료구조의 모든 경우의 수를 전부 고려하여 해를 찾는 도중 막히면 되돌아가서 해를 찾는 기법
- 최적화 문제와 결정 문제를 푸는 방법
- 가지치기(Prunning)를 통해 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 이동하며 가지치기를 얼마나 잘하는지에 따라 효율성이 결정됨
DFS
https://pasongsong.tistory.com/240
[알고리즘] 너비 우선 탐색 BFS Breadth First Search
BFS 너비 우선 탐색 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식 DFS는 깊이 우선 탐색으로 정점의 자식들을 먼저 탐색하는 방식 BFS 방식 : A -> B -> C -> D -> G -> H -> I -> E -> F -> J 한 단계
pasongsong.tistory.com
가능한 모든 경로를 탐색하여 해를 찾고 불필요한 경로 또한 모두 탐색함
백트래킹과 DFS는 많은 데이터 중에서 자신이 원하는 데이터를 찾는 과정인 것은 동일하나 백트래킹은 불필요한 경우의 수는 탐색하지 않고 DFS는 모든 경우의 수를 탐색한다는 차이가 있다.
백준 N과 M
https://www.acmicpc.net/problem/15649
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
백준의 백트래킹 문제로 숫자 1부터 N까지 중복 없이 M개의 요소를 가지는 수열을 출력하는 문제이다.
백트래킹 방법으로 물이 방법을 풀어보면 아래와 같이 풀 수 있음
- 1번째 요소에는 1, 2, 3이 올 수 있음
- 1번째 요소에서 1을 고를 경우
- 2번째 요소에서는 2와 3이 올 수 있음
- 2번째 요소에서 2를 고를 경우
- 3번째 요소에서는 3이 옴
- 2번째 요소에서 3을 고를 경우
- 3번째 요소에는 2가 옴
다음과 같이 백트래킹으로 문제를 해석할 수 있으며 풀이는 아래의 링크에 있음
https://pasongsong.tistory.com/manage/posts/
Tistory
좀 아는 블로거들의 유용한 이야기
www.tistory.com
'자료구조&알고리즘' 카테고리의 다른 글
| [알고리즘] 최소 신장 트리 - 크루스칼 알고리즘 (0) | 2022.12.02 |
|---|---|
| [알고리즘] 최단 경로 - 다익스트라 (0) | 2022.11.21 |
| [알고리즘] 탐욕 알고리즘 Greedy (0) | 2022.11.12 |
| [알고리즘] 깊이 우선 탐색 DFS Depth First Search (0) | 2022.11.07 |
| [알고리즘] 너비 우선 탐색 BFS Breadth First Search (0) | 2022.11.05 |
