# 삼성전자 DS 코딩테스트 종합 해결 전략 가이드

## 목차

1. 전체 코드 구조
2. 기본 알고리즘
2.1 BFS (너비 우선 탐색)
2.2 DFS (깊이 우선 탐색)
2.3 다익스트라 알고리즘
2.4 브루트포스 (완전탐색)
2.5 그리디 알고리즘
2.6 우선순위 큐
2.7 백트래킹
3. 특수 알고리즘
3.1 투 포인터
3.2 비트마스킹
3.3 분리 집합 (Union-Find)
3.4 회전 알고리즘
4. 시뮬레이션 로직
5. 자주 사용되는 테크닉
5.1 회전
5.2 순열, 중복 순열, 조합, 중복 조합
5.3 중력
5.4 달팽이(나선형) 배열
5.5 이동 중 벽에 부딪혀서 방향이 전환되는 경우
5.6 배열 한 칸씩 돌리기
5.7 부분 회전
5.8 토네이도 (나선형) 이동
5.9 격자 밖으로 나가는 경우 처리
5.10 2차원 누적 합 (2D Prefix Sum)
5.11 C++에서 배열을 함수 매개변수로 사용하기

## 1. 전체 코드 구조

삼성 DS 코딩테스트 문제를 해결하기 위한 전체적인 코드 구조는 다음과 같습니다:

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstring>
#include <climits>
#include <map>
#include <set>
#include <bitset>
using namespace std;

const int MAX_N = 100;
const int INF = INT_MAX;
const int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
const int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};

int N, M, K;
vector<vector<int>> board;
vector<vector<bool>> visited;

struct Entity {
    int x, y, id, hp, attack;
    // 추가 속성
};

vector<Entity> entities;

// 각 알고리즘 함수 선언
void simulate();
vector<vector<int>> bfs(int startX, int startY);
void dfs(int x, int y);
vector<int> dijkstra(int start);
void bruteForce();
void greedyAlgorithm();
void usePriorityQueue();
void backtracking(int depth);
void twoPointers();
void bitmaskingExample();
void initUnionFind();
int find(int x);
void unite(int a, int b);
void rotateMatrix(vector<vector<int>>& matrix);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // 입력 처리
    cin >> N >> M >> K;
    board.resize(N, vector<int>(M));
    visited.resize(N, vector<bool>(M, false));

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> board[i][j];
        }
    }

    // 엔티티 정보 입력 (예시)
    for (int i = 0; i < K; i++) {
        int x, y, hp, attack;
        cin >> x >> y >> hp >> attack;
        entities.push_back({x, y, i, hp, attack});
    }

    // 시뮬레이션 실행
    simulate();

    // 결과 출력
    // ...

    return 0;
}

// 각 알고리즘 함수 구현
// ...

이 코드 구조의 특징:

1. 필요한 모든 헤더 파일을 포함합니다.
2. 자주 사용되는 상수와 방향 배열을 정의합니다.
3. 문제에서 주어지는 주요 변수들을 전역 변수로 선언합니다.
4. 2D 벡터를 사용하여 게임 보드와 방문 여부를 표현합니다.
5. `Entity` 구조체를 정의하여 게임 내 객체를 표현합니다.
6. 각 알고리즘에 대한 함수를 선언합니다.
7. `main` 함수에서 입력 처리, 시뮬레이션 실행, 결과 출력의 기본 흐름을 제공합니다.

## 2. 기본 알고리즘

### 2.1 BFS (너비 우선 탐색)

BFS는 그래프나 트리 구조에서 노드를 탐색하는 알고리즘으로, 시작 노드에서 가까운 노드부터 차례대로 탐색합니다.

#### BFS의 핵심 로직:

1. 시작 노드를 큐에 넣고 방문 처리합니다.
2. 큐가 빌 때까지 다음 과정을 반복합니다:
a. 큐에서 노드를 꺼냅니다.
b. 꺼낸 노드의 인접한 노드 중 방문하지 않은 노드를 모두 큐에 넣고 방문 처리합니다.

#### BFS의 특징:

- 최단 경로 문제를 해결할 수 있습니다.
- 두 노드 사이의 최단 거리나 경로를 찾을 수 있습니다.
- 큐를 사용하여 구현합니다.
- 메모리를 많이 사용할 수 있습니다.

#### 예시 코드 (미로 탈출 최단 경로):

다음은 "미로 탈출" 문제를 BFS로 해결하는 예시 코드입니다:

struct Point {
    int x, y, dist;
};

vector<vector<int>> bfs(int startX, int startY, int exitX, int exitY) {
    queue<Point> q;
    vector<vector<int>> dist(N, vector<int>(M, -1));

    q.push({startX, startY, 0});
    dist[startX][startY] = 0;

    while (!q.empty()) {
        Point current = q.front();
        q.pop();

        if (current.x == exitX && current.y == exitY) {
            return dist;  // 출구에 도달
        }

        for (int i = 0; i < 4; i++) {
            int nx = current.x + dx[i];
            int ny = current.y + dy[i];

            if (nx >= 0 && nx < N && ny >= 0 && ny < M &&
                board[nx][ny] == 0 && dist[nx][ny] == -1) {
                dist[nx][ny] = current.dist + 1;
                q.push({nx, ny, current.dist + 1});
            }
        }
    }

    return dist;  // 출구에 도달하지 못한 경우
}

#### 기출 문제 예시 (정령 이동):

"정령 이동" 문제에서 BFS를 활용하여 정령의 이동 경로를 찾는 코드:

struct Spirit {
    int x, y, direction;
};

vector<vector<int>> findSpiritPath(int startX, int startY) {
    queue<Spirit> q;
    vector<vector<int>> visited(N, vector<int>(N, -1));

    q.push({startX, startY, 2});  // 2: 남쪽
    visited[startX][startY] = 0;

    while (!q.empty()) {
        Spirit current = q.front();
        q.pop();

        // 남쪽으로 이동 시도
        if (canMoveDown(current)) {
            int nx = current.x + 1;
            if (visited[nx][current.y] == -1) {
                visited[nx][current.y] = visited[current.x][current.y] + 1;
                q.push({nx, current.y, 2});
            }
        }
        // 서쪽으로 회전 시도
        else if (canRotateWest(current)) {
            int ny = current.y - 1;
            if (visited[current.x][ny] == -1) {
                visited[current.x][ny] = visited[current.x][current.y] + 1;
                q.push({current.x, ny, 3});
            }
        }
        // 동쪽으로 회전 시도
        else if (canRotateEast(current)) {
            int ny = current.y + 1;
            if (visited[current.x][ny] == -1) {
                visited[current.x][ny] = visited[current.x][current.y] + 1;
                q.push({current.x, ny, 1});
            }
        }
    }

    return visited;
}

이 코드는 정령의 이동 규칙을 BFS에 적용하여 모든 가능한 이동 경로를 탐색합니다.

### 2.2 DFS (깊이 우선 탐색)

DFS는 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. 시작 정점에서 다음 분기로 넘어가기 전에, 해당 분기를 완벽하게 탐색하는 방법입니다.

#### DFS의 핵심 로직:

