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
- 알고리즘
- 리액트
- 싸피12기
- 부울경캠퍼스
- 스프링
- ssafy job fair
- Lombok
- viroreact
- viro
- MySQL
- Security
- React Native CLI
- 스프링부트
- react
- Spring
- 회원가입
- IntelliJ
- 싸피
- SSAFY
- connetion refused
- viro-community
- maven
- 싸피셜
- SSAFY 11기
- 백준
- springboot
- SSAFYcial
- ssafy 12기
- boj
- arduino uno wifi rev2
Archives
- Today
- Total
목록2024/03/04 (1)
log
[백트래킹] 정의 및 활용 예시
🔎 백트래킹이란? 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법 → 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아간다 == 가지치기 (가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다!) 백트래킹 기법의 유망성 판단 어떤 값이(어떤 노드가) 해가 될 가능성이 있다면 유망하다고 하며, 유망하지 않은 값에 가지 않는 것을 가지치기라고 한다. 유망하지 않다고 판단되면 그 값의 이전으로 돌아가 다음 값으로 넘어간다. (이전 노드로 돌아가 다음 자식 노드로 간다.) 🔎 DFS vs 백트래킹 vs 분기한정법 DFS 가능한 모든 경로를 깊이 우선으로 탐색하는 것 (한 방향으로 갈 수 있는 경로를 먼저 탐색) → 현재 정점과 인접한 간선들을 모두 검사하여 아직 ..
Algorithm
2024. 3. 4. 23:35