백준 156491 [Kotlin, S3] 백준 15649번 N과 M(1) N과 M(1)(15649번)Silver 3#백트래킹 문제 내용 문제 접근백트래킹을 이용해 해결 가능하다.완전탐색으로도 해결할 수 있지만 백트래킹을 쓰는 게 공부에 도움이 될 것 같다. 1부터 n까지의 자연수 중 중복 없이 m개를 고르는 모든 경우를 출력한다.백트래킹의 개념부터 간단하게 이야기하겠다. 백트래킹은 일자로 쭉 내려가다가 정답이 아님이 확실시되면 이전으로 돌아와서 다시 다른 경로로 검색을 시작하는 방법이다.간단하게 사진으로 진행 과정을 봐보자. 처음에는 0 -> 1 -> 3으로 이동하면서 탐색한다. 3에 도달하면 더 깊게 들어갈 수 없기 때문에 부모 노드로 다시 이동해서 다른 경로로 재탐색하는 방식이다. 부모 노드로 돌아가는 방법은 자식까지 dfs로 특정 깊이까지 들어가고 나면 저장하면서 방문.. 2024. 8. 13. 이전 1 다음 728x90 반응형
