반응형 백트래킹18 [백준] 15656번 - N과 M(7) (Java) https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 입력받은 배열은 DFS 탐색을 하기전에 오름차순으로 먼저 정렬을 한다. 2. 중복방문을 허용하기 때문에 방문배열은 사용하지 않는다. 3. 순서가 바뀌면 다른 조합으로 인식한다. - for (i = 0 to N)으로 해서 새로운 탐색을 할 때 처음부터 다시 시작한다. import java.util.Scanner; import java.util.Arrays; import java.lan.. 2022. 12. 9. [백준] 15655번 - N과 M(6) (Java) https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 입력받은 숫자를 수열로 출력한다. 2. 중복을 허용하지 않는다. - 방문배열을 사용해서 방문하지 않은 수라면 조합에 사용하고 방문처리한다. - level을 하나 높여서 재귀함수 호출한다. - 재귀 호출에서 돌아오면 방문처리를 리셋한다. 3. 순서가 바뀌어도 동일조합으로 인식한다. - for (i = start to N)으로 사용한다. - DFS(i, level+1)을 한다. impo.. 2022. 12. 9. [백준] 15654번 - N과 M(5) (Java) https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 오름차순으로 출력해야 하기 때문에 입력값을 먼저 정렬해야 한다. 2. 숫자 대신 배열 인덱스를 넘겨주고, 배열 A[i]를 저장한다. 3. 중복 조합을 허용하지 않기 때문에 방문배열을 사용한다. - 방문한 숫자가 아니면 값을 조합한다. - 재귀에서 돌아오면 다음 탐색을 위해 방문처리를 초기화한다. import java.util.Scanner; import java.util.Arrays.. 2022. 12. 9. [백준] 15652번 - N과 M(4) (Java) https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 중복 숫자를 허용한다. - 방문배열 사용X 2. 순서가 바뀌어도 동일 조합으로 본다. - for(i=start to N)으로 하고 재귀호출 때 DFS(i, level+1)을 한다. import java.util.Scanner; import java.lang.StringBuilder; public class Main { static int N, M; static int A[]; static .. 2022. 12. 9. [백준] 9663번 - N-Queen (Java) https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹의 대표 문제이다. 퀸은 상하좌우 대각선으로 거리제한 없이 움직일 수 있다. 그 동선에 걸리지 않도록 다른 퀸을 N개 배치를 하는 경우의 수를 구하는 문제이다. 각 행별로 놓을 수 있는 위치가 발견되면 재귀호출을 해주고, N개 만큼 배치가 되었다면 count+1을 해준다. * 두가지 문제 1. 재귀호출을 어떤 방식으로 할 것인가 2. 퀸을 놓을 수 있는 위치인지 어떻게 판단할 것인가 * 체스판의 퀸을 일차.. 2022. 10. 13. [백준] 15651번 - N과 M(3) (Java) https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 중복숫자와 순열 모두 허용이다. N과 M (1)과 (2)에서 중복을 막기 위해 사용했던 visited[]을 사용 안하면 된다. 다만, 출력을 System.out.print()를 하게 되면 시간초과가 난다. 대신 StringBuilder로 문자열을 계속 머지한다음 마지막 한번 출력했더니 통과했다. import java.util.Scanner; //[백준] 15651번 - N과 M(3) (Java).. 2022. 10. 13. [백준] 15650번 - N과 M(2) (Java) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N과 M(1)과 비슷한데 중복 순열을 허용하지 않는 점이 차이가 닌다. 이전 문제는 중복 숫자만 방문배열을 통해서 처리를 했는데 이 문제에서는 순서가 달라도 중복이면 표시하면 안된다. 예제를 보면, 4 2 ---- 1 2 1 3 1 4 2 3 2 4 3 4 이런 식으로 1로 시작하는 값이 2로 시작하는 순열을 시작할 때 중복체크 락이 걸려있어야 한다. (1)에서는 재귀 호출에서 돌아오면 중복체크.. 2022. 10. 13. [백준] 15649번 - N과M(1) (Java) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 중복되는 수를 제외한 모든 경우의 수를 탐색해야 한다. dfs탐색을 사용한 백트레킹 알고리즘으로 풀자. 백트레킹은 탐색할 노드를 조건문으로 판단하여 유.. 2022. 10. 13. [백준] 1987번 - 알파벳 (Java)(○) https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 1. 세로 R, 가로 C로 된 맵이 있고, 대문자 알파벳으로 채워져 있음. 2. (1, 1)에 말이 있는데 상/하/좌/우로 움직일 수 있음. 그런데 이동한 칸의 알파벳은 이전 위치의 알파벳들과 달라야지 이동이 가능함. 3. 칸을 지날 때 마다 알파벳을 저장하는 배열이 필요하고, 새 알파벳과 비교하는 함수가 필요함. 4. 방문배열도 당연히 필요함. 5. dfs함수 파라미터는 좌표를 넘겨주자... 2022. 9. 2. 이전 1 2 다음 반응형
