지구정복

https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net -문제해설 dfs를 이용해야 하고 방문함수를 사용해서 이전 깊이에서 방문한 수는 건너뛰도록 해야한다. 그리고 다시 이전 깊이로 돌아오면(백트래킹) 방문함수를 다시 미방문 처리해줘야 한다. n과 m(1) 문제와 비슷하니 참고..! 다른 점은 사용될 숫자를 입력받고 정렬을 해야 된다는 점이다. -자바 package bruteforce; import java.io.BufferedReader; ..

https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net -문제해설 1. n, m, arr, sb는 모두 전역변수, n과 m을 입력받는다. 2. dfs메소드 호출. dfs 매개변수는 arr배열에 어느 수부터 저장할 지를 나타내는 start와 dfs메서드의 재귀호출한 횟수(깊이)를 나타내는 depth가 있다. 3. dfs메소드 내부에는 depth == m일 경우 arr배열에 담겨있는 값들을 sb에 append시키고 메서드를 return시켜서 이전 dfs..

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net -문제해설 1부터 n까지의 숫자 중에서 m 길이만큼의 수열을 만드는데 오름차순이고 중복되는 숫자가 와도 되는 문제이다. n과 m이 4 4 인 경우 1 1 1 1 1 1 1 2 1 1 1 3 1 1 1 4 1 1 2 1 . . . 4 4 3 4 4 4 4 1 4 4 4 2 4 4 4 3 4 4 4 4 를 출력하면 된다. n=4, m=2라고 가정하자. 1. n과 m을 입력받고 수열을 담을 arr을 ..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net -문제해설 DFS를 이용해서 백트래킹을 구현하면 쉽게 풀 수 있는 문제이다. 처음에 이해가 어려운데 알고보면 간단하다. 예시와 같이 n=4, m=4라고 해보자. 1. n, m 입력받고 출력값을 담을 배열 arr, dfs의 방문처리를 위한 배열 visit를 전역변수로 선언하고 main메서드 안에서 초기화해준다. 2. dfs함수 호출 dfs( n, m, depth ) depth가 m이면, 즉 4이면..