백트래킹이란?
백트래킹이란 원하는 값을 찾는 도중 현재 대상이 원하는 값이 아닐때, 더 이상 그 대상을 탐색하지 않고 전 단계로 돌아가서 원하는 값을 푸는 방식이다. 우리가 가장 많이 사용하는 방식인 DFS, BFS가 바로 백트래킹에 속한다고 한다.
DFS, BFS가 바로 백트래킹에 속한다고 한다.
사실 이 말은 매우 불친절한 말이다. 백트래킹이 무엇인가에 대해 의문점이 생겨서 많은 게시글들을 참고하고 여기저기를 뒤져본 결과 나름 내가 내려본 결론은 백트래킹은 DFS 나 BFS에서 조건문을 통해 우리가 찾고자 하는 값이 절대 아닌 것들은 탐색하지 않고 우리가 찾고자 하는 값이 있는 것들만을 탐색하여 우리가 원하는 값을 찾는 방식이라고 생각한다.
이해를 돕기위한 예로 유명한 백트래킹 문제를 가져와 보겠다.
백준 9663번: N-Queen
9663번: N-Queen - Kotlin (백트래킹)
9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 N-Q
everyday-develop-myself.tistory.com
이런 백트래킹 방식을 이용한 것들로는 순열과 조합이 있다.
순열 (Permutation) & 조합 (Combination)
순열이란? 수학에서 순열(Permutation) 또는 치환은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 즉, 순열은 정의역과 공역이 같은 일대일 대응이다. n개의 원소의 순서를 뒤섞는 순
everyday-develop-myself.tistory.com
알고리즘 문제들을 점점 풀어가면서 느끼는 점은 하나만 알아서는 절대 많은 문제를 해결하지 못한다는 것이다. 알고리즘은 서로서로 연결되어 있고 서로를 변형하거나 발전시킨 방식임으로 한 방식만을 추구하지 말고 최대한 여러가지 방식을 전부 배워서 잘 응용한다면 많은 알고리즘 문제들을 해결할 수 있을 것이다.
'개발자의 기본 소양 > ALGORITHM' 카테고리의 다른 글
| Euclidean algorithm (유클리드 호제법) (0) | 2023.03.03 |
|---|---|
| Knapsack Problem (배낭 문제) with 12865번: 평범한 배낭 (0) | 2023.02.26 |
| Floyd-Warshall Algirithm (플로이드 워셜 알고리즘) (0) | 2023.02.23 |
| Dijkstra Algorithm (다익스트라 알고리즘) with 프로그래머스 - 배달 (0) | 2023.02.23 |
| Brute Force (완전탐색) (0) | 2023.02.13 |
