백트래킹(Backtracking) ?
백트래킹은 '가능한 모든 방법을 탐색한다'는 기본 아이디어에서 나온다. 브루트 포스 알고리즘과의 차이는 브루트 포스의 경우 모든 경우를 전부 시도해보는 방식이라면, 백트래킹의 경우 탐색을 진행하면서, 조건에 맞지 않는 부분을 제외하며 진행하는데에 차이가 있다.
DFS는 현재 지점에서 방문할 곳이 있다면, 재귀 호출을 이용하여 계속 이동하게 되는데, 모든 곳을 방문하기 때문에, 목표지점이 있지 않는 경로에 빠져, 비효율적인 결과를 초래할 수 있다. 그래서 이와 같은 비효율적인 경로를 차단하고 목표지점에 갈 수있는 가능성이 있는 루트를 검사하는 방법이 백트래킹 알고리즘이다.
가지치기를 얼마나 잘하느냐에 따라 시간이 많이 단축이 될 수가 있으니, 반복적인 연습을 통해 조건을 잘 설정해주어, 효율적인 알고리즘을 작성하는 훈련이 필요하다.
연습을 위한 백트래킹 문제
https://www.acmicpc.net/problem/15649
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
https://www.acmicpc.net/problem/14888
14888번: 연산자 끼워넣기
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수,
www.acmicpc.net
'Algorithm > Algorithm' 카테고리의 다른 글
| [Algorithm] Big-O 관점에서의 배열과 객체 (0) | 2023.02.13 |
|---|---|
| [Algorithm] Big-O-Notation (0) | 2023.02.12 |
| [Algorithm] 동적 계획법(Dynamic Programming) (0) | 2022.01.10 |
| [Algorithm] 유클리드 호제법 (0) | 2021.12.27 |
| [Algorithm] 에라토스테네스의 체 (0) | 2021.12.27 |