1. 시작 노드를 스택에 넣고 방문 처리합니다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다.
3. 2번 과정을 스택이 빌 때까지 반복합니다.

#### DFS의 특징:

- 모든 노드를 방문하고자 할 때 사용합니다.
- 백트래킹에 사용됩니다.
- 스택 또는 재귀 함수를 이용하여 구현합니다.
- 메모리를 적게 사용하지만, 해가 없는 경로를 탐색할 때 시간이 오래 걸릴 수 있습니다.

#### 예시 코드 (연결된 구역 찾기):

int dfs(int x, int y, int& size) {
    visited[x][y] = true;
    size++;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx >= 0 && nx < N && ny >= 0 && ny < M &&
            !visited[nx][ny] && board[nx][ny] == board[x][y]) {
            dfs(nx, ny, size);
        }
    }

    return size;
}

int findLargestConnectedArea() {
    int maxSize = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!visited[i][j]) {
                int size = 0;
                maxSize = max(maxSize, dfs(i, j, size));
            }
        }
    }
    return maxSize;
}

#### 기출 문제 예시 (바닥 먼지 청소):

"바닥 먼지 청소" 문제에서 DFS를 활용하여 특정 구역의 먼지를 청소하는 코드:

int cleanDust(int x, int y) {
    if (x < 0 || x >= N || y < 0 || y >= N || board[x][y] == 0 || visited[x][y]) {
        return 0;
    }

    visited[x][y] = true;
    int dustAmount = board[x][y];
    board[x][y] = 0;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        dustAmount += cleanDust(nx, ny);
    }

    return dustAmount;
}

int cleanAllDust() {
    int totalDust = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (!visited[i][j] && board[i][j] > 0) {
                totalDust += cleanDust(i, j);
            }
        }
    }
    return totalDust;
}

이 코드는 DFS를 사용하여 연결된 먼지 영역을 찾고 청소하며, 청소한 먼지의 총량을 계산합니다.

### 2.3 다익스트라 알고리즘

다익스트라 알고리즘은 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 음의 가중치가 없는 그래프에서 사용할 수 있습니다.

#### 다익스트라 알고리즘의 핵심 로직:

1. 시작 정점을 선택하고, 시작 정점에서 다른 모든 정점까지의 거리를 무한대로 초기화합니다.
2. 시작 정점의 거리를 0으로 설정하고, 방문하지 않은 정점 중 가장 거리가 짧은 정점을 선택합니다.
3. 선택한 정점을 방문 처리하고, 이 정점을 거쳐 다른 정점으로 가는 거리가 기존에 알려진 거리보다 짧으면 거리를 갱신합니다.
4. 모든 정점을 방문할 때까지 2-3 과정을 반복합니다.

#### 다익스트라 알고리즘의 특징:

- 그리디 알고리즘의 일종입니다.
- 최단 경로를 구하는 데 사용됩니다.
- 우선순위 큐를 사용하여 효율적으로 구현할 수 있습니다.
- 음의 가중치가 있는 그래프에서는 사용할 수 없습니다.

#### 예시 코드 (최소 비용 경로 찾기):

struct Node {
    int x, y, cost;
    Node(int _x, int _y, int _cost) : x(_x), y(_y), cost(_cost) {}
};

struct compare {
    bool operator()(const Node& a, const Node& b) {
        return a.cost > b.cost;
    }
};

int dijkstra() {
    vector<vector<int>> dist(N, vector<int>(M, INF));
    priority_queue<Node, vector<Node>, compare> pq;

    dist[0][0] = board[0][0];
    pq.push(Node(0, 0, board[0][0]));

    while (!pq.empty()) {
        int x = pq.top().x;
        int y = pq.top().y;
        int cost = pq.top().cost;
        pq.pop();

        if (x == N-1 && y == M-1) return cost;

        if (cost > dist[x][y]) continue;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                int newCost = cost + board[nx][ny];
                if (newCost < dist[nx][ny]) {
                    dist[nx][ny] = newCost;
                    pq.push(Node(nx, ny, newCost));
                }
            }
        }
    }

    return -1;  // 도달할 수 없는 경우
}

#### 기출 문제 예시 (마법사 상어와 파이어스톰):

"마법사 상어와 파이어스톰" 문제에서 다익스트라 알고리즘을 활용하여 얼음이 녹는 최소 시간을 계산하는 코드:

struct Ice {
    int x, y, time;
    Ice(int _x, int _y, int _t) : x(_x), y(_y), time(_t) {}
};

struct compare {
    bool operator()(const Ice& a, const Ice& b) {
        return a.time > b.time;
    }
};

int meltIce() {
    vector<vector<int>> meltTime(N, vector<int>(N, INF));
    priority_queue<Ice, vector<Ice>, compare> pq;

    // 초기 얼음 위치 추가
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (board[i][j] > 0) {
                pq.push(Ice(i, j, 0));
                meltTime[i][j] = 0;
            }
        }
    }

    int lastMeltTime = 0;

    while (!pq.empty()) {
        int x = pq.top().x;
        int y = pq.top().y;
        int time = pq.top().time;
        pq.pop();

        if (time > meltTime[x][y]) continue;

        lastMeltTime = max(lastMeltTime, time);

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                int newTime = time + 1;
                if (newTime < meltTime[nx][ny]) {
                    meltTime[nx][ny] = newTime;
                    pq.push(Ice(nx, ny, newTime));
                }
            }
        }
    }

    return lastMeltTime;
}

이 코드는 다익스트라 알고리즘을 사용하여 각 얼음이 녹는 최소 시간을 계산하고, 모든 얼음이 녹는 데 걸리는 총 시간을 반환합니다.

### 2.4 브루트포스 (완전탐색)

브루트포스(Brute Force) 또는 완전탐색은 가능한 모든 경우의 수를 탐색하여 문제의 해를 찾는 방법입니다. 단순하지만 확실한 방법으로, 문제의 제약 조건이 작을 때 유용합니다.

#### 브루트포스의 핵심 로직:

1. 문제의 가능한 모든 경우의 수를 나열합니다.
2. 각 경우에 대해 문제의 조건을 만족하는지 확인합니다.
3. 조건을 만족하는 경우 중 가장 좋은 해를 선택합니다.

#### 브루트포스의 특징:

- 모든 경우를 고려하므로 항상 정확한 해를 찾을 수 있습니다.
- 문제의 크기가 작을 때 효과적입니다.
- 구현이 비교적 간단합니다.
- 문제의 크기가 커지면 시간 복잡도가 급격히 증가합니다.

#### 예시 코드 (최적의 포탑 위치 찾기):

int calculateScore(int x, int y) {
    int score = 0;
    for (int dir = 0; dir < 8; dir++) {
        int nx = x, ny = y;
        int dist = 0;
        while (true) {
            nx += dx[dir];
            ny += dy[dir];
            dist++;
            if (nx < 0 || nx >= N || ny < 0 || ny >= M) break;
            if (board[nx][ny] == 1) {
                score += dist;
                break;
            }
        }
    }
    return score;
}

