내 맴

문제 ) https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net [ 풀이 ] Backtracking Algorithm을 사용하여 문제를 풀어주었다 - Backtracking Algorithm 이란? ✔ 해를 찾는도중에 해가 아니면 되돌아가서 다시 해를 찾는 기법 ✔ DFS (깊이 우선 탐색 ) 으로 모든 Node를 검색한뒤 Node의 유망성을 점검하여 유망하지않으면 부모노드로 돌아간 후 다른 자손 노드를 탐색한다 - Node가 Promising한지 ..

- Backtracking Algorithm ✔ 해를 찾는도중에 해가 아니면 되돌아가서 다시 해를 찾는 기법 ✔ 모든 경우의 수를 전부 고려한다 ( 브루트 포스 Algorithm과 유사) ✔ 최적화(optimization) 문제와 결정(decision) 문제 ( yes or no question) 를 해결할수있다. ✔ DFS (깊이 우선 탐색 ) 으로 모든 Node를 검색한뒤 Node의 유망성을 점검하여 유망하지않으면 부모노드로 돌아간 후 다른 자손 노드를 탐색한다 - 순서 1. State Space Tree에서 DFS를 실시한다 2. 각 Node가 promising한 지 점검 3. If Node가 promising한 경우 → 자손 Node 탐색 Else non promising한 경우 → 부모 Node..