백트래킹 (2) 썸네일형 리스트형 [BOJ / Node.js] 15666. N과 M(12) https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N.. [Algorithm] 백트래킹(Backtracking) 백트래킹(Backtracking) ? 백트래킹은 '가능한 모든 방법을 탐색한다'는 기본 아이디어에서 나온다. 브루트 포스 알고리즘과의 차이는 브루트 포스의 경우 모든 경우를 전부 시도해보는 방식이라면, 백트래킹의 경우 탐색을 진행하면서, 조건에 맞지 않는 부분을 제외하며 진행하는데에 차이가 있다. DFS는 현재 지점에서 방문할 곳이 있다면, 재귀 호출을 이용하여 계속 이동하게 되는데, 모든 곳을 방문하기 때문에, 목표지점이 있지 않는 경로에 빠져, 비효율적인 결과를 초래할 수 있다. 그래서 이와 같은 비효율적인 경로를 차단하고 목표지점에 갈 수있는 가능성이 있는 루트를 검사하는 방법이 백트래킹 알고리즘이다. 가지치기를 얼마나 잘하느냐에 따라 시간이 많이 단축이 될 수가 있으니, 반복적인 연습을 통해 조건.. 이전 1 다음