int findOptimalTurretPosition() {
    int maxScore = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == 0) {  // 빈 칸인 경우
                int score = calculateScore(i, j);
                maxScore = max(maxScore, score);
            }
        }
    }

    return maxScore;
}

#### 기출 문제 예시 (마법사 상어와 복제):

"마법사 상어와 복제" 문제에서 브루트포스를 활용하여 상어의 최적 이동 경로를 찾는 코드:

int maxFishCaught = 0;
vector<int> bestPath;

void findBestPath(int x, int y, int moves, int fishCaught, vector<int>& path) {
    if (moves == 3) {
        if (fishCaught > maxFishCaught) {
            maxFishCaught = fishCaught;
            bestPath = path;
        }
        return;
    }

    for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4) {
            int caught = board[nx][ny];
            board[nx][ny] = 0;  // 물고기 잡기
            path.push_back(dir);

            findBestPath(nx, ny, moves + 1, fishCaught + caught, path);

            board[nx][ny] = caught;  // 물고기 되돌리기
            path.pop_back();
        }
    }
}

vector<int> findOptimalSharkPath(int startX, int startY) {
    vector<int> path;
    findBestPath(startX, startY, 0, 0, path);
    return bestPath;
}

이 코드는 상어의 모든 가능한 이동 경로를 탐색하여 가장 많은 물고기를 잡을 수 있는 경로를 찾습니다.

### 2.5 그리디 알고리즘

그리디 알고리즘은 각 단계에서 지역적으로 최적인 선택을 하는 방식으로 전체 문제의 최적해를 구하는 알고리즘입니다. 항상 최적해를 보장하지는 않지만, 계산 속도가 빠르고 구현이 간단합니다.

#### 그리디 알고리즘의 핵심 로직:

1. 현재 상황에서 가장 좋아 보이는 선택을 합니다.
2. 선택한 결과를 기반으로 문제를 축소합니다.
3. 축소된 문제에 대해 1-2 과정을 반복합니다.

#### 그리디 알고리즘의 특징:

- 각 단계에서 지역적으로 최적인 선택을 합니다.
- 일반적으로 빠른 실행 시간을 가집니다.
- 항상 최적해를 보장하지는 않습니다.
- 최적해를 구할 수 있는 경우, 증명이 필요합니다.

#### 예시 코드 (동전 거스름돈 문제):

int greedyCoinChange(int amount, vector<int>& coins) {
    sort(coins.rbegin(), coins.rend());  // 내림차순 정렬
    int coinCount = 0;
    
    for (int coin : coins) {
        while (amount >= coin) {
            amount -= coin;
            coinCount++;
        }
    }
    
    return coinCount;
}

#### 기출 문제 예시 (상어 중학교):

"상어 중학교" 문제에서 그리디 알고리즘을 활용하여 블록 그룹을 찾는 코드:

struct BlockGroup {
    int size;
    int rainbowCount;
    int standardX;
    int standardY;
};

BlockGroup findLargestBlockGroup() {
    BlockGroup largest = {0, 0, -1, -1};

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (board[i][j] > 0) {  // 일반 블록
                BlockGroup current = findGroup(i, j);
                if (isLarger(current, largest)) {
                    largest = current;
                }
            }
        }
    }

    return largest;
}

bool isLarger(const BlockGroup& a, const BlockGroup& b) {
    if (a.size != b.size) return a.size > b.size;
    if (a.rainbowCount != b.rainbowCount) return a.rainbowCount > b.rainbowCount;
    if (a.standardX != b.standardX) return a.standardX > b.standardX;
    return a.standardY > b.standardY;
}

BlockGroup findGroup(int x, int y) {
    int color = board[x][y];
    vector<vector<bool>> visited(N, vector<bool>(N, false));
    queue<pair<int, int>> q;
    BlockGroup group = {1, 0, x, y};

    q.push({x, y});
    visited[x][y] = true;

    while (!q.empty()) {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny]) {
                if (board[nx][ny] == color || board[nx][ny] == 0) {
                    visited[nx][ny] = true;
                    q.push({nx, ny});
                    group.size++;
                    if (board[nx][ny] == 0) group.rainbowCount++;
                    else if (nx < group.standardX || (nx == group.standardX && ny < group.standardY)) {
                        group.standardX = nx;
                        group.standardY = ny;
                    }
                }
            }
        }
    }

    return group;
}

이 코드는 그리디 방식으로 가장 큰 블록 그룹을 찾습니다. 각 단계에서 현재 가장 큰 그룹을 선택하는 방식으로 동작합니다.

### 2.6 우선순위 큐

우선순위 큐는 일반적인 큐와 달리 우선순위가 가장 높은 데이터가 먼저 나오는 자료구조입니다. 힙(Heap)을 이용하여 구현되며, 다익스트라 알고리즘, 프림 알고리즘 등 다양한 알고리즘에서 활용됩니다.

#### 우선순위 큐의 특징:

- 삽입과 삭제 연산의 시간 복잡도는 O(log N)입니다.
- 최대 힙 또는 최소 힙으로 구현할 수 있습니다.
- STL의 priority_queue를 사용하거나 직접 구현할 수 있습니다.

#### 예시 코드 (최소 힙):

#include <queue>
#include <vector>
#include <functional>

// 최소 힙
priority_queue<int, vector<int>, greater<int>> minHeap;

// 삽입
minHeap.push(5);
minHeap.push(2);
minHeap.push(8);

// 최솟값 추출
while (!minHeap.empty()) {
    cout << minHeap.top() << " ";
    minHeap.pop();
}
// 출력: 2 5 8

#### 기출 문제 예시 (마법사 상어와 파이어볼):

"마법사 상어와 파이어볼" 문제에서 우선순위 큐를 활용하여 파이어볼을 관리하는 코드:

struct Fireball {
    int r, c, m, s, d;
    Fireball(int r, int c, int m, int s, int d) : r(r), c(c), m(m), s(s), d(d) {}
};

struct CompareFireball {
    bool operator()(const Fireball& a, const Fireball& b) {
        if (a.r != b.r) return a.r > b.r;
        if (a.c != b.c) return a.c > b.c;
        return a.m < b.m;
    }
};

priority_queue<Fireball, vector<Fireball>, CompareFireball> pq;

void moveFireballs() {
    priority_queue<Fireball, vector<Fireball>, CompareFireball> nextPq;
    
    while (!pq.empty()) {
        Fireball fb = pq.top();
        pq.pop();
        
        int nr = (fb.r + dr[fb.d] * fb.s) % N;
        int nc = (fb.c + dc[fb.d] * fb.s) % N;
        if (nr < 0) nr += N;
        if (nc < 0) nc += N;
        
        nextPq.push(Fireball(nr, nc, fb.m, fb.s, fb.d));
    }
    
    pq = nextPq;
}

