Coding World

백트랙킹 : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법. DFS와 백트랙킹의 차이? - DFS : DFS는 가능한 모든 경로(후보)를 탐색합니다. 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 해동이 없으므로 경우의 수를 줄이지 못한다. - 백트랙킹 : 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아 가는 것 . 코딩에서 쓸데없는 반복문의 횟수를 줄일 수 있으므로 효율적이다. 이러한 로직을 "가지치기"라고하며 불필요한 부분을 쳐내고 올바른 쪽으로 향한다는 의미이다. 만약 N!의 경우의 수를 가진 문제에서 최악의 경우 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있다. 즉 백트랙킹은 모든 가능한 경우의..

* '박트리'님의 알고리즘 공부 포스트를 참조하였습니다. 알고리즘 공부, 어떻게 해야하나요? 오랜만에 정상적인 포스팅을 쓴다. 메일로 가장 많이 물어 보는 질문들이 [알고리즘 공부 어떻게 해야하나요? 어떻게 하셨어요? 뭘 공부해야 할 지 모르겠어요.] 와 같은 질문들이다. 위 질문에 baactree.tistory.com - PS 실력을 올리기 위해 갖춰야 할 기본 요소 1. 구현력 2. 문제해결능력 3. 배경지식 - PS 을 위해 요구되는 배경지식들 1. 코딩 문법 2. 시,공간 복잡도 분석 3. 배열 4. 트리 5. 그래프 6. BST(Binary Search Tree, 이진 탐색 트리) 7. DFS, BFS 8. 백트래킹 9. DP(Dynamic Programming) 10. 분할정복 11. 최단거리..