Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
Tags
- CodeEngn Basic 01
- 리버싱
- 논문리뷰
- 코드엔진
- 디지털 포렌식 트랙
- bob
- 철학
- 코드엔진 베이직
- malware
- CodeEngn Basic 5
- 사회적 사실
- BoB 12기 최종합격 후기
- 에밀 뒤르켐
- h4ckinggame
- BoB 12기
- 코드엔진 basic 5
- Best of the Best
- CodeEngn
- 자살론
- codeengn basic rce 01
- 사회분업론
Archives
- Today
- Total
woonadz :)
[개념정리]백 트래킹_nabi 본문
반응형
기록용
3줄 TMI
알고리즘 스터디 날짜가 조금씩 밀렸다. 이는 내가 나태해지고 있다는 걸 의미하는 것 같아 반성을 하고 있다. 이번주 활동부터는 정말 절대로 미루지 않을 것이다. 나는 약속을 정말 중요하게 생각하는데 활동이 밀리는 걸 보며 회의감이 든다.
백 트래킹이란?
모든 경우의 수를 전부 고려하는 알고리즘.
상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/Heuristic Search)이 있다. -나무위키-
라고 정의되어있긴 하지만 내가 생각하는 정의와는 좀 다르다.
저 정의를 보자마자 가장 먼저 든 생각은 '브루트 포스와의 차이점이 있는 가' 였다.
브루트 포스도 위 백 트래킹 개념과 마찬가지로 모든 경우의 수를 비교하여 답을 찾아내는 알고리즘이다.
하지만 이 둘은 서로 다른 알고리즘 개념이다.
백 트래킹(Backtracing)
백 트래킹을 번역하면 역추적을 의미한다.
이를 프로그래밍에 적용하면 모든 경우의 수를 고려하는 것은 맞지만 가능성이 있는 것에 한해 찾아가는 '가지치기' 기법을 사용하는 알고리즘이다. 즉, 이미 지나쳐 온 노드더라도 다시 돌아가 다른 가능성을 시도해보는 기법이다. 주로 재귀함수로 구현된다.
- 가지치기 : 조건에 맞지 않는 노드는 찾아가지 않음.
이제 위에서 생긴 의문을 해결하겠다.
백 트래킹, 브루트 포스, DFS 의 차이점
백 트래킹 : 가지치기를 통해 불필요한 루트를 제거할 수 있으므로 DFS 알고리즘에 비해 시간을 단출할 수 있다.
브루트 포스 : '깊이'와 '탐색'에 국한된 개념이 아닌 모든 경우의 수를 다 대입해보는 것을 통틀어 브루트 포스라고 부른다.
DFS : 트리의 깊은 곳으로 탐색해가는 완전 탐색 기법 중 하나
반응형
'IT > 자료구조 및 알고리즘' 카테고리의 다른 글
[개념정리] 기본 자료구조 (0) | 2022.01.23 |
---|---|
[개념정리]동적 계획법_nabi (0) | 2021.11.23 |
[개념정리]정수론 및 조합론_nabi (0) | 2021.11.08 |
[개념정리]정렬_nabi (0) | 2021.10.27 |
[개념정리]브루트 포스_nabi (0) | 2021.10.18 |