void combineFireballs() {
    vector<vector<vector<Fireball>>> grid(N, vector<vector<Fireball>>(N));
    
    while (!pq.empty()) {
        Fireball fb = pq.top();
        pq.pop();
        grid[fb.r][fb.c].push_back(fb);
    }
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j].size() >= 2) {
                int totalM = 0, totalS = 0;
                bool allEven = true, allOdd = true;
                for (Fireball& fb : grid[i][j]) {
                    totalM += fb.m;
                    totalS += fb.s;
                    if (fb.d % 2 == 0) allOdd = false;
                    else allEven = false;
                }
                
                int newM = totalM / 5;
                int newS = totalS / grid[i][j].size();
                
                if (newM > 0) {
                    for (int d = 0; d < 4; d++) {
                        int newD = (allEven || allOdd) ? d * 2 : d * 2 + 1;
                        pq.push(Fireball(i, j, newM, newS, newD));
                    }
                }
            } else if (grid[i][j].size() == 1) {
                pq.push(grid[i][j][0]);
            }
        }
    }
}

이 코드는 우선순위 큐를 사용하여 파이어볼을 위치와 질량에 따라 정렬하고 관리합니다. 파이어볼의 이동과 합체를 효율적으로 처리할 수 있습니다.

### 2.7 백트래킹

백트래킹은 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법입니다. 주로 최적화 문제와 결정 문제를 해결하는 데 사용됩니다.

#### 백트래킹의 핵심 로직:

1. 현재 상태에서 가능한 모든 후보군을 생성합니다.
2. 각 후보를 체크하여 해결책으로 가능한지 검사합니다.
3. 가능하다면 해당 후보를 선택하고 다음 단계로 진행합니다.
4. 해결책이 아니라면 이전 단계로 돌아갑니다.

#### 백트래킹의 특징:

- 가지치기(Pruning)를 통해 불필요한 경우를 제거합니다.
- DFS를 기반으로 하지만, 가지치기를 통해 효율성을 높입니다.
- 주로 재귀 함수로 구현합니다.

#### 예시 코드 (N-Queens 문제):

bool isSafe(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 solveNQueens(vector<int>& board, int row, int N) {
    if (row == N) {
        return true;
    }
    
    for (int col = 0; col < N; col++) {
        if (isSafe(board, row, col, N)) {
            board[row] = col;
            
            if (solveNQueens(board, row + 1, N)) {
                return true;
            }
            
            board[row] = -1;  // Backtrack
        }
    }
    
    return false;
}

#### 기출 문제 예시 (게리맨더링 2):

"게리맨더링 2" 문제에서 백트래킹을 활용하여 선거구를 나누는 코드:

int minDifference = INT_MAX;

void divideDistricts(int x, int y, int d1, int d2) {
    if (x + d1 + d2 >= N || y - d1 < 0 || y + d2 >= N) return;
    
    vector<vector<int>> districts(N, vector<int>(N, 5));
    vector<int> population(6, 0);
    
    // 경계선 그리기
    for (int i = 0; i <= d1; i++) {
        districts[x + i][y - i] = 5;
        districts[x + d2 + i][y + d2 - i] = 5;
    }
    for (int i = 0; i <= d2; i++) {
        districts[x + i][y + i] = 5;
        districts[x + d1 + i][y - d1 + i] = 5;
    }
    
    // 1번 선거구
    for (int r = 0; r < x + d1; r++) {
        for (int c = 0; c <= y; c++) {
            if (districts[r][c] == 5) break;
            districts[r][c] = 1;
        }
    }
    
    // 2번 선거구
    for (int r = 0; r <= x + d2; r++) {
        for (int c = N - 1; c > y; c--) {
            if (districts[r][c] == 5) break;
            districts[r][c] = 2;
        }
    }
    
    // 3번 선거구
    for (int r = x + d1; r < N; r++) {
        for (int c = 0; c < y - d1 + d2; c++) {
            if (districts[r][c] == 5) break;
            districts[r][c] = 3;
        }
    }
    
    // 4번 선거구
    for (int r = x + d2 + 1; r < N; r++) {
        for (int c = N - 1; c >= y - d1 + d2; c--) {
            if (districts[r][c] == 5) break;
            districts[r][c] = 4;
        }
    }
    
    // 인구 계산
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            population[districts[r][c]] += board[r][c];
        }
    }
    
    int maxPop = *max_element(population.begin() + 1, population.end());
    int minPop = *min_element(population.begin() + 1, population.end());
    
    minDifference = min(minDifference, maxPop - minPop);
}

void backtrack() {
    for (int x = 0; x < N - 2; x++) {
        for (int y = 1; y < N - 1; y++) {
            for (int d1 = 1; y - d1 >= 0; d1++) {
                for (int d2 = 1; y + d2 < N && x + d1 + d2 < N; d2++) {
                    divideDistricts(x, y, d1, d2);
                }
            }
        }
    }
}

이 코드는 백트래킹을 사용하여 모든 가능한 선거구 분할을 탐색하고, 인구 차이가 가장 작은 경우를 찾습니다.

## 3. 특수 알고리즘

### 3.1 투 포인터

투 포인터 알고리즘은 두 개의 포인터를 이용해 배열이나 리스트를 순차적으로 탐색하는 알고리즘입니다. 주로 연속된 구간에 대한 문제를 해결할 때 사용됩니다.

#### 투 포인터의 핵심 로직:

1. 시작점과 끝점을 가리키는 두 개의 포인터를 사용합니다.
2. 문제의 조건에 따라 포인터를 이동시킵니다.
3. 포인터가 배열의 끝에 도달하면 알고리즘을 종료합니다.

#### 예시 코드 (부분합이 S인 연속된 수열 찾기):

int twoPointers(vector<int>& arr, int S) {
    int n = arr.size();
    int start = 0, end = 0;
    int sum = 0, minLen = INT_MAX;

    while (end < n) {
        while (sum < S && end < n) {
            sum += arr[end++];
        }
        
        while (sum >= S && start < n) {
            minLen = min(minLen, end - start);
            sum -= arr[start++];
        }
    }

    return minLen == INT_MAX ? 0 : minLen;
}

#### 기출 문제 예시 (어항 정리):

"어항 정리" 문제에서 투 포인터를 활용하여 물고기를 재분배하는 코드:

void redistributeFish() {
    int left = 0, right = N - 1;
    
    while (left < right) {
        int diff = abs(fishbowls[left] - fishbowls[right]);
        int move = diff / 5;
        
        if (fishbowls[left] < fishbowls[right]) {
            fishbowls[left] += move;
            fishbowls[right] -= move;
        } else {
            fishbowls[left] -= move;
            fishbowls[right] += move;
        }
        
        left++;
        right--;
    }
}

이 코드는 두 개의 포인터를 사용하여 양 끝의 어항부터 물고기를 재분배합니다.

### 3.2 비트마스킹

비트마스킹은 정수의 이진수 표현을 자료구조로 사용하는 기법입니다. 집합을 표현하거나 상태를 나타내는 데 효율적으로 사용될 수 있습니다.

#### 비트마스킹의 특징:

- 메모리 사용량을 줄일 수 있습니다.
- 빠른 집합 연산이 가능합니다.
- 코드가 간결해질 수 있습니다.

#### 예시 코드 (부분집합 생성):

void generateSubsets(int n) {
    for (int i = 0; i < (1 << n); i++) {
        cout << "Subset " << i << ": ";
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                cout << j << " ";
            }
        }
        cout << endl;
    }
}

