반응형
그룹액티비티 1번
int fun1(int x, int y) {
if (x > y) {
return 0;
}
return y + fun1(x, y - 1);
}이 합은 등차수열의 합과 같습니다. 등차수열의 합 공식은 다음과 같습니다:
주어진 함수 분석
주어진 함수 fun1은 다음과 같은 형태입니다:
cpp
코드 복사
int fun1(int x, int y) { if (x > y) { return 0; } return y + fun1(x, y - 1); }
이 함수는 x와 y를 입력으로 받으며, x가 y보다 클 때는 0을 반환하고, 그렇지 않으면 y를 더한 값을 fun1(x, y - 1)을 재귀적으로 호출하여 반환합니다.
함수의 반환값을 x와 y의 함수로 나타내기
함수의 동작을 따라가며, 반환값을 더 간단한 함수로 표현할 수 있습니다.
- 기저 조건: x > y일 때 0을 반환합니다.
- 재귀 호출: y + fun1(x, y - 1)은 y와 그보다 작은 값인 y - 1을 더한 결과로, 이 과정은 x > y가 될 때까지 반복됩니다.
이 함수는 사실 y에서 x까지 모든 정수를 더하는 함수와 같습니다. 즉, y + (y - 1) + (y - 2) + ... + x와 같은 형태로 동작합니다. 이를 수학적으로 표현하면, 이는 y와 x 사이의 연속적인 수들의 합입니다.
수학적 표현
이 연속적인 수들의 합을 구하는 방법은 다음과 같습니다:
text
코드 복사
S = y + (y - 1) + (y - 2) + ... + x
이 합은 등차수열의 합과 같습니다. 등차수열의 합 공식은 다음과 같습니다:
S=n2⋅(a1+an)S = \frac{n}{2} \cdot (a_1 + a_n)여기서 n은 항의 개수, a_1은 첫 번째 항, a_n은 마지막 항입니다.
- 첫 번째 항은 y, 마지막 항은 x.
- 항의 개수는 y - x + 1.
따라서 함수의 반환값은 다음과 같습니다:
Return Value=(y−x+1)2⋅(x+y)\text{Return Value} = \frac{(y - x + 1)}{2} \cdot (x + y)이 표현은 fun1(x, y)의 반환값을 x와 y의 함수로 나타낸 것입니다.
예시
- 입력: fun1(2, 5)의 경우, 함수는 5 + 4 + 3 + 2 = 14를 반환합니다.
- 수학적 계산: 위의 수학적 공식에 따르면, Return Value=(5−2+1)2⋅(2+5)=42⋅7=2⋅7=14\text{Return Value} = \frac{(5 - 2 + 1)}{2} \cdot (2 + 5) = \frac{4}{2} \cdot 7 = 2 \cdot 7 = 14
따라서 함수 fun1(2, 5)는 14를 반환합니다.
2번
int fun2(int n) {
if (n == 1)
return 0;
else
return 1 + fun2(n / 2);
}수학적 표현
이 함수의 반환값은 log₂(n)에 해당하는 값을 나타냅니다. 정확하게는 floor(log₂(n))입니다.
예시
- fun2(1)의 경우:
- n == 1이므로 바로 0을 반환합니다.
- fun2(2)의 경우:
- fun2(2)는 1 + fun2(2 / 2) = 1 + fun2(1)입니다.
- fun2(1)은 0을 반환하므로, 1 + 0 = 1을 반환합니다.
- fun2(5)의 경우:
- fun2(5)는 1 + fun2(5 / 2) = 1 + fun2(2)입니다.
- fun2(2)는 1 + fun2(2 / 2) = 1 + fun2(1)입니다.
- fun2(1)은 0을 반환하므로, fun2(2)는 1 + 0 = 1이 되고,
- 따라서 fun2(5)는 1 + 1 = 2를 반환합니다.
3번
void fun3(int n) {
if (n == 0)
return;
fun3(n / 2);
printf("%d", n % 2);
}함수 분석
- 기저 조건:
- 만약 n == 0이면, 함수는 아무 작업도 하지 않고 반환합니다. 즉, 재귀 호출이 종료됩니다.
- 재귀 호출:
- fun3(n / 2)를 호출하여 n을 2로 나눈 값을 다시 fun3에 전달합니다. 이는 n이 0이 될 때까지 반복됩니다.
- printf("%d", n % 2)는 n을 2로 나눈 나머지(n % 2)를 출력합니다. 이 부분은 n이 2로 나누어질 때마다 나머지 값을 출력하는 역할을 합니다.
함수 동작 설명
이 함수는 n을 2로 계속해서 나누며, 나머지 값을 출력하는 함수입니다. 재귀적으로 n을 2로 나누면서, 마지막에 n이 0이 될 때까지 나머지 값을 출력하는 순서가 중요합니다.
핵심 개념: 이 함수는 n을 이진수로 출력하는 함수입니다. 왜냐하면, 2로 나눈 나머지는 이진수 표현에서 각 자리를 나타내기 때문입니다
4번
void fun4(int n) {
if (n > 1)
fun4(n - 1);
for (int i = 0; i < n; i++)
printf(" * ");
}함수 분석
- 기저 조건:
- 만약 n > 1이라면 fun4(n - 1)이 호출됩니다. 이 함수는 재귀적으로 n - 1을 인수로 하여 계속 호출됩니다.
- n == 1일 때는 fun4(n - 1)이 호출되지 않으므로, 이 시점에서 재귀 호출이 종료됩니다.
- 반복문:
- for (int i = 0; i < n; i++)는 n번 반복하며 " * "를 출력합니다.
- 즉, n의 값에 따라 " * "를 출력하는 반복문이 실행됩니다.
함수 동작 설명
- 이 함수는 n이 1일 때까지 재귀적으로 호출되며, 그 후 각 재귀 호출에서 n에 해당하는 " * "를 출력합니다.
- 함수가 처음 호출되면 n부터 1까지 재귀적으로 호출된 후, 그 다음에 각 호출마다 n 개의 " * "를 출력합니다.
5번
int fun(int x, int y) {
if (y == 0)
return 0;
return (x + fun(x, y - 1));
}
- 기저 조건:
- 만약 y == 0이면 함수는 0을 반환합니다.
- 재귀 호출:
- 만약 y != 0이면 x + fun(x, y - 1)이 호출됩니다.
- 즉, y가 0이 될 때까지 x를 계속 더하는 방식입니다.
- 결과적으로 fun(x, y)는 x가 y번 더해진 값을 반환합니다.
- 따라서 fun(x, y)는 x * y를 반환하는 함수입니다.
- 기저 조건:
- b == 0일 때, 함수는 1을 반환합니다.
- 재귀 호출:
- b != 0이면 fun(a, fun5(a, b - 1))을 호출합니다.
- 이때 fun5(a, b - 1)이 먼저 호출되어 b - 1에 대한 결과가 계산됩니다. 그 후, fun(a, ...)가 호출되는데, 여기서 fun(x, y)는 x * y와 같은 방식으로 동작하므로, fun(a, fun5(a, b - 1))은 a와 fun5(a, b - 1)의 곱을 반환합니다.
함수 동작 예시
fun5(2, 3)을 호출한 경우:
- fun5(2, 3)은 fun(2, fun5(2, 2))을 호출합니다.
- fun5(2, 2)는 fun(2, fun5(2, 1))을 호출합니다.
- fun5(2, 1)은 fun(2, fun5(2, 0))을 호출합니다.
- fun5(2, 0)은 1을 반환합니다.
- fun5(2, 1)은 fun(2, 1)을 호출하고, fun(2, 1)은 2 + 0 = 2를 반환합니다.
- fun5(2, 2)는 fun(2, 2)를 호출하고, fun(2, 2)는 2 + 2 = 4를 반환합니다.
- fun5(2, 3)은 fun(2, 4)를 호출하고, fun(2, 4)는 2 + 2 + 2 + 2 = 8을 반환합니다.
- 그러므로:
따라서 fun5(2, 3)의 결과는 8입니다.
반환값을 a와 b에 관한 식으로 표현하기
fun(x, y)는 x * y이므로, fun5(a, b)는 재귀적으로 fun(a, fun5(a, b - 1))을 호출하여 곱셈을 반복합니다.
결과적으로, fun5(a, b)는 a의 b번째 거듭제곱을 구하는 함수로, 다음과 같은 수식으로 표현됩니다:
fun5(a,b)=ab\text{fun5}(a, b) = a^b
결론
따라서, 주어진 함수 fun5(a, b)의 반환값은 a^b (a의 b제곱)입니다.
6번
함수 fun6는 주어진 배열 a[]에서 첫 번째 원소부터 n번째 원소까지 중 가장 큰 값을 찾는 함수입니다.
동작 설명:
- 기저 조건:
- 배열의 크기가 1일 때(n == 1), 배열의 첫 번째 원소 a[0]를 반환합니다.
- 재귀 호출:
- 배열의 나머지 원소들에 대해서 가장 큰 값을 찾기 위해 fun6(a, n - 1)을 재귀적으로 호출합니다.
- 이때 반환된 값 x는 a[0]부터 a[n-2]까지의 최대값이 됩니다.
- 마지막으로, x와 a[n-1]을 비교하여 더 큰 값을 반환합니다.
결론:
fun6(a, n)은 배열 a[]의 첫 번째 원소부터 n번째 원소까지 중 가장 큰 값을 반환하는 함수입니다.
7번
함수 fun7는 주어진 배열 a[]의 첫 번째 원소부터 n번째 원소까지에 대해 가중 평균을 계산하는 함수입니다.
동작 설명:
기저 조건:
n == 1일 때, 배열의 첫 번째 원소 a[0]을 반환합니다.
재귀 호출:
배열의 첫 번째 원소부터 n-1번째 원소까지의 가중 평균을 계산하기 위해, fun7(a, n-1)을 재귀적으로 호출합니다.
(a[n-1] + (n-1) * fun7(a, n-1)) / n에서:
a[n-1]은 현재 원소이고,
(n-1) * fun7(a, n-1)은 이전 계산된 평균에 가중치를 더한 값입니다.
그 결과를 n으로 나누어 n개 원소에 대한 가중 평균을 구합니다.
결론:
fun7(a, n)은 배열 a[]의 첫 번째 원소부터 n번째 원소까지의 가중 평균을 계산하는 함수입니다.
8번
함수 fun8은 a의 b제곱을 계산하는 함수입니다. 이 함수는 분할 정복을 사용하여 효율적으로 거듭제곱을 계산합니다.
동작 설명:
- 기저 조건:
- b == 0이면 1을 반환합니다. (어떤 수의 0제곱은 1이기 때문)
- 재귀 호출:
- 만약 b가 짝수일 경우, fun8(a * a, b / 2)를 호출하여 a^b를 계산합니다. (거듭제곱을 절반으로 나누어 계산)
- 만약 b가 홀수일 경우, fun8(a * a, b / 2) * a를 호출하여 계산된 결과에 a를 한 번 더 곱합니다.
결론:
fun8(a, b)는 a의 b제곱을 효율적으로 계산하는 함수로, 재귀적으로 계산을 분할하여 수행합니다.
9번
함수 fun9 설명
함수 fun9는 배열 arr[]의 start_index에서 end_index까지의 구간에서 선택 정렬(Selection Sort) 방식으로 가장 작은 값을 찾아서 배열의 앞부분에 배치하는 역할을 합니다.
동작 설명:
- 기저 조건:
- start_index >= end_index이면 함수가 종료됩니다. 즉, start_index가 end_index보다 크거나 같으면 더 이상 정렬할 필요가 없다는 의미입니다.
- 선택 정렬:
- minIndex(arr, start_index, end_index) 함수는 배열에서 start_index부터 end_index까지의 구간에서 가장 작은 값을 가진 원소의 인덱스를 반환합니다.
- 그런 다음 arr[start_index]와 arr[min_index]의 값을 교환하여 가장 작은 값을 배열의 앞부분으로 이동시킵니다.
- 재귀 호출:
- fun9(arr, start_index + 1, end_index)는 배열의 다음 구간을 처리하기 위해 재귀적으로 호출됩니다. 즉, 한 번 호출될 때마다 start_index가 1씩 증가하여 점차 배열의 끝까지 탐색합니다.
결론:
fun9는 배열의 부분 구간을 재귀적으로 처리하면서, 선택 정렬 방식으로 배열을 정렬합니다. 각 재귀 호출에서 가장 작은 값을 찾아 현재 위치에 배치하고, 나머지 부분을 정렬합니다.
int minIndex(int arr[], int start_index, int end_index) {
int min_idx = start_index;
for (int i = start_index + 1; i < end_index; i++) {
if (arr[i] < arr[min_idx]) {
min_idx = i;
}
}
return min_idx;
}
예상문제
예상문제 1: 재귀 함수와 합산
문제: 다음과 같은 순환 함수가 있습니다. 이 함수의 반환값을 x와 y에 관한 식으로 나타내세요.
int fun1(int x, int y) {
if (x >= y) return 0;
return x + fun1(x + 1, y);
}
예상문제 2: 이진수의 개수 계산
문제: 주어진 순환 함수는 주어진 숫자 n을 2로 계속 나누어 나가며, n이 1이 될 때까지 몇 번 나누는지를 계산합니다. 코드와 함께 함수가 하는 일을 설명하세요.
int fun2(int n) {
if (n == 1) return 0;
else return 1 + fun2(n / 2);
}
예상문제 3: 배열의 가중 평균 계산
문제: 주어진 배열 a[]에서 n개의 요소에 대해 가중 평균을 계산하는 함수입니다. 함수의 결과를 설명하세요.
double fun7(double a[], int n) {
if (n == 1) return a[0];
return (a[n - 1] + (n - 1) * fun7(a, n - 1)) / n;
}
예상문제 4: 재귀적 선택 정렬
문제: 배열을 재귀적으로 선택 정렬하는 프로그램을 작성하세요. 아래와 같은 함수로 배열을 정렬할 수 있도록 수정하세요..
void fun9(int arr[], int start_index, int end_index) {
if (start_index >= end_index) return;
int min_index;
int temp;
min_index = minIndex(arr, start_index, end_index);
temp = arr[start_index];
arr[start_index] = arr[min_index];
arr[min_index] = temp;
fun9(arr, start_index + 1, end_index);
}예상문제 6: 배열에서 최대값 찾기 (재귀적 방법)
문제: 주어진 배열 arr[]에서 n개의 요소에 대해 최대값을 찾는 함수의 동작을 설명하고, 함수를 작성하세요.
int fun6(int a[], int n) {
if (n == 1) return a[0];
int x = fun6(a, n - 1);
return (x > a[n - 1] ? x : a[n - 1]);
}
11번
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 순환 함수로 두 문자열을 사전식으로 비교하는 함수
int compare(string str1, string str2, int index = 0) {
// 문자열의 길이가 다르면, 짧은 문자열이 먼저 오므로 그 차이를 비교
if (index == str1.length() && index == str2.length()) {
return 0; // 두 문자열이 완전히 같으면 0을 반환
}
if (index == str1.length()) {
return -1; // str1이 먼저 끝나면 str1이 사전식으로 먼저 오므로 -1을 반환
}
if (index == str2.length()) {
return 1; // str2가 먼저 끝나면 str2가 사전식으로 먼저 오므로 1을 반환
}
// 현재 index 위치의 문자들 비교
if (str1[index] < str2[index]) {
return -1; // str1이 사전식으로 먼저 오면 -1
} else if (str1[index] > str2[index]) {
return 1; // str1이 사전식으로 나중에 오면 1
}
// 문자가 같으면, 다음 문자로 비교를 계속 진행
return compare(str1, str2, index + 1);
}
int main() {
string word1, word2;
// 두 단어 입력 받기
cout << "두 단어를 입력하세요: ";
cin >> word1 >> word2;
// 사전식 순서 비교 결과 출력
int result = compare(word1, word2);
if (result == -1) {
cout << word1 << " < " << word2 << endl;
} else if (result == 0) {
cout << word1 << " == " << word2 << endl;
} else {
cout << word1 << " > " << word2 << endl;
}
return 0;
}예상문제:
- 두 문자열의 사전식 순서 비교 및 정렬 프로그램 작성하기
- 문제: 두 문자열을 입력받아 사전식 순서대로 정렬하는 프로그램을 작성하시오. 이때, 문자열의 사전식 순서를 비교하는 함수는 순환적으로 구현해야 한다. 사전식 순서는 알파벳 순서로, 같으면 0을, 첫 번째 문자열이 더 작은 경우에는 -1을, 두 번째 문자열이 더 작은 경우에는 1을 반환해야 한다. C++ 표준 라이브러리에서 제공하는 문자열 비교 함수는 사용하지 않는다.
- 조건:
- 두 문자열의 길이는 최대 1000자까지 허용된다.
- 사전식 순서대로 문자열을 정렬하여 출력하시오.
- 입력:
- 첫 번째 줄에 정수 N (1 ≤ N ≤ 1000)이 주어진다.
- 두 번째 줄부터 N개의 문자열이 주어진다. 각 문자열은 공백으로 구분된다.
- 출력:
- 정렬된 문자열들을 한 줄에 하나씩 출력하시오.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// 두 문자열을 사전식으로 비교하는 함수
int compare(string str1, string str2, int index = 0) {
if (index == str1.length() && index == str2.length()) {
return 0; // 두 문자열이 같으면 0을 반환
}
if (index == str1.length()) {
return -1; // str1이 먼저 끝나면 str1이 사전식으로 먼저 오므로 -1을 반환
}
if (index == str2.length()) {
return 1; // str2가 먼저 끝나면 str2가 사전식으로 먼저 오므로 1을 반환
}
// 현재 문자들 비교
if (str1[index] < str2[index]) {
return -1; // str1이 사전식으로 먼저 오면 -1
} else if (str1[index] > str2[index]) {
return 1; // str1이 사전식으로 나중에 오면 1
}
// 문자가 같으면, 다음 문자로 비교를 계속 진행
return compare(str1, str2, index + 1);
}
int main() {
int N;
cin >> N; // 문자열의 개수 입력
vector<string> words(N);
for (int i = 0; i < N; i++) {
cin >> words[i]; // 각 문자열 입력
}
// 재귀적으로 비교하여 정렬
sort(words.begin(), words.end(), [](const string &a, const string &b) {
return compare(a, b) < 0; // 사전식 순서대로 정렬
});
// 정렬된 문자열 출력
for (const string &word : words) {
cout << word << endl;
}
return 0;
}
12번
#include <iostream>
#include <vector>
using namespace std;
class NQueens {
public:
// N개의 퀸을 배치하는 방법의 개수를 반환하는 함수
int countSolutions(int N) {
// 각 열에 퀸을 놓은 상태를 추적하기 위한 배열
vector<int> board(N, -1);
int solutionCount = 0;
// 재귀적으로 퀸을 배치하면서 해를 찾는다.
solve(board, N, 0, solutionCount);
return solutionCount;
}
private:
// 백트래킹을 사용하여 퀸을 배치하는 함수
void solve(vector<int>& board, int N, int row, int& solutionCount) {
// 모든 퀸을 배치했으면, 해를 하나 찾은 것임
if (row == N) {
solutionCount++;
return;
}
for (int col = 0; col < N; col++) {
// 해당 위치에 퀸을 놓을 수 있는지 확인
if (isSafe(board, row, col, N)) {
board[row] = col; // 퀸을 배치
solve(board, N, row + 1, solutionCount); // 다음 행으로 이동
board[row] = -1; // 백트래킹
}
}
}
// 해당 위치에 퀸을 놓을 수 있는지 확인하는 함수
bool isSafe(const vector<int>& board, int row, int col, int N) {
for (int i = 0; i < row; i++) {
// 같은 열에 퀸이 있는지, 대각선에 퀸이 있는지 확인
if (board[i] == col || abs(board[i] - col) == abs(i - row)) {
return false;
}
}
return true;
}
};
int main() {
NQueens nQueens;
// N=1부터 N=15까지의 해의 개수를 구하여 출력
for (int N = 1; N <= 15; ++N) {
int result = nQueens.countSolutions(N);
cout << result << " ";
}
return 0;
}
응용문제:
문제:
N-Queens 문제를 기반으로, 특정 열에 퀸을 반드시 배치해야 한다는 제약을 추가하여 퀸을 배치하는 프로그램을 작성하시오.
- 입력으로 두 가지 값이 주어진다:
- N (1 <= N <= 15): 퀸을 배치할 체스판의 크기.
- K (1 <= K <= N): K번째 열에 퀸을 반드시 배치해야 한다는 제약.
- 주어진 제약에 따라 퀸을 배치할 수 있는 방법의 개수를 출력하시오
#include <iostream>
#include <vector>
using namespace std;
class NQueens {
public:
// 특정 열에 반드시 퀸을 배치한 후, 가능한 배치 방법을 카운트하는 함수
int countSolutions(int N, int K) {
// 각 열에 퀸을 놓은 상태를 추적하는 배열
vector<int> board(N, -1);
int solutionCount = 0;
// 3번째 열에 퀸을 놓은 후, 나머지 열에 대해 재귀적으로 해결
solve(board, N, K - 1, solutionCount); // K는 1-based index
return solutionCount;
}
private:
// 백트래킹을 사용하여 퀸을 배치하는 함수
void solve(vector<int>& board, int N, int fixedColumn, int& solutionCount) {
// 첫 번째로 반드시 퀸이 들어가야 할 열을 배치
board[fixedColumn] = fixedColumn; // 해당 열에 퀸을 배치
solveRecursive(board, N, 0, solutionCount); // 첫 번째 행부터 시작
board[fixedColumn] = -1; // 원래 상태로 되돌리기 (백트래킹)
}
// 재귀적으로 나머지 퀸을 배치하는 함수
void solveRecursive(vector<int>& board, int N, int row, int& solutionCount) {
// 모든 행에 퀸을 배치했다면 해를 하나 찾은 것
if (row == N) {
solutionCount++;
return;
}
// 현재 행에 퀸을 배치할 수 있는 열을 찾음
for (int col = 0; col < N; col++) {
if (board[col] == -1 && isSafe(board, row, col, N)) {
board[row] = col;
solveRecursive(board, N, row + 1, solutionCount);
board[row] = -1; // 백트래킹
}
}
}
// 해당 위치에 퀸을 놓을 수 있는지 확인하는 함수
bool isSafe(const vector<int>& board, int row, int col, int N) {
// 다른 퀸이 같은 열에 있거나, 대각선에 있으면 안 된다.
for (int i = 0; i < row; i++) {
if (board[i] == col || abs(board[i] - col) == abs(i - row)) {
return false;
}
}
return true;
}
};
int main() {
NQueens nQueens;
// 예시 입력을 받음
int N, K;
cin >> N >> K;
// 해의 개수를 구하여 출력
int result = nQueens.countSolutions(N, K);
cout << result << endl;
return 0;
}응용문제 (킹과 퀸 배치 문제):
문제:
N×N 체스판에서 퀸과 킹을 배치해야 한다. 퀸은 전통적인 N-Queens 규칙을 따르고, 킹은 자기 자신을 포함한 인접 8칸에 퀸이 존재하면 안 된다는 제약을 가진다.
- 퀸의 규칙: 퀸은 같은 행, 열, 또는 대각선에 다른 퀸이 없어야 한다.
- 킹의 규칙: 킹은 인접한 8개의 칸에 퀸이 있을 수 없다.
- 주어진 크기의 체스판에서 퀸과 킹을 배치할 수 있는 방법의 수를 구하시오.
입력:
- N (1 <= N <= 15): 퀸과 킹을 배치할 체스판의 크기
출력:
- 퀸과 킹을 배치할 수 있는 방법의 수를 출력하시오.
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
class QueenKingPlacement {
public:
int countSolutions(int N) {
// 체스판 초기화
vector<int> board(N, -1); // 각 열에 퀸 배치 상태를 추적
int solutionCount = 0;
solve(board, N, 0, solutionCount); // 퀸을 배치하는 함수 호출
return solutionCount;
}
private:
void solve(vector<int>& board, int N, int row, int& solutionCount) {
if (row == N) {
// 퀸 배치가 완료된 후, 킹 배치 가능 여부를 확인
if (canPlaceKings(board, N)) {
solutionCount++;
}
return;
}
for (int col = 0; col < N; col++) {
if (board[col] == -1 && isSafe(board, row, col, N)) {
board[row] = col; // 퀸을 배치
solve(board, N, row + 1, solutionCount);
board[row] = -1; // 백트래킹
}
}
}
bool isSafe(const vector<int>& board, int row, int col, int N) {
for (int i = 0; i < row; i++) {
if (board[i] == col || abs(board[i] - col) == abs(i - row)) {
return false;
}
}
return true;
}
// 킹을 배치할 수 있는지 확인하는 함수
bool canPlaceKings(const vector<int>& board, int N) {
vector<vector<bool>> boardStatus(N, vector<bool>(N, true));
// 퀸이 놓여 있는 칸을 표시
for (int row = 0; row < N; row++) {
if (board[row] != -1) {
int col = board[row];
// 퀸이 놓여진 칸과 킹이 놓을 수 없는 칸을 표시
for (int i = max(0, row - 1); i <= min(N - 1, row + 1); i++) {
for (int j = max(0, col - 1); j <= min(N - 1, col + 1); j++) {
boardStatus[i][j] = false;
}
}
}
}
// 킹이 놓을 수 있는 자리를 확인
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
if (boardStatus[row][col]) {
// 킹을 배치할 수 있으면 return true
return true;
}
}
}
return false;
}
};
int main() {
QueenKingPlacement solution;
// 예시 입력을 받음
int N;
cin >> N;
// 해의 개수를 구하여 출력
int result = solution.countSolutions(N);
cout << result << endl;
return 0;
}
문제: 킹의 배치 문제
문제 설명:
N×N 체스판에 킹을 배치해야 합니다. 킹은 한 번에 한 칸씩만 이동할 수 있으며, 각 킹은 인접한 8개의 칸에 다른 킹이 있을 수 없습니다. 즉, 킹은 다른 킹과 인접할 수 없습니다. 킹을 체스판에 최대한 많이 배치하려고 할 때, 배치할 수 있는 킹의 최대 개수를 구하시오.
조건:
- 킹은 체스판에서 한 번에 한 칸씩만 이동할 수 있다.
- 킹은 다른 킹과 인접한 칸에 배치할 수 없다.
- 킹은 반드시 빈 칸에만 배치해야 한다.
- 체스판의 크기는 N×N이며, N은 1 이상 15 이하의 정수이다.
#include <iostream>
#include <vector>
using namespace std;
class KingPlacement {
public:
int maxKings(int N) {
// N x N 체스판 초기화
vector<vector<bool>> board(N, vector<bool>(N, true));
int maxCount = 0;
placeKings(board, N, 0, 0, 0, maxCount); // 킹을 배치하는 함수 호출
return maxCount;
}
private:
// 킹을 배치할 수 있는지 확인하는 함수
bool canPlaceKing(const vector<vector<bool>>& board, int N, int row, int col) {
if (row < 0 || row >= N || col < 0 || col >= N || !board[row][col]) {
return false;
}
// 킹이 놓여 있을 수 없는 인접 8칸을 확인
int directions[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
for (int i = 0; i < 8; i++) {
int newRow = row + directions[i][0];
int newCol = col + directions[i][1];
if (newRow >= 0 && newRow < N && newCol >= 0 && newCol < N && !board[newRow][newCol]) {
return false;
}
}
return true;
}
// 킹을 배치하는 함수
void placeKings(vector<vector<bool>>& board, int N, int row, int col, int count, int& maxCount) {
if (row == N) {
maxCount = max(maxCount, count); // 최대 킹 배치 수 갱신
return;
}
if (col == N) {
placeKings(board, N, row + 1, 0, count, maxCount); // 한 행 끝나면 다음 행으로 이동
return;
}
// 킹을 놓지 않는 경우
placeKings(board, N, row, col + 1, count, maxCount);
// 킹을 놓는 경우
if (canPlaceKing(board, N, row, col)) {
board[row][col] = false; // 킹을 놓은 칸을 비우지 않도록 표시
placeKings(board, N, row, col + 1, count + 1, maxCount);
board[row][col] = true; // 킹을 놓은 칸을 다시 복구
}
}
};
int main() {
KingPlacement solution;
// 예시 입력을 받음
int N;
cin >> N;
// 킹을 최대한 배치할 수 있는 방법을 구하여 출력
int result = solution.maxKings(N);
cout << result << endl;
return 0;
}반응형
'IT 프로그래밍 > 자료구조' 카테고리의 다른 글
| 자료구조 예상 문제 1 (0) | 2024.12.15 |
|---|---|
| 자료구조 그룹액티비티7 (0) | 2024.12.15 |
| 자료구조 [예상] (0) | 2024.10.23 |
| 자료구조 과제3 (0) | 2024.10.23 |
| [자료구조] 노래찾기 (2) | 2024.10.23 |