ROOT

📌 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 📌 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 📌 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 📌 문제 풀이 👨‍🏫 접근 백트래킹의 꽃인 N-Queen 문제이다. N-Queen이 가능한 모든 경우를 탐색해야 한다. 👨‍🏫 문제 풀이 📄 전체 코드 n = int(input()) flag_1 = [0] * n flag_2 = [0] * (2 * n - 1) flag_3 = [0] * (2 * n - 1) cnt = 0 def nQueen(depth): global cnt if dep..

📌 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 📌 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 📌 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 📌 문제 풀이 👨‍🏫 접근 1, 2, 3을 사용해서 만들 수 있는 경우를 모두 구하는 문제. 다이나믹 프로그래밍과 백트래킹 둘 중 하나를 사용해서 풀이할 수 있다...

📌 문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 📌 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 📌 출력 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. 📌 문제 풀이 👨‍🏫 접근 6603 로또와 비슷한 문제 리스트를 모두 순회하면서 문제의 조건을 충족하는 경우를 출력한다. 브루트포스 알고리즘 중에서 백트래킹을 사용했다. 👨‍🏫 문제 풀이 📄 전체 코드 def solve(idx, SUM): glo..

📌 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34]) 집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오. 📌 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다..