#### 기출 문제 예시 (마법사 상어와 비바라기):

"마법사 상어와 비바라기" 문제에서 비트마스킹을 활용하여 구름의 상태를 관리하는 코드:

const int MAX_N = 50;
int N, M;
int board[MAX_N][MAX_N];
int clouds = 0;  // 비트마스크로 구름 상태 표현

void moveAndRain(int d, int s) {
    int newClouds = 0;
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (clouds & (1 << (i * N + j))) {
                int ni = (i + dy[d] * s + N * 50) % N;
                int nj = (j + dx[d] * s + N * 50) % N;
                newClouds |= (1 << (ni * N + nj));
                board[ni][nj]++;
            }
        }
    }
    
    clouds = newClouds;
}

void waterCopy() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (clouds & (1 << (i * N + j))) {
                int count = 0;
                for (int k = 1; k < 8; k += 2) {
                    int ni = i + dy[k];
                    int nj = j + dx[k];
                    if (ni >= 0 && ni < N && nj >= 0 && nj < N && board[ni][nj] > 0) {
                        count++;
                    }
                }
                board[i][j] += count;
            }
        }
    }
}

void createNewClouds() {
    int newClouds = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (!(clouds & (1 << (i * N + j))) && board[i][j] >= 2) {
                newClouds |= (1 << (i * N + j));
                board[i][j] -= 2;
            }
        }
    }
    clouds = newClouds;
}

이 코드는 비트마스킹을 사용하여 구름의 상태를 효율적으로 관리합니다. 각 비트는 해당 위치에 구름이 있는지 여부를 나타냅니다.

### 3.3 분리 집합 (Union-Find)

분리 집합(Disjoint Set)은 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조입니다. Union-Find 알고리즘을 통해 구현됩니다.

#### 분리 집합의 핵심 연산:

1. Find: 어떤 원소가 주어졌을 때, 이 원소가 속한 집합을 찾습니다.
2. Union: 두 개의 집합을 하나로 합칩니다.

#### 예시 코드:

vector<int> parent;

int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) parent[b] = a;
}

// 초기화
void init(int n) {
    parent.resize(n);
    for (int i = 0; i < n; i++) parent[i] = i;
}

#### 기출 문제 예시 (나무 재테크):

"나무 재테크" 문제에서 분리 집합을 활용하여 나무들의 그룹을 관리하는 코드:

struct Tree {
    int x, y, age;
    Tree(int x, int y, int age) : x(x), y(y), age(age) {}
};

vector<int> parent;
vector<Tree> trees;

int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) parent[b] = a;
}

void springAndSummer() {
    vector<int> deadTrees;
    for (int i = 0; i < trees.size(); i++) {
        int x = trees[i].x, y = trees[i].y;
        if (nutrients[x][y] >= trees[i].age) {
            nutrients[x][y] -= trees[i].age;
            trees[i].age++;
            // 나무가 자란 후 인접한 나무들과 그룹화
            for (int d = 0; d < 8; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                    for (int j = 0; j < trees.size(); j++) {
                        if (trees[j].x == nx && trees[j].y == ny) {
                            unite(i, j);
                            break;
                        }
                    }
                }
            }
        } else {
            deadTrees.push_back(i);
        }
    }
    
    // 여름: 죽은 나무 처리
    for (int i : deadTrees) {
        int x = trees[i].x, y = trees[i].y;
        nutrients[x][y] += trees[i].age / 2;
    }
    
    // 죽은 나무 제거
    for (int i = deadTrees.size() - 1; i >= 0; i--) {
        trees.erase(trees.begin() + deadTrees[i]);
    }
}

이 코드는 분리 집합을 사용하여 인접한 나무들을 그룹화하고, 각 그룹별로 나무의 성장과 번식을 관리합니다.

### 3.4 회전 알고리즘

회전 알고리즘은 2차원 배열이나 행렬을 회전시키는 알고리즘입니다. 주로 90도, 180도, 270도 회전이 많이 사용됩니다.

#### 회전 알고리즘의 핵심 로직:

1. 새로운 2차원 배열을 생성합니다.
2. 원본 배열의 각 요소를 새 배열의 적절한 위치로 이동시킵니다.
3. 필요한 경우 원본 배열을 새 배열로 교체합니다.

#### 예시 코드 (90도 시계 방향 회전):

vector<vector<int>> rotate90Clockwise(vector<vector<int>>& matrix) {
    int n = matrix.size();
    vector<vector<int>> rotated(n, vector<int>(n));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            rotated[j][n-1-i] = matrix[i][j];
        }
    }
    
    return rotated;
}

#### 기출 문제 예시 (모노미노도미노):

"모노미노도미노" 문제에서 블록을 회전시키는 코드:

void rotateBlock(vector<pair<int, int>>& block) {
    int maxX = 0, maxY = 0;
    for (auto& p : block) {
        maxX = max(maxX, p.first);
        maxY = max(maxY, p.second);
    }
    
    for (auto& p : block) {
        int temp = p.first;
        p.first = p.second;
        p.second = maxX - temp;
    }
}

void placeBlock(vector<pair<int, int>>& block, int board[10][4]) {
    int lowestY = 10;
    for (auto& p : block) {
        for (int y = 0; y < 10; y++) {
            if (y == 9 || board[y + 1][p.first] != 0) {
                lowestY = min(lowestY, y - p.second);
                break;
            }
        }
    }
    
    for (auto& p : block) {
        board[lowestY + p.second][p.first] = 1;
    }
}

int playGame(vector<vector<pair<int, int>>>& blocks) {
    int score = 0;
    int board[10][4] = {0};
    
    for (auto& block : blocks) {
        placeBlock(block, board);
        
        // 행이 가득 찼는지 확인
        for (int y = 9; y >= 0; y--) {
            if (board[y][0] && board[y][1] && board[y][2] && board[y][3]) {
                score++;
                for (int ny = y; ny > 0; ny--) {
                    for (int x = 0; x < 4; x++) {
                        board[ny][x] = board[ny-1][x];
                    }
                }
                for (int x = 0; x < 4; x++) board[0][x] = 0;
                y++;  // 한 행을 제거했으므로 같은 y를 다시 검사
            }
        }
        
        // 상위 두 행 확인
        int overflow = 0;
        for (int y = 0; y < 2; y++) {
            for (int x = 0; x < 4; x++) {
                if (board[y][x]) {
                    overflow++;
                    break;
                }
            }
        }
        
        // 넘친 만큼 아래로 밀기
        for (int y = 9; y >= 2; y--) {
            for (int x = 0; x < 4; x++) {
                board[y][x] = board[y - overflow][x];
            }
        }
        for (int y = 0; y < 2; y++) {
            for (int x = 0; x < 4; x++) {
                board[y][x] = 0;
            }
        }
    }
    
    return score;
}

이 코드는 블록을 회전시키고 게임 보드에 배치하는 과정을 구현합니다. 회전 알고리즘을 사용하여 블록의 방향을 변경하고, 행이 가득 찼을 때 점수를 얻고 행을 제거하는 로직을 포함합니다.

## 4. 시뮬레이션 로직

