겜돌이의 개발일지

개요 N-queens 문제는 N * N 체스판에 N개의 퀸을 서로 공격받지 않게 놓는 방법의 개수를 구하는 문제이다. 예시 n = 4일 때 정답의 개수를 구해보자. 먼저 각 열에는 한 개의 퀸을 놓을 수 있다. 무작정으로 놓을 수 있는 모든 경우에 수를 고려하면 다음과 같다. 총 4 * 4 * 4 * 4 = 256가지의 경우에 대해 놓을 수 있는지 각각 검사해야 한다. 하지만 (2, 1)에 퀸을 놓는 순간 조건을 만족하지 않으므로 이후 자식 노드들은 검사하지 않아도 된다. 따라서 백트래킹을 활용하면 검사해야 하는 가짓 수를 줄일 수 있다. 스도우 코드 상태공간트리 예제 코드(C++) n을 입력받아 n * n 체스판에서 n개의 퀸을 놓을 수 있는 총 방법의 개수를 출력하는 코드 1 2 3 4 5 6 7 8..

문제 백준 15654 N과 M (5) C++ 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 풀이 n과 m (1)에서 출력값이 1 ~ n 이었다면 n과 m (5)는 사용자 입력을 받아 출력을 해야한다. 알고리즘이 바뀌는 건 없다. 백트래킹을 사용하여 순열을 출력하면 된다. 단 출력 시에는 1 ~ n을 출력하는 것이 아니라 사용자 입력을 받아 오름차순으로 정리한 vector를 출력한다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ..

문제 백준 2023 신기한 소수 C++ 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 풀이 백트래킹을 활용합니다. 1. 0자리부터 시작합니다. 2. 현재 숫자에 1~9까지 숫자를 뒤에 붙여가며 소수인지 판별합니다. 2-1. 소수라면 dfs를 재귀호출 합니다. 이 때 수와 자리수를 갱신해줍니다. 3. 현재 수가 N자리 이면 수를 출력하고 함수를 종료합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28..

문제 백준 1038 감소하는 수 C++ 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 풀이 감소하는 수의 순서는 다음과 같습니다. 한 자리 : 0 (0번째) -> 1 (1번째) ~ ... ~ 9 (9번째) 두 자리 : 10 -> 20 -> 21 -> 30 -> 31 -> 32 -> ... -> 98 세 자리 : 210 > 310 -> 320 -> 321 -> ... -> 987 네 자리 : 3210 -> ... -> 9876 ... 열 자리 : 9876543210 각 자리 수가 0~9 이기 때..

문제 백준 1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 입력을 받은 후, 문자열을 알파벳 오름차순으로 정렬합니다. 그 이후에 루프를 돌면서 password의 크기가 length가 되면 검사를 합니다. 검사 후 조건(모음 1개 이상, 자음 2개 이상)을 만족하면 출력하고, 만족하지 못 하면 출력하지 않습니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37..