1. 콘웨이의 생명 게임 구현
콘웨이의 생명 게임은 세포 자동자(cellular automaton)의 한 종류로, 생명체의 탄생, 생존, 죽음을 단순한 규칙으로 시뮬레이션합니다. 각 세포는 8개의 이웃을 가질 수 있으며, 다음 규칙에 따라 상태가 변화합니다:
- 생존 규칙:
- 이웃 세포가 2개 또는 3개인 살아있는 세포는 다음 세대에도 생존합니다.
- 사망 규칙:
- 이웃 세포가 2개 미만인 살아있는 세포는 고립으로 죽습니다.
- 이웃 세포가 3개 초과인 살아있는 세포는 과밀로 죽습니다.
- 탄생 규칙:
- 이웃 세포가 정확히 3개인 죽어있는 세포는 다음 세대에서 살아있는 세포로 부활합니다.
모든 세포의 상태 변화는 동시에 발생합니다. 즉, 다음 세대의 상태를 계산할 때에는 현재 세대의 상태만을 기준으로 합니다.
알고리즘 구현 (C++)
게임 보드는 2차원 배열로 표현되며, 각 셀은 살아있는 상태(1) 또는 죽어있는 상태(0)를 가집니다. 사용자로부터 초기 살아있는 세포의 위치를 입력받아 보드를 초기화합니다. 각 세대마다 모든 세포에 대해 이웃 세포의 수를 계산하고 위 규칙에 따라 다음 세대의 상태를 결정합니다. 다음 세대의 상태가 모두 계산되면, 현재 세대의 상태를 다음 세대의 상태로 업데이트하고 화면에 출력합니다. 이 과정은 사용자가 중단할 때까지 반복됩니다.
#include <iostream>
#include <vector>
#include <string>
#include <cctype> // For toupper
#include <limits> // For numeric_limits
// Grid dimensions
const int GRID_ROWS = 8;
const int GRID_COLS = 8;
// Cell states
const int LIVE_CELL = 1;
const int DEAD_CELL = 0;
// Global grids for simplicity, can be passed as arguments
std::vector<std::vector<int>> currentGrid(GRID_ROWS, std::vector<int>(GRID_COLS, DEAD_CELL));
std::vector<std::vector<int>> nextGrid(GRID_ROWS, std::vector<int>(GRID_COLS, DEAD_CELL));
// Function declarations
void initializeGameGrid();
int calculateLiveNeighbors(int r, int c);
void displayGridStatus();
void updateGridState();
int main() {
char continue_game;
initializeGameGrid();
while (true) {
displayGridStatus();
for (int r = 0; r < GRID_ROWS; ++r) {
for (int c = 0; c < GRID_COLS; ++c) {
int neighborCount = calculateLiveNeighbors(r, c);
if (currentGrid[r][c] == LIVE_CELL) {
// Rule 1 & 3: Live cell dies if underpopulation (<2) or overpopulation (>3)
if (neighborCount < 2 || neighborCount > 3) {
nextGrid[r][c] = DEAD_CELL;
}
// Rule 2: Live cell with 2 or 3 neighbors lives
else {
nextGrid[r][c] = LIVE_CELL;
}
} else { // currentGrid[r][c] == DEAD_CELL
// Rule 4: Dead cell becomes live if exactly 3 neighbors
if (neighborCount == 3) {
nextGrid[r][c] = LIVE_CELL;
}
// Stays dead otherwise
else {
nextGrid[r][c] = DEAD_CELL;
}
}
}
}
updateGridState();
std::cout << "\n다음 세대로 진행하시겠습니까? (Y/N): ";
std::cin >> continue_game;
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // Clear input buffer
if (std::toupper(continue_game) != 'Y') {
break;
}
}
return 0;
}
// Initialize the game grid by user input for live cells
void initializeGameGrid() {
std::cout << "콘웨이의 생명 게임 시뮬레이션" << std::endl;
std::cout << "생존할 세포의 좌표 (행, 열)을 입력하세요." << std::endl;
std::cout << "범위: 0 <= 행 < " << GRID_ROWS << ", 0 <= 열 < " << GRID_COLS << std::endl;
std::cout << "입력 종료는 -1 -1 입력 (또는 유효하지 않은 범위 입력)." << std::endl;
int inputRow, inputCol;
while (true) {
std::cout << "좌표 입력 (행 열): ";
std::cin >> inputRow >> inputCol;
if (inputRow == -1 && inputCol == -1) {
break;
}
if (inputRow >= 0 && inputRow < GRID_ROWS && inputCol >= 0 && inputCol < GRID_COLS) {
currentGrid[inputRow][inputCol] = LIVE_CELL;
} else {
std::cout << "경고: (행, 열) 좌표가 유효 범위를 벗어났습니다. (-1 -1 입력 시 종료)" << std::endl;
// Clear bad input if any
std::cin.clear();
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}
}
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // Clear any remaining input
}
// Calculate the number of live neighbors for a given cell
int calculateLiveNeighbors(int r, int c) {
int liveCount = 0;
for (int dr = -1; dr <= 1; ++dr) {
for (int dc = -1; dc <= 1; ++dc) {
if (dr == 0 && dc == 0) continue; // Skip the cell itself
int neighborR = r + dr;
int neighborC = c + dc;
// Check boundaries
if (neighborR >= 0 && neighborR < GRID_ROWS && neighborC >= 0 && neighborC < GRID_COLS) {
if (currentGrid[neighborR][neighborC] == LIVE_CELL) {
liveCount++;
}
}
}
}
return liveCount;
}
// Display the current state of the grid
void displayGridStatus() {
std::cout << "\n\n-------------------- 현재 세포 상태 --------------------" << std::endl;
for (int r = 0; r < GRID_ROWS; ++r) {
for (int c = 0; c < GRID_COLS; ++c) {
std::cout << (currentGrid[r][c] == LIVE_CELL ? '*' : '-');
}
std::cout << std::endl;
}
}
// Copy the next generation grid to the current grid
void updateGridState() {
for (int r = 0; r < GRID_ROWS; ++r) {
for (int c = 0; c < GRID_COLS; ++c) {
currentGrid[r][c] = nextGrid[r][c];
}
}
}
2. 잠긴 문 퍼즐
복도에 1번부터 n번까지 n개의 문이 모두 잠긴 상태로 있습니다. 우리가 n번 지나갈 때마다 1번 문부터 시작합니다. i번째 지나갈 때마다 (i = 1, 2, ..., n) 우리는 i의 배수인 문들의 상태를 바꿉니다. 만약 문이 잠겨있으면 열고, 열려있으면 잠급니다. 마지막 n번째 지나간 후에 어떤 문들이 열려있고, 어떤 문들이 잠겨있을까요? 그리고 총 몇 개의 문이 열려있을까요?
알고리즘 구현 (C++)
이 문제는 각 문이 몇 번 상태가 바뀌는지를 추적하여 해결할 수 있습니다. 문 번호가 k인 문은 k의 약수 개수만큼 상태가 바뀝니다. 예를 들어, 1번 문은 1의 배수일 때(1번째 지나갈 때) 한 번 바뀝니다. 2번 문은 1의 배수일 때, 2의 배수일 때 두 번 바뀝니다. 문은 처음에 닫혀있으므로, 상태가 홀수 번 바뀌면 열리고, 짝수 번 바뀌면 닫힙니다. 따라서, 약수의 개수가 홀수인 문들만 최종적으로 열려 있게 됩니다. 약수의 개수가 홀수인 수는 제곱수(예: 1, 4, 9, 16...)뿐입니다.
#include <iostream>
#include <vector>
#include <numeric> // For std::numeric_limits
const int MAX_DOORS_LIMIT = 1000;
int main() {
int numberOfDoors;
std::cout << "총 문의 개수를 입력하세요 (1 ~ " << MAX_DOORS_LIMIT << "): ";
while (true) {
std::cin >> numberOfDoors;
if (std::cin.fail() || numberOfDoors <= 0 || numberOfDoors > MAX_DOORS_LIMIT) {
std::cin.clear(); // Clear error flags
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // Discard invalid input
std::cout << "잘못된 입력입니다. 1에서 " << MAX_DOORS_LIMIT << " 사이의 정수를 다시 입력하세요: ";
} else {
break;
}
}
// Initialize all doors as closed (false)
// doorStates[0] corresponds to door #1, doorStates[n-1] to door #n
std::vector<bool> doorStates(numberOfDoors, false); // false = closed, true = open
// Simulate N passes
// 'passNum' represents the i-th pass (from 1 to numberOfDoors)
for (int passNum = 1; passNum <= numberOfDoors; ++passNum) {
// In the i-th pass, we change the state of doors whose numbers are multiples of i
// 'doorIdx' represents the 0-indexed position in the vector
for (int doorIdx = passNum - 1; doorIdx < numberOfDoors; doorIdx += passNum) {
doorStates[doorIdx] = !doorStates[doorIdx]; // Toggle door state
}
}
std::cout << "\n최종적으로 열려 있는 문:" << std::endl;
int openDoorCount = 0;
for (int i = 0; i < numberOfDoors; ++i) {
if (doorStates[i]) {
std::cout << " " << (i + 1) << "번 문" << std::endl;
openDoorCount++;
}
}
std::cout << "\n총 " << openDoorCount << "개의 문이 열려 있습니다." << std::endl;
return 0;
}
3. 세 물통 퍼즐
8파인트의 물이 가득 찬 물통 하나와, 각각 5파인트 및 3파인트 용량의 빈 물통 두 개가 있습니다. 물통을 완전히 채우거나 완전히 비우는 방식, 또는 한 물통에서 다른 물통으로 물을 붓는 방식으로, 세 물통 중 하나에 정확히 4파인트의 물을 얻으려고 합니다. 이때 물을 붓는 과정을 추적하여 해법을 찾아야 합니다.
알고리즘 구현 (C++)
이 문제는 너비 우선 탐색(BFS)을 사용하여 해결할 수 있습니다. 각 물통의 현재 물의 양 (예: [0, 0, 8])을 하나의 '상태'로 정의하고, 가능한 모든 물 붓기 동작을 통해 다음 상태로 전환합니다. 이미 방문한 상태는 다시 탐색하지 않도록 기록하여 중복 계산을 피합니다. 목표는 어느 물통이든 4파인트의 물을 포함하는 상태를 찾는 것입니다. 경로를 재구성하기 위해 각 상태는 이전 상태의 인덱스를 저장해야 합니다. BFS는 최소한의 동작으로 해답을 찾을 수 있음을 보장합니다.
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm> // For std::min and std::reverse
// Define capacities of the three jugs: Jug0=3L, Jug1=5L, Jug2=8L
const int JUG_CAPACITIES[] = {3, 5, 8};
// Represents a state of the jugs
struct JugState {
std::vector<int> amounts; // Current water amounts in jugs
int parentIndex; // Index of the parent state in the `allStates` vector
int actionFrom; // Jug index from which water was poured (-1 for initial state)
int actionTo; // Jug index to which water was poured (-1 for initial state)
JugState(int a0, int a1, int a2, int parent = -1, int from = -1, int to = -1)
: amounts({a0, a1, a2}), parentIndex(parent), actionFrom(from), actionTo(to) {}
// For map key comparison (not strictly needed if std::vector<int> is key)
bool operator<(const JugState& other) const {
return amounts < other.amounts;
}
};
// Function to print the path from the initial state to the solution state
void printPath(const std::vector<JugState>& allStates, int endIndex) {
std::vector<JugState> path;
int currentIndex = endIndex;
while (currentIndex != -1) {
path.push_back(allStates[currentIndex]);
currentIndex = allStates[currentIndex].parentIndex;
}
std::reverse(path.begin(), path.end()); // Path from start to end
std::cout << "\n물 4파인트를 얻기 위한 과정:" << std::endl;
for (size_t i = 0; i < path.size(); ++i) {
const auto& state = path[i];
// Print action taken to reach this state
if (i > 0) {
std::cout << " 단계 " << i << ": ";
if (state.actionFrom != -1) { // Not the initial state
std::cout << (state.actionFrom + 1) << "번 물통에서 " << (state.actionTo + 1) << "번 물통으로 물 붓기";
}
std::cout << " -> ";
} else {
std::cout << " 초기 상태: ";
}
std::cout << "[" << state.amounts[0] << ", " << state.amounts[1] << ", " << state.amounts[2] << "]" << std::endl;
}
}
int main() {
std::queue<int> q; // Stores indices of states in `allStates` vector
std::vector<JugState> allStates; // Stores all explored states
std::map<std::vector<int>, bool> visited; // Tracks visited states using amounts as key
// Initial state: Jug2 (8-pint) full, others empty
// Capacities: Jug0=3, Jug1=5, Jug2=8. Initial amounts: [0, 0, 8]
JugState initialState(0, 0, JUG_CAPACITIES[2]);
allStates.push_back(initialState);
visited[initialState.amounts] = true;
q.push(0); // Push index of initial state
int targetAmount = 4;
int solutionIndex = -1; // Stores the index of the first state found that meets the target
while (!q.empty()) {
int currentIndex = q.front();
q.pop();
const JugState& currentState = allStates[currentIndex];
// Check if target amount (4 pints) is achieved in any jug
for (int amount : currentState.amounts) {
if (amount == targetAmount) {
solutionIndex = currentIndex;
break;
}
}
if (solutionIndex != -1) break; // Solution found, exit BFS
// Explore possible next states (pouring water)
for (int from = 0; from < 3; ++from) {
for (int to = 0; to < 3; ++to) {
if (from == to) continue; // Cannot pour to itself
// Create a potential next state by copying the current one
JugState nextState = currentState;
int& amountFrom = nextState.amounts[from];
int& amountTo = nextState.amounts[to];
// If source jug is empty or destination jug is full, cannot pour
if (amountFrom == 0 || amountTo == JUG_CAPACITIES[to]) {
continue;
}
// Calculate how much water can be poured
// It's the minimum of: water in source OR remaining space in destination
int pourAmount = std::min(amountFrom, JUG_CAPACITIES[to] - amountTo);
amountFrom -= pourAmount;
amountTo += pourAmount;
// Check if this new state has been visited
if (!visited[nextState.amounts]) {
visited[nextState.amounts] = true;
nextState.parentIndex = currentIndex; // Record parent for path reconstruction
nextState.actionFrom = from;
nextState.actionTo = to;
allStates.push_back(nextState); // Add new state to our collection
q.push(allStates.size() - 1); // Push index of new state to queue
}
}
}
}
if (solutionIndex != -1) {
printPath(allStates, solutionIndex);
} else {
std::cout << "물 4파인트를 만들 수 있는 방법을 찾을 수 없습니다." << std::endl;
}
return 0;
}
4. 문자열 매칭 문제
주어진 텍스트 내에서 특정 문자열(패턴)의 모든 발생 위치를 찾아야 합니다. 여기서는 가장 기본적인 문자열 매칭 알고리즘인 브루트 포스(Brute Force, BF) 알고리즘을 구현합니다.
브루트 포스(BF) 알고리즘 구현 (C++)
브루트 포스 문자열 매칭 알고리즘은 텍스트의 모든 가능한 시작 위치에서 패턴과 일치하는지 확인하는 간단한 접근 방식입니다. 텍스트의 `i`번째 문자부터 패턴의 첫 문자를 비교하고, 일치하면 다음 문자로 진행하여 패턴의 끝까지 비교합니다. 불일치가 발생하면, 텍스트의 시작 위치를 한 칸 뒤로 이동하여 다시 패턴의 첫 문자부터 비교를 시작합니다. 이 과정은 텍스트의 끝까지 반복됩니다. 최악의 경우 시간 복잡도는 O(M*N) (M은 텍스트 길이, N은 패턴 길이)입니다.
#include <iostream>
#include <string>
// <vector> not strictly needed for BF, but common in C++ string algorithms
// BF (Brute Force) 문자열 매칭 알고리즘
// text: 전체 텍스트 문자열
// pattern: 찾을 패턴 문자열
// startIndex: 텍스트에서 검색을 시작할 위치 (0-based index)
// 반환값: 패턴이 처음으로 일치하는 텍스트 내의 시작 인덱스, 일치하지 않으면 -1
int findSubstringBF(const std::string& text, const std::string& pattern, int startIndex) {
int textLength = text.length();
int patternLength = pattern.length();
// 빈 패턴은 항상 일치한다고 간주하거나 오류로 처리할 수 있습니다.
// 여기서는 startIndex에서 일치한다고 간주합니다.
if (patternLength == 0) return startIndex;
// 패턴이 텍스트보다 길면 매칭 불가
if (patternLength > textLength) return -1;
// 시작 인덱스가 유효 범위를 벗어나면 매칭 불가
if (startIndex < 0 || startIndex > textLength - patternLength) return -1;
// 텍스트의 가능한 모든 시작 위치를 순회
for (int i = startIndex; i <= textLength - patternLength; ++i) {
int j;
// 현재 텍스트 위치(i)에서 패턴과 비교
for (j = 0; j < patternLength; ++j) {
if (text[i + j] != pattern[j]) {
break; // 불일치 발생, 다음 텍스트 시작 위치로 이동
}
}
if (j == patternLength) {
// 패턴 전체가 일치하는 경우, 시작 인덱스 반환
return i;
}
}
return -1; // 텍스트에서 패턴을 찾지 못함
}
int main() {
std::string mainText = "ABABDABACDABABCABAB";
std::string searchPattern1 = "ABABCABAB";
std::string searchPattern2 = "ABCDE";
std::string searchPattern3 = "BAB";
int position1 = findSubstringBF(mainText, searchPattern1, 0);
if (position1 != -1) {
std::cout << "'" << searchPattern1 << "'이(가) 텍스트에서 인덱스 " << position1 << "에서 발견되었습니다.\n";
} else {
std::cout << "'" << searchPattern1 << "'이(가) 텍스트에서 발견되지 않았습니다.\n";
}
int position2 = findSubstringBF(mainText, searchPattern2, 0);
if (position2 != -1) {
std::cout << "'" << searchPattern2 << "'이(가) 텍스트에서 인덱스 " << position2 << "에서 발견되었습니다.\n";
} else {
std::cout << "'" << searchPattern2 << "'이(가) 텍스트에서 발견되지 않았습니다.\n";
}
// 다른 시작 인덱스에서의 검색 예시
int position3 = findSubstringBF(mainText, searchPattern3, 3); // 인덱스 3부터 검색 시작
if (position3 != -1) {
std::cout << "'" << searchPattern3 << "'이(가) 인덱스 3부터 시작하는 텍스트에서 인덱스 " << position3 << "에서 발견되었습니다.\n";
} else {
std::cout << "'" << searchPattern3 << "'이(가) 인덱스 3부터 시작하는 텍스트에서 발견되지 않았습니다.\n";
}
return 0;
}
5. 교대 배열된 디스크 정렬
2n개의 디스크가 일렬로 놓여 있으며, n개의 검은 디스크와 n개의 흰 디스크가 '검, 흰, 검, 흰...'과 같이 교대로 배열되어 있습니다. 목표는 모든 검은 디스크를 오른쪽에, 모든 흰색 디스크를 왼쪽에 배치하는 것입니다. 이 문제는 오직 인접한 디스크의 위치를 교환하는 방식으로만 해결할 수 있습니다. 이때, 이 작업을 수행하는 알고리즘을 작성하고 필요한 총 교환 횟수를 결정해야 합니다.
알고리즘 구현 (C++)
이 문제는 버블 정렬(Bubble Sort)과 유사한 방식으로 해결할 수 있습니다. 흰색 디스크를 '1', 검은색 디스크를 '2'로 표현하면, 초기 배열은 [2, 1, 2, 1, ..., 2, 1] 형태가 됩니다. 목표는 모든 '1'이 모든 '2' 앞에 오도록, 즉 [1, 1, ..., 1, 2, 2, ..., 2] 형태로 정렬하는 것입니다. 버블 정렬은 인접한 요소만을 교환하여 정렬하기 때문에, 문제의 조건에 부합하며 교환 횟수를 쉽게 세어낼 수 있습니다. 각 교환은 인접한 디스크의 순서가 뒤바뀔 때마다 카운트됩니다.
총 교환 횟수는 n개의 흰색 디스크와 n개의 검은 디스크가 교대로 배치된 상태(`BW BW ...` 또는 `2 1 2 1 ...`)에서 모든 흰색 디스크가 왼쪽으로, 모든 검은색 디스크가 오른쪽으로 이동하는 데 필요한 인접 교환 횟수입니다. 이 값은 `n * (n + 1) / 2`로 계산됩니다.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // For std::swap
// Function to print the current arrangement of discs
void printDiscArrangement(const std::vector<int>& discs) {
for (int disc : discs) {
if (disc == 1) {
std::cout << "백 "; // White disc
} else {
std::cout << "흑 "; // Black disc
}
}
std::cout << std::endl;
}
int main() {
int numPairs; // 'n' in the problem (total discs = 2n)
std::cout << "디스크 쌍의 개수(n)를 입력하세요 (총 디스크 2n): ";
std::cin >> numPairs;
if (std::cin.fail() || numPairs <= 0) {
std::cout << "유효한 디스크 쌍의 개수를 입력해주세요." << std::endl;
// Clear bad input if any
std::cin.clear();
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
return 1;
}
int totalDiscs = 2 * numPairs;
std::vector<int> discs(totalDiscs); // 1 for white, 2 for black
// Initialize discs: Black, White, Black, White... (흑, 백, 흑, 백...)
// This means even indices are Black (2), odd indices are White (1)
for (int i = 0; i < totalDiscs; ++i) {
discs[i] = (i % 2 == 0) ? 2 : 1;
}
std::cout << "\n초기 디스크 배치: ";
printDiscArrangement(discs);
long long swapCount = 0; // Use long long for swap count to prevent overflow for large N
// Use bubble sort logic to move all whites to the left and blacks to the right
// The goal is to sort '1's before '2's, which corresponds to white on left, black on right.
for (int i = 0; i < totalDiscs - 1; ++i) {
for (int j = 0; j < totalDiscs - 1 - i; ++j) {
// If a black disc (2) is before a white disc (1), swap them
if (discs[j] > discs[j + 1]) { // e.g., if discs[j] is 2 and discs[j+1] is 1
std::swap(discs[j], discs[j + 1]);
swapCount++;
}
}
}
std::cout << "정렬 후 디스크 배치: ";
printDiscArrangement(discs);
std::cout << "총 교환 횟수: " << swapCount << std::endl;
return 0;
}