시뮬레이션은 주어진 규칙에 따라 상태를 변화시키며 문제를 해결하는 방법입니다. 삼성 DS 코딩테스트에서 매우 중요한 부분입니다.

#### 시뮬레이션의 핵심 로직:

1. 초기 상태를 설정합니다.
2. 주어진 규칙에 따라 상태를 변화시킵니다.
3. 종료 조건을 확인합니다.
4. 필요한 경우 결과를 계산하거나 출력합니다.

#### 예시 코드 (간단한 생명 게임 시뮬레이션):

vector<vector<int>> simulateLifeGame(vector<vector<int>>& board) {
    int n = board.size(), m = board[0].size();
    vector<vector<int>> newBoard(n, vector<int>(m));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int liveNeighbors = countLiveNeighbors(board, i, j);
            if (board[i][j] == 1) {
                newBoard[i][j] = (liveNeighbors == 2 || liveNeighbors == 3) ? 1 : 0;
            } else {
                newBoard[i][j] = (liveNeighbors == 3) ? 1 : 0;
            }
        }
    }
    
    return newBoard;
}

int countLiveNeighbors(vector<vector<int>>& board, int x, int y) {
    int count = 0;
    for (int i = -1; i <= 1; i++) {
        for (int j = -1; j <= 1; j++) {
            if (i == 0 && j == 0) continue;
            int nx = x + i, ny = y + j;
            if (nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size()) {
                count += board[nx][ny];
            }
        }
    }
    return count;
}

#### 기출 문제 예시 (아기 상어):

"아기 상어" 문제에서 시뮬레이션을 활용한 코드:

struct Shark {
    int x, y, size, eat;
};

int N;
vector<vector<int>> board;
Shark shark;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

int bfs() {
    vector<vector<int>> dist(N, vector<int>(N, -1));
    queue<pair<int, int>> q;
    vector<pair<int, int>> fishes;
    int minDist = INT_MAX;
    
    q.push({shark.x, shark.y});
    dist[shark.x][shark.y] = 0;
    
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        if (dist[x][y] > minDist) break;
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if (dist[nx][ny] != -1 || board[nx][ny] > shark.size) continue;
            
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});

            if (board[nx][ny] > 0 && board[nx][ny] < shark.size) {
                if (dist[nx][ny] < minDist) {
                    minDist = dist[nx][ny];
                    fishes.clear();
                    fishes.push_back({nx, ny});
                } else if (dist[nx][ny] == minDist) {
                    fishes.push_back({nx, ny});
                }
            }
        }
    }
    
    if (fishes.empty()) return 0;
    
    sort(fishes.begin(), fishes.end());
    int fx = fishes[0].first, fy = fishes[0].second;
    
    shark.x = fx;
    shark.y = fy;
    shark.eat++;
    if (shark.eat == shark.size) {
        shark.size++;
        shark.eat = 0;
    }
    
    board[fx][fy] = 0;
    
    return minDist;
}

int simulate() {
    int time = 0;
    while (true) {
        int moveTime = bfs();
        if (moveTime == 0) break;
        time += moveTime;
    }
    return time;
}

이 코드는 아기 상어의 움직임을 시뮬레이션합니다. BFS를 사용하여 가장 가까운 먹을 수 있는 물고기를 찾고, 상어를 이동시키며 크기를 키우는 과정을 구현합니다.

## 5. 자주 사용되는 테크닉

### 5.1 회전

회전은 2차원 배열을 다룰 때 자주 사용되는 테크닉입니다. ZIP 함수를 활용하거나 인덱스 규칙을 찾아 구현할 수 있습니다.

#### 5.1.1 ZIP을 활용한 회전 (Python):

arr = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]

# 시계 방향 90도 (= 반시계 방향 270도)
arr_90 = list(map(list, zip(*arr[::-1])))
print(arr_90)

# 시계 방향 180도 (= 반시계 방향 180도)
arr_180 = [a[::-1] for a in arr[::-1]]
print(arr_180)

# 시계 방향 270도 (= 반시계 방향 90도)
arr_270 = [x[::-1] for x in list(map(list, zip(*arr[::-1])))[::-1]]
print(arr_270)

이 방법의 장점:
- 생각하기 쉽고 빠르게 구현할 수 있습니다.
- 정사각형이 아닌 직사각형의 경우에도 배열의 인덱스 고민 없이 빠르게 처리할 수 있습니다.

단점:
- 메모리나 시간 복잡도 면에서는 인덱스 규칙을 사용한 방법보다 좋지 않을 수 있습니다.

#### 5.1.2 인덱스 규칙을 이용한 회전 (C++):

vector<vector<int>> rotate90(vector<vector<int>>& arr) {
    int n = arr.size();
    int m = arr[0].size();
    vector<vector<int>> result(m, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            result[j][n-1-i] = arr[i][j];
        }
    }
    return result;
}

vector<vector<int>> rotate180(vector<vector<int>>& arr) {
    int n = arr.size();
    int m = arr[0].size();
    vector<vector<int>> result(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            result[n-1-i][m-1-j] = arr[i][j];
        }
    }
    return result;
}

vector<vector<int>> rotate270(vector<vector<int>>& arr) {
    int n = arr.size();
    int m = arr[0].size();
    vector<vector<int>> result(m, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            result[m-1-j][i] = arr[i][j];
        }
    }
    return result;
}

이 방법의 장점:
- 메모리와 시간 복잡도 면에서 효율적입니다.
- 직사각형 배열에 대해서도 쉽게 적용할 수 있습니다.

주의할 점:
- 회전 후 배열의 크기가 변할 수 있으므로, 결과 배열의 크기를 올바르게 설정해야 합니다.

### 5.2 순열, 중복 순열, 조합, 중복 조합

순열과 조합은 백트래킹을 이용해 구현할 수 있습니다. 삼성 코딩테스트에서는 itertools 라이브러리 사용이 불가능하므로, 직접 구현해야 합니다.

#### 5.2.1 순열 (Permutations):

vector<int> arr = {1, 2, 3, 4};
vector<bool> visited(arr.size(), false);

void permutations(int n, vector<int>& current) {
    if (current.size() == n) {
        // 순열 완성, 처리 로직
        return;
    }
    for (int i = 0; i < arr.size(); i++) {
        if (!visited[i]) {
            visited[i] = true;
            current.push_back(arr[i]);
            permutations(n, current);
            current.pop_back();
            visited[i] = false;
        }
    }
}

// 사용 예: vector<int> current; permutations(2, current);

특징:
- 순서를 고려하며, 중복을 허용하지 않습니다.
- visited 배열을 사용하여 중복 선택을 방지합니다.

#### 5.2.2 중복 순열 (Product):

void product(int n, vector<int>& current) {
    if (current.size() == n) {
        // 중복 순열 완성, 처리 로직
        return;
    }
    for (int i = 0; i < arr.size(); i++) {
        current.push_back(arr[i]);
        product(n, current);
        current.pop_back();
    }
}

// 사용 예: vector<int> current; product(2, current);

특징:
- 순서를 고려하며, 중복을 허용합니다.
- visited 배열을 사용하지 않아 같은 원소를 여러 번 선택할 수 있습니다.

