728x90
반응형
이론
이번에 볼 알고리즘은 백트래킹이다. 백트래킹을 알아두면 대부분 해를 찾는데 도움이 될것이다. 백트레킹은 탐색하는 도중 중복되거나 해를 찾는 방향이 맞지 안 맞으면 그 부분을 탐색하지않는다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. 이러면 불필요한 탐색을 할 필요가 없어서 기존 완전 탐색보다 시간적이나 메모리가 단축할수 있다. 자세한것은 아래 사이트에서 확인해보면된다.
https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89
퇴각검색 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 퇴각검색(영어: backtracking, 한국어: 백트래킹)은 한정 조건을 가진 문제를 풀려는 전략이다. "퇴각검색(backtrack)"이란 용어는 1950년대의 미국 수학자 D. H. 레머가
ko.wikipedia.org
728x90
반응형
'알고리즘 > 이론' 카테고리의 다른 글
| [알고리즘 이론] 동적계획법(Dynamic Programming, DP) (0) | 2022.12.14 |
|---|---|
| [알고리즘 이론] 트리(Tree) (0) | 2022.12.13 |
| [알고리즘 이론] 힙(Heap) (0) | 2022.12.07 |
| [알고리즘 이론] 그리디(Greedy) (0) | 2022.11.23 |
| [알고리즘 이론] 구간합, 누적합(prefix sum) (1) | 2022.11.08 |