목록백트래킹 (6)

Kangho_Story

[백준] 30242번 N-Queen (Easy) C++ 풀이

알고리즘 분류백트래킹문제 설명N-Queen 문제는 크기가 N×N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법 한 가지를 출력하는 것은 쉽다.이 문제에서는 몇 개의 퀸이 이미 놓여있을 때, 퀸을 놓는 방법 한 가지를 출력해 보자.입력 설명첫 번째 줄에 정수 N이 주어진다. (1≤N≤20)두 번째 줄에 정수 Q1, Q2, Q3,...,QN이 주어진다. Qi는 i번째 행에 있는 퀸의 열의 번호를 의미한다. (0≤Qi≤N)만약 Qi가 0이라면 i번째 행에는 퀸이 놓여있지 않다는 뜻이다.퀸이 서로 공격하는 올바르지 않은 상태의 입력 혹은 N개의 퀸이 모두 놓여있는 경우의 입력은 없다.출력 설명첫 번째 줄에 정수 A1, A2, A3, ⋯를 출력한다. Ai는 i번..
PS 2024. 10. 23. 16:46
[백준] 9663번 N-Queen C++ 풀이

알고리즘 분류브루트포스백트래킹문제 설명N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.입력 설명첫째 줄에 N이 주어진다. (1 ≤ N 출력 설명첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.예제 입력8예제 출력92아이디어실제로 배열에 퀸의 위치를 기록하지 않고퀸이 놓여있는 열과 퀸이 놓여있는 좌표만 기록한다.그리고 하나의 행과 열에는 무조건 퀸이 한 개만 존재할 수 있으므로0행부터 n-1행까지 재귀적으로 내려가면서 같은 행과 같은 열 그리고 대각선 경로에 겹치는 퀸이 없는 자리에만 다음 퀸을 놓는다.모든 행에 겹치지 않게 퀸을 하나씩 놓았다면 경우의 수를 1 ..
PS 2024. 10. 22. 13:16
[백준] N과 M (12) C++ 풀이

알고리즘 분류백트래킹문제 설명N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.N개의 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.고른 수열은 비내림차순이어야 한다.길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.입력 설명첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.출력 설명한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력..
PS 2024. 9. 20. 10:14
[백준] 15663번 N과 M c++ 풀이

알고리즘 분류백트래킹문제 설명N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.N개의 자연수 중에서 M개를 고른 수열입력 설명첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.출력 설명한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다.예제 입력3 14 4 24 29 7 9 14 41 1 1 1예제 출력241 71 97 17 99 19 79 91 1 1 1아이디어백트래킹을 이용해서 푸는데 중복..
PS 2024. 9. 19. 11:33
[백준] 15654번 N과 M (5) C++ 풀이

알고리즘 분류백트래킹문제 설명N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.N개의 자연수 중에서 M개를 고른 수열입력 설명첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.출력 설명한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다.예제 입력3 14 5 24 29 8 7 14 41231 1232 1233 1234예제 출력2451 71 81 97 17 87..
PS 2024. 9. 13. 11:16
[백준] 15650번 N과 M (2) C++ 풀이

알고리즘 분류백트래킹문제 설명자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열고른 수열은 오름차순이어야 한다.입력 설명첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)출력 설명한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다.예제 입력3 14 24 4예제 출력1231 21 31 42 32 43 4 1 2 3 4아이디어1~n까지 벡터에 push 하면서 재귀적으로 들어가다가 만약 벡터의 길이가 m과 같아지면 해당 벡터를 출력하고리턴하고..
PS 2024. 9. 9. 13:22
Prev 1 Next