#### 5.2.3 조합 (Combinations):

void combinations(int n, vector<int>& current, int start) {
    if (current.size() == n) {
        // 조합 완성, 처리 로직
        return;
    }
    for (int i = start; i < arr.size(); i++) {
        current.push_back(arr[i]);
        combinations(n, current, i + 1);
        current.pop_back();
    }
}

// 사용 예: vector<int> current; combinations(2, current, 0);

특징:
- 순서를 고려하지 않으며, 중복을 허용하지 않습니다.
- start 인덱스를 사용하여 이전에 선택한 원소 이후의 원소만 고려합니다.

#### 5.2.4 중복 조합 (Combinations with replacement):

void combinationsWithReplacement(int n, vector<int>& current, int start) {
    if (current.size() == n) {
        // 중복 조합 완성, 처리 로직
        return;
    }
    for (int i = start; i < arr.size(); i++) {
        current.push_back(arr[i]);
        combinationsWithReplacement(n, current, i);  // 다음 재귀에서도 현재 인덱스부터 시작
        current.pop_back();
    }
}

// 사용 예: vector<int> current; combinationsWithReplacement(2, current, 0);

특징:
- 순서를 고려하지 않으며, 중복을 허용합니다.
- 현재 인덱스부터 다시 시작하여 같은 원소를 여러 번 선택할 수 있습니다.

### 5.3 중력

중력 효과를 구현할 때는 아래에서부터 위로 올라가며 처리하는 것이 효율적입니다.

void applyGravity(vector<vector<int>>& board) {
    int n = board.size();
    int m = board[0].size();
    
    for (int j = 0; j < m; j++) {
        int bottom = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            if (board[i][j] != 0) {
                swap(board[bottom][j], board[i][j]);
                bottom--;
            }
        }
    }
}

특징:
- 각 열에 대해 아래에서부터 위로 올라가며 처리합니다.
- 0이 아닌 값을 만나면 가장 아래쪽으로 이동시킵니다.
- 이 방식은 "떨어지는" 효과를 효율적으로 구현합니다.

### 5.4 달팽이(나선형) 배열

달팽이 배열은 2차원 배열을 나선형으로 순회하는 패턴입니다.

vector<vector<int>> createSpiralArray(int n) {
    vector<vector<int>> arr(n, vector<int>(n, 0));
    int value = 1;
    int top = 0, bottom = n - 1, left = 0, right = n - 1;

    while (value <= n * n) {
        for (int i = left; i <= right; i++)
            arr[top][i] = value++;
        top++;

        for (int i = top; i <= bottom; i++)
            arr[i][right] = value++;
        right--;

        if (top <= bottom) {
            for (int i = right; i >= left; i--)
                arr[bottom][i] = value++;
            bottom--;
        }

        if (left <= right) {
            for (int i = bottom; i >= top; i--)
                arr[i][left] = value++;
            left++;
        }
    }

    return arr;
}

특징:
- 4개의 변수(top, bottom, left, right)를 사용하여 현재 채워야 할 영역의 경계를 관리합니다.
- 각 반복에서 한 변을 채우고 경계를 조정합니다.
- 안쪽으로 좁혀가며 모든 칸을 채웁니다.

### 5.5 이동 중 벽에 부딪혀서 방향이 전환되는 경우

물체가 이동하다 벽에 부딪혀 방향을 바꾸는 경우, 다음과 같이 구현할 수 있습니다:

void move(int& x, int& y, int& dx, int& dy, int n, int m) {
    x += dx;
    y += dy;
    
    if (x < 0 || x >= n || y < 0 || y >= m) {
        // 벽에 부딪힌 경우
        x -= dx;
        y -= dy;
        dx = -dx;
        dy = -dy;
    }
}

// 사용 예
int x = 0, y = 0;
int dx = 1, dy = 1;  // 초기 이동 방향
int n = 10, m = 10;  // 보드의 크기

for (int i = 0; i < 20; i++) {
    move(x, y, dx, dy, n, m);
    cout << "Position: (" << x << ", " << y << ")" << endl;
}

특징:
- 물체의 새 위치를 계산한 후, 벽과의 충돌 여부를 확인합니다.
- 충돌 시 이전 위치로 되돌리고 방향을 반대로 바꿉니다.
- 이 방식은 "튕기는" 효과를 간단히 구현할 수 있습니다.

### 5.6 배열 한 칸씩 돌리기

배열을 한 칸씩 돌리는 경우, 다음과 같이 구현할 수 있습니다:

void rotateArrayOneStep(vector<int>& arr, bool clockwise = true) {
    if (clockwise) {
        int temp = arr.back();
        for (int i = arr.size() - 1; i > 0; i--) {
            arr[i] = arr[i-1];
        }
        arr[0] = temp;
    } else {
        int temp = arr[0];
        for (int i = 0; i < arr.size() - 1; i++) {
            arr[i] = arr[i+1];
        }
        arr.back() = temp;
    }
}

// 2D 배열의 특정 행 또는 열 회전
void rotate2DArrayPart(vector<vector<int>>& arr, int index, bool isRow, bool clockwise = true) {
    if (isRow) {
        rotateArrayOneStep(arr[index], clockwise);
    } else {
        vector<int> column;
        for (int i = 0; i < arr.size(); i++) {
            column.push_back(arr[i][index]);
        }
        rotateArrayOneStep(column, clockwise);
        for (int i = 0; i < arr.size(); i++) {
            arr[i][index] = column[i];
        }
    }
}

특징:
- 1차원 배열 회전은 마지막(또는 첫) 요소를 임시 저장하고 나머지를 이동시킨 후 저장된 요소를 넣는 방식으로 구현합니다.
- 2D 배열의 특정 행이나 열 회전은 해당 부분을 1차원 배열로 추출하여 회전한 후 다시 넣는 방식으로 구현합니다.
- clockwise 매개변수를 통해 시계 방향 또는 반시계 방향 회전을 선택할 수 있습니다.
- 이 방법은 배열의 일부분만 회전해야 하는 경우에 유용합니다.

### 5.7 부분 회전

부분 회전은 2차원 배열의 특정 부분만 회전시키는 기법입니다. 이 기법은 단계별로 구현하는 것이 중요합니다.

void rotatePartial90(vector<vector<int>>& arr, int sy, int sx, int size) {
    vector<vector<int>> temp(size, vector<int>(size));
    
    // 1단계: 부분 배열을 임시 배열로 복사
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            temp[i][j] = arr[sy+i][sx+j];
        }
    }
    
    // 2단계: 90도 회전
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            arr[sy+j][sx+size-1-i] = temp[i][j];
        }
    }
}

// 사용 예
vector<vector<int>> board = {{1, 2, 3, 4},
                             {5, 6, 7, 8},
                             {9, 10, 11, 12},
                             {13, 14, 15, 16}};
rotatePartial90(board, 1, 1, 2);  // (1,1)부터 2x2 크기의 부분을 90도 회전

특징:
- 회전할 부분을 임시 배열로 복사한 후 회전시킵니다.
- 이 방법은 배열의 일부분만 회전해야 하는 경우에 유용합니다.
- 회전의 중심점과 크기를 지정할 수 있어 유연하게 사용할 수 있습니다.

### 5.8 토네이도 (나선형) 이동

토네이도 패턴은 중앙에서 시작하여 나선형으로 이동하는 패턴입니다. 이는 "마법사 상어와 토네이도" 같은 문제에서 자주 사용됩니다.

vector<pair<int, int>> tornadoPattern(int n) {
    vector<pair<int, int>> pattern;
    int x = n/2, y = n/2;
    int dx[] = {0, 1, 0, -1};  // 좌, 하, 우, 상 순서
    int dy[] = {-1, 0, 1, 0};
    int dir = 0;
    int moveCount = 0;
    int moveDistance = 1;

    pattern.push_back({x, y});

    while (true) {
        for (int i = 0; i < moveDistance; i++) {
            x += dx[dir];
            y += dy[dir];
            if (x < 0 || y < 0) return pattern;
            pattern.push_back({x, y});
        }

        dir = (dir + 1) % 4;
        moveCount++;

        if (moveCount == 2) {
            moveDistance++;
            moveCount = 0;
        }
    }
}

// 사용 예
vector<pair<int, int>> tornado = tornadoPattern(5);
for (auto& p : tornado) {
    cout << "(" << p.first << ", " << p.second << ") ";
}

특징:
- 중앙에서 시작하여 반시계 방향으로 나선형 이동 패턴을 생성합니다.
- 이동 거리가 2번마다 1씩 증가합니다.
- 격자 밖으로 나가면 패턴 생성을 종료합니다.

### 5.9 격자 밖으로 나가는 경우 처리

격자 기반 문제에서 객체가 격자 밖으로 나가는 경우, 반대편으로 이동하거나 방향을 바꾸는 등의 처리가 필요할 수 있습니다.

pair<int, int> wrapAround(int x, int y, int n) {
    x = (x + n) % n;
    y = (y + n) % n;
    return {x, y};
}

pair<int, int> bounce(int x, int y, int& dx, int& dy, int n) {
    if (x < 0 || x >= n) {
        dx = -dx;
        x = max(0, min(x, n-1));
    }
    if (y < 0 || y >= n) {
        dy = -dy;
        y = max(0, min(y, n-1));
    }
    return {x, y};
}

// 사용 예
int n = 5;
int x = 4, y = 4, dx = 1, dy = 1;

// 반대편으로 이동
auto [nx, ny] = wrapAround(x + dx, y + dy, n);
cout << "Wrap around: (" << nx << ", " << ny << ")" << endl;

// 방향 전환
tie(x, y) = bounce(x + dx, y + dy, dx, dy, n);
cout << "Bounce: (" << x << ", " << y << "), New direction: (" << dx << ", " << dy << ")" << endl;

특징:
- `wrapAround` 함수는 객체가 격자 밖으로 나갔을 때 반대편으로 이동시킵니다.
- `bounce` 함수는 객체가 격자 경계에 부딪혔을 때 방향을 바꾸고 위치를 조정합니다.
- 이러한 함수들은 다양한 시뮬레이션 문제에서 유용하게 사용될 수 있습니다.

### 5.10 2차원 누적 합 (2D Prefix Sum)

2차원 배열에서 특정 직사각형 영역의 합을 빠르게 계산해야 하는 경우, 2차원 누적 합을 사용할 수 있습니다.

vector<vector<int>> calculatePrefixSum2D(const vector<vector<int>>& arr) {
    int n = arr.size();
    int m = arr[0].size();
    vector<vector<int>> prefixSum(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            prefixSum[i][j] = arr[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];
        }
    }

    return prefixSum;
}

int getSum(const vector<vector<int>>& prefixSum, int x1, int y1, int x2, int y2) {
    return prefixSum[x2+1][y2+1] - prefixSum[x1][y2+1] - prefixSum[x2+1][y1] + prefixSum[x1][y1];
}

// 사용 예
vector<vector<int>> arr = {{1, 2, 3},
                           {4, 5, 6},
                           {7, 8, 9}};
auto prefixSum = calculatePrefixSum2D(arr);
cout << "Sum of rectangle (0,0) to (1,1): " << getSum(prefixSum, 0, 0, 1, 1) << endl;

특징:
- 전처리를 통해 누적 합 배열을 계산합니다.
- 이후 어떤 직사각형 영역의 합도 O(1) 시간에 계산할 수 있습니다.
- 특정 영역의 합을 자주 계산해야 하는 문제에서 유용합니다.

네, 이 내용을 전략서에 추가하기 위해 다음과 같이 정리할 수 있습니다:

### 5.11 C++에서 배열을 함수 매개변수로 사용하기

C++에서 배열을 함수의 매개변수로 사용할 때는 몇 가지 주의해야 할 점이 있습니다. 이를 이해하고 올바르게 사용하면 코딩 테스트에서 더 효율적이고 안전한 코드를 작성할 수 있습니다.

#### 5.11.1 배열 전달 메커니즘

C++에서 배열을 함수에 전달할 때, 배열의 첫 번째 요소의 메모리 주소가 전달됩니다. 이는 다음과 같은 특성을 가집니다:

- 배열 전체가 복사되지 않아 메모리 효율적입니다.
- 함수 내에서 원본 배열을 직접 수정할 수 있습니다.

void processArray(int arr[]) {
    // arr은 배열의 첫 번째 요소를 가리키는 포인터입니다.
}

#### 5.11.2 배열 크기 전달의 필요성

배열을 함수에 전달할 때는 배열의 크기도 함께 전달해야 합니다. 이는 다음과 같은 이유 때문입니다:

- C++에서 배열은 자체 크기 정보를 가지고 있지 않습니다.
- 함수 내에서 배열의 크기를 알아야 올바른 처리가 가능합니다.

void printArray(int arr[], size_t size) {
    for (size_t i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// 사용 예
int myArray[] = {1, 2, 3, 4, 5};
printArray(myArray, 5);

배열의 크기를 계산하는 일반적인 방법:

int size = sizeof(arr) / sizeof(arr[0]);

#### 5.11.3 원본 배열 보호

함수 내에서 원본 배열을 수정하지 않도록 하려면 `const` 키워드를 사용합니다:

void printArray(const int arr[], size_t size) {
    for (size_t i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    // arr[0] = 0;  // 컴파일 에러: const 배열은 수정할 수 없습니다.
}

#### 5.11.4 주요 포인트 요약

1. 배열을 함수에 전달할 때는 배열의 첫 번째 요소의 주소가 전달됩니다.
2. 배열의 크기를 함께 전달하여 함수 내에서 올바르게 처리할 수 있도록 합니다.
3. 함수 내에서 배열을 직접 수정할 수 있으므로, 원본 보호가 필요한 경우 `const` 키워드를 사용합니다.
4. 배열 크기 계산 시 `sizeof(arr) / sizeof(arr[0])` 공식을 활용할 수 있습니다.

이러한 배열 처리 기법을 잘 활용하면 코딩 테스트에서 더 효율적이고 안전한 코드를 작성할 수 있습니다.