문제 분석 및 풀이

설계 분석

• 자주 변경되는 데이터에 맞는 자료구조가 세그먼트 트리임을 알면 쉽게 접근할 수 있는 문제
• 여기서는 짝수의 개수 혹은 홀수의 개수를 세그먼트 트리로 관리하면 $O(logN)$으로 구할 수 있음.

• $O(logM)$

풀이

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 100001;
// 홀수만 저장하는 세그먼트 트리
int oddSegTree[4 * MAX];
// 실제 수열에 홀수가 있는지 짝수가 있는지 저장하는 배열
// 0이면 짝수 1이면 홀수
int seqArr[MAX];
int N, M;

void UpdateTree(int node, int left, int right, int idx, int diff)
{
    if (left > idx || idx > right) return;
    oddSegTree[node] += diff;
    if (left == right) return;

    int mid = (left + right) / 2;
    UpdateTree(node * 2, left, mid, idx, diff);
    UpdateTree(node * 2 + 1, mid+1, right, idx, diff);
}

// [targetLeft, targetRight] 범위의 합을 구하는 함수
int query(int node, int left, int right, int targetLeft, int targetRight)
{
    if (targetLeft <= left && right <= targetRight) return oddSegTree[node];
    if (targetLeft > right || left > targetRight) return 0;

    int mid = (left + right) / 2;
    return query(node * 2, left, mid , targetLeft, targetRight)
    + query(node * 2 + 1, mid + 1, right, targetLeft, targetRight);
}

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

    cin >> N;

    for (int i=1; i<=N; i++)
    {
        int inval;
        cin >> inval;
        // 홀수인 경우 트리 갱신
        if (inval % 2 != 0)
        {
            seqArr[i] = 1;
            UpdateTree(1,1,N,i,1); 
        }
    }

    cin >> M;

    for (int i=0; i<M; i++)
    {
        int cmd, a, b;
        cin >> cmd;
        if (cmd == 1)
        {
            // a위치의 값을 b로 바꾼다.
            cin >> a >> b;
            // a위치에 있던값이 짝수이고 바뀔 값이 홀수
            if (seqArr[a] == 0 && b % 2 != 0)
            {
                // 홀수로 바꾸기
                seqArr[a] = 1;
                // 홀수의 개수 +1
                UpdateTree(1,1,N,a,1); 
            }
            // a위치에 있던값이 홀수이고 바뀔 값이 짝수
            else if (seqArr[a] == 1 && b % 2 == 0)
            {
                // 짝수로 바꾸기
                seqArr[a] = 0;
                // 홀수의 개수 -1
                UpdateTree(1,1,N,a,-1); 
            }
        }
        else if (cmd == 2)
        {
            // [a,b]의 짝수 개수 출력
            // 홀수 개수 구해서 빼기
            cin >> a >> b;
            cout << (b-a + 1) - query(1,1,N,a,b) << "\n";
        }
        else if (cmd == 3)
        {
            // [a,b]의 홀수 개수 출력
            cin >> a >> b;
            cout << query(1,1,N,a,b) << "\n";
        }
    }

    return 0;
}

문제 분석 및 풀이

설계 분석

• 자식들의 정보만 가지는 트리를 구현하고, 중복되는 입력을 한번에 처리하는 문제.
• m개의 간선을 입력하고 루트부터 n개의 노드를 순회하며 자식 노드에 값을 중첩시킨다. $O(N+M)$

풀이

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
const int MAX = 100'001;
int n, m;
int costArr[MAX];
unordered_map<int, vector<int>> g;

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

    // 자식 노드를 저장하는 그래프 초기화
    cin >> n >> m;
    for (int val=1; val<=n; val++)
    {
        int parent;
        cin >> parent;
        g[parent].push_back(val);
    }

    // 입력값 기록
    for (int i=0; i<m; i++)
    {
        int target, value;
        cin >> target >> value;
        costArr[target] += value;
    }

    // root노드부터 점점 내려가면서 값을 중첩
    queue<int> q;
    q.push(1);
    while(!q.empty())
    {
        // 현재 방문한 노드
        int front = q.front(); q.pop();
        // 현재 노드의 인접노드에 값을 누적
        for (auto v : g[front])
        {
            costArr[v] += costArr[front];
            q.push(v);
        }
    }

    for (int i=1; i<=n; i++)
        cout << costArr[i] << " ";


    return 0;
}

문제 분석 및 풀이

설계 분석

• 세그먼트 트리를 활용할 수 있는지 확인하는 문제
• 세그먼트 트리는 자주 변경되는 데이터의 누적합에 사용된다.
  • 여기서는 i번 맛의 사탕이 몇개 있는지를 합해서 트리를 구현
  • 1번이 2개 2번이 3개면 1-2까지의 사탕은 5개 있다.
  • r순위의 사탕을 꺼내기 위해서 현재 범위에 사탕이 몇개 있는지 확인하면서 범위를 좁혀 사탕을 찾는다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 1000001;
int n;
long long A,B,C;
long long segTree[4*MAX];

void UpdateTree(int node, int left, int right, int idx, int diff)
{
    // idx --left --- right -- idx 인 경우 처리
    if (left > idx || idx > right) return;
    segTree[node] += diff;
    if (left == right) return;

    int mid = (left + right)/2;
    //왼쪽 자식 노드
    UpdateTree(node * 2, left, mid, idx, diff);
    //오른쪽 자식 노드
    UpdateTree(node * 2 + 1, mid + 1, right, idx, diff);
}

int query(int node, int left, int right, long long rank)
{
    if (left == right)  return left;
    int mid = (left + right) / 2;
    // 왼쪽 자식의 범위 [left , mid] 까지의 개수가 rank보다 많으면 
    // 즉 왼쪽범위의 사탕개수가 순위보다 같거나 많아지면 왼쪽 자식으로 감.
    // 사탕의 개수보다 rank가 크면
    // 오른쪽 범위에 답이 있으니까 왼쪽만큼의 개수를 빼고 탐색
    if (segTree[node * 2] >= rank)
        return query(node * 2, left, mid, rank);
    else
        return query(node * 2 + 1, mid + 1, right, rank - segTree[node * 2]);


}

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

    cin >> n;
    for(int i=0; i<n; i++)
    {
        cin >> A;
        if (A == 1)
        {
            cin >> B;
            int res = query(1, 1, MAX, B);
            cout << res << "\n";
            UpdateTree(1, 1, MAX, res, -1);
        }
        else
        {
            cin >> B >> C;
            UpdateTree(1, 1, MAX, B, C);
        }
    }
    return 0;
}

문제 분석 및 풀이

설계 분석

• 트리를 적절하게 구현할 수 있는지 확인하는 문제

• 배열에 자신의 부모를 기록해서 트리로 만든다.

• $O(logN)$

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>
using namespace std;
const int MAX = 10001;
int T,N;
int parent[MAX];

int Solution(int a, int b)
{
    int currA = a;
    int currB = b;

    vector<int> parentAvec;
    unordered_set<int> parBuset;

    parentAvec.push_back(a);
    parBuset.insert(b);

    // A부터 root까지의 노드를 담는다.
    while (true)
    {
        if (parent[currA] == currA) break;
        parentAvec.push_back(parent[currA]);
        currA = parent[currA];
    }

    // B부터 root까지의 노드를 해시셋에 담는다.
    while (true)
    {
        if (parent[currB] == currB) break;
        parBuset.insert(parent[currB]);
        currB = parent[currB];
    }

    // A부터 위로 올라가면서 B의 부모 목록에 있는지 확인하고
    // 있으면 반환.
    for (auto e : parentAvec)
    {
        if (parBuset.find(e) != parBuset.end())
            return e;
    }

    return -1;
}

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

    cin >> T;
    while(T--)
    {
        cin >> N;
        for (int i=1; i<=N; i++)
        {
            parent[i] = i;
        }

        for (int i=0; i<N-1; i++)
        {
            int p, c;
            cin >> p >> c;

            parent[c] = p;
        }

        int targetA, targetB;
        cin >> targetA >> targetB;

        int ans = Solution(targetA, targetB);
        cout << ans << "\n";
    }

    return 0;
}

문제 분석 및 풀이

설계 분석

• 여러 지점에서 동시에 BFS를 하는 문제
• 불이 먼저 탐색을 하도록
  • 플레이어가 먼저 탐색을 하면 플레이어와 불이 같은 위치에서 해당 깊이의 탐색이 종료 (플레이어 위치에 불이 뒤는게 번짐)

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
enum CellType
{
    NONE = 0,
    WALL,
    FIRE,
    JIHOON,
};

struct Cell
{
    int x;
    int y;
    int cnt;
    int type;

    Cell operator+(const pair<int,int>& other)
    {
        int nx = x + other.first;
        int ny = y + other.second;

        return {nx, ny, cnt+1, type};
    }
};

char graph[1000][1000];
bool visited[1000][1000];

vector<Cell> fireVec;
vector<pair<int,int>> dirVec={
    {1,0},
    {0,1},
    {-1,0},
    {0,-1},
};

Cell startCell;
int R,C;

bool CanGo(Cell next)
{
    if (next.x < 0 || next.x >= R) return false;
    if (next.y < 0 || next.y >= C) return false;
    if (visited[next.x][next.y]) return false;
    if (graph[next.x][next.y] == CellType::WALL) return false;
    if (graph[next.x][next.y] == CellType::FIRE) return false;
    if (graph[next.x][next.y] != CellType::NONE && next.type == CellType::FIRE)
        graph[next.x][next.y] = CellType::FIRE;

    return true;
}

int BFS(Cell start)
{
    queue<Cell> q;
    Cell curr;
    bool isEscape = false;

    // 불이 있는 칸 큐에 넣기
    for (auto c : fireVec)
    {
        q.push(c);
        visited[c.x][c.y] = true;
    }

    // 지훈이 위치 넣기
    q.push(start);
    visited[start.x][start.y] = true;

    // BFS
    while(!q.empty())
    {
        curr = q.front(); q.pop();
        // 지훈이가 가장자리에 가면 탈출
        if (curr.type == CellType::JIHOON)
        {
            if (curr.x == 0 || curr.x == R-1 || curr.y == 0 || curr.y == C-1)
            {
                isEscape = true;
                break;
            }
        }

        // D R U L 방향으로 탐색
        for (auto c : dirVec)
        {
            Cell nextCell = curr + c;
            if (CanGo(nextCell))
            {
                // 지훈, 불 상관없이 방문처리
                visited[nextCell.x][nextCell.y] = true;
                q.push(nextCell);
            }
        }
    }

    // 탈출했으면 지훈의 cnt를 반환
    if (isEscape)
        return curr.cnt;

    return -1;
}

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

    cin >> R >> C;
    Cell jihoon;

    // 입력
    for (int i=0; i<R; i++)
    {
        string row;
        cin >> row;
        for (int j=0; j<C; j++)
        {
            int type = 0;
            if (row[j] == '#')
                type = CellType::WALL;
            else if (row[j] == 'J')
                jihoon = {i,j,1,CellType::JIHOON};
            else if (row[j] == 'F')
                fireVec.push_back({i,j,0});

            graph[i][j] = type;
        }
    }

    auto res = BFS(jihoon);
    if (res == -1)
        cout << "IMPOSSIBLE";
    else
        cout << res;

    return 0;
}

문제 분석 및 풀이

설계 분석

• 동적 계획법 문제
• i번째 동전까지 사용해서 금액 j를 만들때 i-1번째 동전까지 사용해서 만든 금액을 다시 활용한다.
• 해당 단계의 결과가 다음 단계에 사용되므로 동적 계획법과 어울린다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int T, K;
int dp[101][10001];
int coin[101];
int cnt[101];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> T >> K;

    for (int i=1; i<=K; i++)
        cin >> coin[i] >> cnt[i];

    dp[0][0] = 1;
    //dp[i][j] -> i번째 동전까지 사용해서 j를 만드는 경우의 수

    for (int i = 1; i <= K; i++)
    {
        for (int j = 0; j <= T; j++)
        {
            // i번째 동전을 l개 사용하는 경우
            for (int l = 0; l <= cnt[i]; l++)
            {
                // i번째 동전까지 사용해서 j를 만드는 중
                // i번째 동전 l개를 제외한 금액
                int val = j - coin[i] * l;
                if (val < 0) break;
                // i번쨰 동전까지 사용해서 j를 만드는 경우의 수는 다음의 합과 같다.
                // i번째 동전을 사용하지 않는 경우
                // i번째 동전을 1개 사용하는 경우
                // ...
                // i번쨰 동전을 모두 사용한 경우
                dp[i][j] += dp[i-1][val];
            }
        }
    }

    cout << dp[K][T];

    system("pause");
    return 0;
}

문제 분석 및 풀이

설계 분석

• BFS를 사용하는 문제.
• 바이러스를 놓을 수 있는 칸의 정보를 알려주고 바이러스의 개수를 알려준다.
• 놓을 수 있는 칸들의 조합을 뽑아서 해당 상태에서 BFS를 시작하는 문제.
• next_permutaion을 통해서 조합 생성

$O(kCm \times N^2)$

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int N, M;
int graph[50][50];
int emptyCount = 0;
const int minVal = 987654321;
int ans = minVal;

enum CellType
{
    None = 0,
    Wall = 1,
    Candidate = 2,
};

struct Cell
{
    int x;
    int y;
    int depth;

    Cell operator+(const Cell other)
    {
        int nx = x + other.x;
        int ny = y + other.y;

        return {nx, ny, depth+1};
    }
};

// 바이러스를 놓을 수 있는 칸들을 담는 벡터
vector<Cell> candidateVec;
// BFS에 사용할 탐색 방향
// R D L U
vector<Cell> dirVec = {
    {0,1,0},
    {1,0,0},
    {0,-1,0},
    {-1,0,0},
};

// 다음칸으로 갈 수 있는지 반환
bool CanGo(const vector<vector<bool>>& visited, Cell nextCell)
{
    if (nextCell.x < 0 || nextCell.x >= N) return false;
    if (nextCell.y < 0 || nextCell.y >= N) return false;
    if (visited[nextCell.x][nextCell.y] == true) return false;
    if (graph[nextCell.x][nextCell.y] == CellType::Wall) return false;
    return true;
}

// 현재 선택된 칸들에 바이러스를 놓고 BFS
void Simulate(vector<int> selected)
{
    queue<Cell> q;
    vector<vector<bool>> visited(N, vector<bool>(N, false));
    // 감염시킨 칸들의 개수 (방문한 칸의 개수)
    int visitedCnt = 0;
    // 현재 BFS에서 가장 먼 거리
    int maxdepth = 0;

    // 선택된 칸을 감염처리하고 BFS시작
    for (auto index : selected)
    {
        q.push(candidateVec[index]);
        visited[candidateVec[index].x][candidateVec[index].y] = true;
        visitedCnt++;
    }

    //BFS
    while(!q.empty())
    {
        auto curr = q.front(); q.pop();
        for (int i=0; i<dirVec.size(); i++)
        {
            // R D L U순으로 격자 그래프 탐색
            Cell nextCell = curr + dirVec[i];
            if (CanGo(visited, nextCell))
            {
                // 갈 수 있으면 방문처리 후 큐에넣는다.
                visited[nextCell.x][nextCell.y] = true;
                visitedCnt++;
                q.push(nextCell);
                // 가장 긴 거리 갱신
                maxdepth = max(maxdepth, nextCell.depth);
            }
        }
    }

    // 방문한 칸의 개수와 빈칸의 개수가 같은경우 (모두 방문한 경우)
    // 갱신
    if (visitedCnt == emptyCount)
        ans = min(ans, maxdepth);
}

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

    cin >> N >> M;
    for (int i=0; i<N; i++)
    {
        for (int j=0; j<N; j++)
        {
            int val;
            cin >> val;
            // 해당 칸이 빈칸인 경우 빈칸의 개수를 늘림.
            if (val == CellType::Candidate) 
            {
                // 2번, 즉 바이러스를 놓을 수 있는 칸은 빈칸처리 후
                // 벡터에 넣어서 따로 관리
                candidateVec.push_back({i,j,0}); 
                val = CellType::None;
                emptyCount++;
            }
            else if (val == CellType::None)
            {
                emptyCount++;
            }

            graph[i][j] = val;
        }    
    }

    // 조합을 위한 보조 수열
    auto comb = vector<bool>(candidateVec.size(), false);

    // 후보 K게 중에서 M개를 뽑기 위해 M개의 true를 생성
    for(int i=0; i < M; i++)
    {
        comb[i] = true;
    }
    sort(comb.begin(), comb.end());

    do
    {
        // 조합을 담기위한 벡터
        vector<int> selected;

        // i번째 원소가 true면 선택된 것.
        for (int i=0; i<comb.size(); i++)
            if (comb[i] != 0)
                // index를 삽입.
                selected.push_back(i);
        // 각 조합마다 시뮬레이션
        Simulate(selected);
    //순열을 활용해 조합을 생성
    } while (next_permutation(comb.begin(), comb.end()));

    // 정답이 갱신되지 않은 경우 (어떤 경우에도 방문불가)
    if(ans == minVal)
        ans = -1;

    cout << ans << "\n";

    return 0;
}

문제 분석 및 풀이

설계 분석

• BFS를 사용하는 문제.
• 단순히 BFS중 탐색 방향에 우선순위를 두는것은 부족함

• 현재 지점에서 먹을 수 있는 물고기들을 후보에 넣음
  • 현재 지점에서 BFS
• 후보중 조건에 맞는 물고기 위치로 이동
  • 현재 지점을 갱신

위 과정을 물고기 후보가 없을때까지 반복.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int graph[20][20];
vector<vector<bool>> visited;
int N;
int ans = 0;

struct Cell
{
    int x;
    int y; 
    int cnt;
    int babySharkSize;
    int depth;

    bool operator<(const Cell& other)
    {
        if (depth == other.depth)
        {
            if (x == other.x)
            {
                return y < other.y;
            }

            return x < other.x;
        }

        return depth < other.depth;
    }
};

bool CanGo(Cell& cell)
{
    int x = cell.x;
    int y = cell.y;
    int bss = cell.babySharkSize;

    if (x < 0 || x >= N) return false;
    if (y < 0 || y >= N) return false;
    if (visited[x][y]) return false;
    if (bss < graph[x][y] && graph[x][y] != 0) return false;

    return true;

}

void BFS(Cell start)
{
    int dx[4] = {-1,0,0,1};
    int dy[4] = {0,-1,1,0};
    queue<Cell> q;
    Cell current;
    vector<Cell> fish;

    fish.push_back(start);

    // 시작좌표에서 BFS실행해서 먹을 수 있는 물고기의 후보 선택
    // 후보들을 최단거리, 상단, 좌측 순으로 정렬해서 맨 앞을 선택
    // 그 후보가 새로운 시작 좌표
    while(true)
    {
        visited = vector<vector<bool>>(N, vector<bool>(N, false));

        //직전 좌표에서 더이상 먹을 수 있는 물고기가 없으면 종료
        if (fish.empty()) break;

        // 먹을 수 있는 물고기 중 조건에 맞는걸 뽑음
        sort(fish.begin(), fish.end());
        int cx=fish.front().x;
        int cy=fish.front().y;
        int& csize = fish.front().babySharkSize;
        int& ccnt = fish.front().cnt;
        visited[cx][cy] = true;

        // 현재 칸의 물고기를 먹을 수 있으면 먹음
        if (graph[cx][cy] < csize &&  graph[cx][cy] != 0)
        {
            graph[cx][cy] = 0;
            ccnt++;
            // 현재까지 먹은 물고기의 수ccnt가 현재 크기와 같아지면 
            // 크기를 늘림
            if (fish.front().cnt == csize)
            {
                csize++;
                ccnt=0;
            }
        }

        // BFS를 위해 Q에 삽입
        // 물고기중 조건에 맞는 게 새로운 시작 좌표
        q.push(fish.front());

        // 정답 갱신
        ans = fish.front().depth;

        // 후보 배열 정리
        fish.clear();


        // BFS 시작
        while(!q.empty())
        {
            current = q.front(); q.pop();
            for (int i=0; i<4; i++)
            {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];

                Cell nCell = {nx, ny, current.cnt, current.babySharkSize, current.depth + 1};
                if (CanGo(nCell))
                {
                    // 물고기 먹을 수 있는 칸은 후보에 추가
                    if (graph[nx][ny] < current.babySharkSize && graph[nx][ny] != 0)
                    {
                        fish.push_back(nCell);
                    }
                    q.push(nCell);
                    visited[nx][ny] = true;
                }
            }
        }
    }

    cout << ans << "\n";
}

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

    int startX;
    int startY;

    cin >> N;

    // 입력
    for (int i=0; i<N; i++)
    {
        for (int j=0; j<N; j++)
        {
            int val;
            cin >> val;
            // 현재 위치를 0으로 바꾸기
            if (val == 9) {startX = i; startY = j; val = 0;}
            graph[i][j] = val;
        }
    }

    BFS({startX,startY,0,2,0});


    return 0;
}

문제 분석 및 풀이

설계 분석

• BFS를 사용하는 문제.
• 처음에는 그리디로 접근 했다가, +1 -1 둘 다 있어서 안된다는 것을 알았다.
• BFS를 통해서 최소 거리를 찾고, 최소 거리를 가지는 경로의 수를 찾는다.
• $O(3N) = O(N)$에 가능

풀이

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N,K;
const int MAX = 100001;
int ans;
vector<int> visited(MAX, MAX);

bool CanGo(int x, int cnt)
{
    // 경계확인
    if (x < 0 || x >= MAX) return false;
    // 최소경로로 방문한 적 있는지 확인
    if (visited[x] < cnt) return false;

    return true;
}

void BFS(int x)
{
    int dx[3] = {-1, 1, 2};
    queue<pair<int,int>> q;
    q.push({x,0});
    visited[x] = 0;

    while(!q.empty())
    {
        int pos = q.front().first;
        int cnt = q.front().second;
        q.pop();

        // 현재 위치가 K이고 cnt가 최솟값이면 경로 수 증가
        if (cnt == visited[K] && pos == K) ans++; 
        int nx = 0;
        for (int i=0; i<3; i++)
        {
            // *2
            if (i == 2)
            {
                nx = pos * 2;
            }
            // +1, -1
            else
            {
                nx = pos + dx[i];
            }

            if (CanGo(nx, cnt+1))
            {
                visited[nx] = cnt+1;
                q.push({nx, cnt+1});
            }
        }
    }
}

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

    cin >> N >> K;

    BFS(N);

    // K까지의 거리의 최소거리
    cout << visited[K] << "\n";
    // 최소경로의 개수
    cout << ans << "\n";

    return 0;
}

문제 분석 및 풀이

설계 분석

• 벽 부수고 지나가기처럼 BFS에 상태를 추가하는 문제태를 추가하는 문제
• $N<100$ 이므로 $O(N^3)$까지 가능
• BFS진행
  • 각 Cell에 어느 방향으로 들어왔는지, 거울 개수는 몇개인지 기록
  • 직전 Cell의 진입 방향과 다음 방향이 다르면 거울 개수 증가

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <cstring>
#include <queue>
using namespace std;

int W, H;
const int INF = 987654321;
struct Pos
{
    int x;
    int y;
    int dir;
    int cnt;

    bool operator==(Pos& other)
    {
        return x==other.x && y==other.y; 
    }

    bool operator<(const Pos& other) const
    {
        return cnt < other.cnt;
    }
};

vector<string> graph;
vector<vector<vector<int>>> visited;
vector<Pos> ans;
vector<Pos> C;

bool CanGo(Pos nextPos)
{
    int x = nextPos.x;
    int y = nextPos.y;
    int dir = nextPos.dir;

    if (x < 0 || x >= H) return false;
    if (y < 0 || y >= W) return false;
    if (graph[x][y] == '*') return false;
    if (visited[x][y][dir] <= nextPos.cnt) return false;

    return true;
}

void BFS(Pos start)
{
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};

    queue<Pos> q;
    q.push({start.x, start.y, -1, 0});

    for (int i=0; i<4; i++)
    visited[start.x][start.y][i] = 0;

    while (!q.empty())
    {
        Pos curr = q.front(); q.pop();
        for (int i=0; i<4; i++)
        {
            int cnt = curr.cnt;
            // 직전 방향과 다르면 거울증가 (90도 꺾이는 경우, 180도 또한 여기 걸리는데 최소 값에서 걸러짐)
            if (curr.dir != -1 && i != curr.dir) cnt++;
            Pos nextPos = {curr.x + dx[i], curr.y + dy[i], i, cnt};
            if (CanGo(nextPos))
            {
                visited[nextPos.x][nextPos.y][nextPos.dir] = cnt;
                q.push(nextPos);
            }
        }
    }
}

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

    cin >> W >> H;
    graph = vector<string>(H, string(W,' '));
    visited = vector<vector<vector<int>>>(H,vector<vector<int>>(W, vector<int>(4,INF)));

    // 격자 그래프 입력
    for (int i=0; i<H; i++)
    {
        for (int j=0; j<W; j++)
        {
            char cell;
            cin >> cell;
            // 레이저의 출발, 도달 기록
            if (cell == 'C')
            {
                C.push_back({i,j,0});
            }
            graph[i][j] = cell;
        }
    }

    BFS(C.front());

    // 4방향으로 들어온 경로중에서 가장 적은 거울을 사용한 경우를 선택
    auto minVal = *min_element(visited[C.back().x][C.back().y].begin(), visited[C.back().x][C.back().y].end());

    cout << minVal;

    return 0;
}

문제 분석 및 풀이

설계 분석

• 간선 정보와 최댓값(최솟값)을 구하라는 이야기가 있어서 일단 최단거리 알고리즘을 생각했다.
• 경로의 중복이 가능하고 돈을 무한히 가지고 있을 수 있는 경우가 있다는 것으로 보아 사이클을 판별하는 문제라고 생각했다.
• 최단경로와 사이클 둘다 관련있는 벨만 포드를 떠올리게 되었고 여기서는 음의 사이클이 아니라 양의 사이클이 있는지 확인해야 한다. (돈을 무한히 가지는 경우에서 힌트를 받음)
• 모든 간선을 검사 하면서 더 큰 값으로 갱신 (N-1번)
• 마지막으로 검사
  • 여기서 갱신되는 노드는 사이클에 포함
• 사이클에서 목적지로 갈 수 있으면 돈을 무한히 가질 수 있음
  • 출발 - 종료 경로 사이에 사이클이 있다는 뜻

구현은 생각보다 금방 끝났지만 통과까지는 엄청난 시간이 걸렸다. 중간에 정답 코드와 비교하면서 어디가 잘못되었는지 비교했는데 아무리봐도 맞는 풀이어서 난감했었는데 질문게시판을 모두 읽어보다가 발견했다.

'같은 경로에 다른 값이 들어오는 경우가 있다'

문제에서 여러 교통 수단을 이용할 수 있다고 이야기한 것을 위와 같은 상황이 생길 수 있다고 생각하면 솔직히 나는 자신 없다. 그래도 경험 해봤으니 문제를 주의 깊게 읽어야 할듯.

여튼 간선을 기록했다면 별로 문제가 없었겠지만 나는 인접 행렬로 그래프 정보를 저장해서 간선의 값이 덮어씌워지는 현상이 생겼고 50%에서 무한 실패를 경험했다. 그 뒤에 큰 값을 유지하도록 바꿔 간단히? 해결했다. 간선을 벡터에 담아서 사용했다면 자연스레 중복된 경로가 여러개 존재해 알아서 갱신 되었겠지... 개인적으로 디버깅할 때 값을 보기 편해서 인접행렬을 선호 했는데. 앞으로는 주의 해야겠다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <cstring>
#include <queue>
using namespace std;

const long long MAX = 987654321;
int N, M, start, dest;
int income[50];
int graph[50][50];
long long dist[50];

void Bellman_Ford(int start)
{
    fill(dist, dist+N, -MAX);
    dist[start] = income[start];

    // N-1번 반복
    for (int k=0; k<N-1; k++)
    {
        for (int i=0; i<N; i++)
        {
            for (int j=0; j<N; j++)
            {
                if(graph[i][j] == -MAX || dist[i] == -MAX) continue;
                if(dist[i] + graph[i][j] >= dist[j])
                {
                    dist[j] = dist[i] + graph[i][j];
                }

            }
        }
    }


    int before  = dist[dest];
    // 여기서 갱신되는 노드는 사이클에 포함
    vector<int> cycle;
    for (int i=0; i<N; i++)
    {
        for (int j=0; j<N; j++)
        {
            if(graph[i][j] == -MAX || dist[i] == -MAX) continue;
            if(dist[i] + graph[i][j] > dist[j])
            {
                cycle.push_back(j);
                dist[j] = dist[i] + graph[i][j];
            }

        }
    }

    int after  = dist[dest];

    // 경로가 없으면
    if(dist[dest] == -MAX)
    {
        cout << "gg\n";
    }
    // 목적지까지의 값이 갱신 되었으면 (도착점이 사이클에 포함되는 경우)
    else if (before != after)
    {
        cout << "Gee\n";
    }
    else
    {
        // 사이클에서 도착점 까지 갈 수 있는지 판단.
        queue<int> q;
        vector<bool> visited(N,false);
        for (auto e : cycle)
        {
            visited[e] = true;
            q.push(e);
        }

        while(!q.empty())
        {
            int u = q.front(); q.pop();
            if (u == dest) 
            {
                cout << "Gee\n";
                return;
            }
            for (int v=0; v<N; v++)
            {
                if (graph[u][v] == -MAX) continue;
                if (visited[v]) continue;
                visited[v] = true;
                q.push(v);
            }
        }
        cout << dist[dest] <<"\n"; 
    }

}

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

    fill(&graph[0][0], &graph[0][0]+(50*50), -MAX);
    cin >> N >> start >> dest >> M;

    // 그래프 초기화
    for (int i=0; i<M; i++)
    {
        int u,v,weight;
        cin >> u >> v >> weight;
        // 동일 경로에 다른 값이 들어오는 경우가 있네... 허허....
        // 이것때문에 3시간 날렸네ㅋㅋㅋㅋ
        // 간선 리스트로 할걸...
        graph[u][v] = max(graph[u][v], -weight);
    }


    // 각 도시에 도착했을때 얻는 돈을 최신화
    for (int i=0; i<N; i++)
    {
        int weight;
        cin >> weight;
        income[i] = weight;
        for (int j=0; j<N; j++)
        {
            if (graph[j][i] != -MAX)
            graph[j][i] += weight;
        }

    }

    Bellman_Ford(start);


    return 0;
}

문제 분석 및 풀이

설계 분석

• 비트마스킹으로 같은 경로를 걸러내는 것이 중요한 문제

• 아래 과정을 P개 이상의 발전소가 켜질때 까지 반복

  • 켜진 발전기중 하나 선택 (i)
  • 꺼진 발전기중 하나 선택 (j)
  • j 켜기
  • i를 이용해서 j를 키는 비용을 추가

• 내 풀이는 P개 이상 켜졌을 때 전역변수에 최솟 값을 갱신하는 방법

• 더욱 최적화된 풀이는 각 상태의 최솟값을 배열에 저장해서 재사용

풀이

나의 풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;

const int INF = 987654321;
int N, P;

int graph[16][16];
int minimum = INF;
unordered_map<int, int> umap;

void dfs(int mask, int val)
{
    if (umap.find(mask) != umap.end())
    {
        int exsistingValue = umap[mask];
        if (exsistingValue <= val) return;
    }

    umap[mask] = val;

    int cnt = 0;
    for (int i = 0; i < N; ++i) {
        if ((mask >> i) & 1) { // i번째 비트가 1인지 확인
            cnt++;
        }
    }

    if (cnt >= P)
    {
        minimum = min(minimum, val);
        return;
    }

    for (int i=0; i<N; i++)
    {
        if (!(mask & (1 << i))) continue;
        for (int j=0; j<N; j++)
        {
            if (mask & (1 << j)) continue;
            dfs(mask | ( 1 << j ), val + graph[i][j]);
        }
    }
}

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

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

    string onOffstat;
    cin >> onOffstat;
    int mask = 0;
    for (int i=0; i<onOffstat.size(); i++)
    {
        if (onOffstat[i] == 'Y')
        {
            mask |= 1 << i;
        }
    }

    cin >> P;

    dfs(mask, 0);
    minimum = minimum == INF ? -1 : minimum;
    cout << minimum;

    return 0;
}

개선 버전

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <cstring>
using namespace std;

const int INF = 987654321;
int N, P;

int graph[16][16];
int minimum = INF;
int cost[1 << 16];

int dfs(int mask)
{
    // 이미 값이 존재하면 그것을 리턴
    if (cost[mask] != -1)
    {
        return cost[mask];
    }

    // 켜진 발전소 개수
    int cnt = 0;
    for (int i = 0; i < N; ++i) 
    {
        if ((mask >> i) & 1) 
            cnt++;
    }

    // P개 이상이면 종료
    if (cnt >= P)
    {
        return 0;
    }

    cost[mask] = INF;
    // 현재 켜져있는 발전소에서 꺼진 발전소로 
    for (int i=0; i<N; i++)
    {
        // 켜저있는 발전소가 i
        if (!(mask & (1 << i))) continue;
        for (int j=0; j<N; j++)
        {
            // 꺼진 발전소가 j
            if (mask & (1 << j)) continue;
            // 현재 상태의 최솟값과, j발전 소를 킨 이후의 dfs값 + i에서 j를 키는 값
            cost[mask] = min(cost[mask], dfs(mask | ( 1 << j )) + graph[i][j]);
        }
    }

    return cost[mask];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
    // dp용 배열 -1로 초기화
    memset(cost, -1, sizeof(cost));

    // 입력
    cin >> N;
    for (int i=0; i<N; i++)
    {
        for (int j=0; j<N; j++)
        {
            int weight;
            cin >> weight;
            graph[i][j] = weight;
        }
    }

    string onOffstat;
    cin >> onOffstat;

    // 발전서 정보 초기회
    int mask = 0;
    for (int i=0; i<onOffstat.size(); i++)
    {
        // 켜진 경우는 비트마스킹
        if (onOffstat[i] == 'Y')
        {
            mask |= 1 << i;
        }
    }

    // 최소 P개 이상 켜져 있어야함
    cin >> P;

    minimum = dfs(mask);

    if (minimum == INF)
    {
        minimum = -1;
    }

    cout << minimum;

    return 0;
}

문제 분석 및 풀이

설계 분석

• 피보나치의 여러 성질, 빠르게 피보나치를 빠르게 구하는 방법을 알아야 풀 수 있는 문제

• 피보나치 수열의 합에 관한 성질을 알야야 함.

  • 

  • 피보나치에 관한 여러 성질들

• 피보나치 수열을 행렬의 거듭제곱을 통해서 구하는 방법을 알아야함

  • $O(logN)$으로 가능
  • 피보나치를 구하는 방법들

풀이

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1000000;

vector<vector<long long>> base =
{
    {1,1},
    {1,0}
};

vector<vector<long long>> current;

vector<vector<long long>> matrix_time(vector<vector<long long>> A, vector<vector<long long>> B)
{
    vector<vector<long long>> res = vector<vector<long long>>(A.size(), vector<long long>(B[0].size()));
    for (int i=0; i<2; i++)
    {
        for (int j=0; j<2; j++)
        {
            long long sum = 0;
            for (int k=0; k<2; k++)
            {
                sum += A[i][k] * B[k][j];
            }
            res[i][j] = sum % MOD;
        }
    }

    return res;
}

vector<vector<long long>> matrix_power(vector<vector<long long>> arr, long long i)
{
    vector<vector<long long>> res = {{1,0},{0,1}};
    while (i > 0)
    {
        if (i % 2 == 1)
        {
            res = matrix_time(res, arr);
        }
            arr = matrix_time(arr, arr);
        i /= 2;
    }

    return res;
}

long long fibo(long long i)
{
    vector<vector<long long>> A =
    {
        {1,1},
        {1,0}
    };

    A = matrix_power(A, i);

    return A[1][0];
}


long long Sol(long long left, long long right)
{
    long long l_1 = fibo(left+1) % MOD;
    long long r_2 = fibo(right+2) % MOD;

    long long sum = ((r_2 - l_1) + MOD) % MOD;

    return sum;
}

int main()
{
    long long l, r;

    cin >> l >> r;

    long long res = Sol(l, r);

    cout << res << "\n";

    return 0;
}

문제 분석 및 풀이

설계, 분석

격자 그래프에서 최단경로를 찾는 문제. 최단경로는 BFS를 사용하는데, 여기서는 열쇠를 여부를 확인해야한다.

예전에 풀었던 벽 부수고 지나가기 처럼 BFS에 상태를 추가하는 풀이.

• visted 배열에 현재 획득한 키의 상태를 저장
  • 비트 마스크를 통해서 관리
• 현재 좌표를 현재 키 상태로 방문한 적 있으면 방문 불가
• 현재 좌표가 문
  • 열쇠가 없으면 방문 불가
• 현재 좌표가 열쇠
  • 열쇠 획득 처리

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;

struct Pos
{
    int x;
    int y;
    int keyStatus = 0;
    int distance = 0;
};

int N, M;
string maze[50];
int visited[50][50][1<<7];
Pos startPos;


void GetKey(Pos& pos, int index)
{
    pos.keyStatus |= 1 << index;
}

bool KeyCheck(int keyStatus, int doorIndex)
{
    if ((keyStatus & 1 << doorIndex) == 0)
    {
        return false;
    }

    return true;
}

bool MoveToNextCell(Pos& next)
{
    // x,y 범위 넘으면 실패
    if (0 > next.x || next.x >= N) return false;
    if (0 > next.y || next.y >= M) return false;
    // 벽이면 실패
    if (maze[next.x][next.y] == '#') return false;

    // 이미 방문했으면 실패
    if (visited[next.x][next.y][next.keyStatus] == true) return false;

    // 열쇠
    if ('a' <= maze[next.x][next.y] && maze[next.x][next.y] <= 'f')
    {
        GetKey(next, maze[next.x][next.y] - 'a');
    }

    // 문
    if ('A' <= maze[next.x][next.y] && maze[next.x][next.y] <= 'F')
    {
        // 열쇠가 없는 경우
        if (KeyCheck(next.keyStatus, maze[next.x][next.y] - 'A') == false) return false;
    }

    return true;
}

void BFS(Pos start)
{
    queue<Pos> q;
    q.push(start);
    visited[start.x][start.y][start.keyStatus] = true;

    while(!q.empty())
    {
        auto f = q.front();
        q.pop();
        for (int i=0; i<4; i++)
        {
            // RDLU 순으로 탐색
            int dx[] = {0,1,0,-1};
            int dy[] = {1,0,-1,0};

            Pos next = {f.x + dx[i], f.y + dy[i], f.keyStatus, f.distance + 1};
            if (MoveToNextCell(next))
            {
                visited[next.x][next.y][next.keyStatus] = true;
                if (maze[next.x][next.y] == '1')
                {
                    cout << next.distance << "\n";
                    return;
                }
                q.push(next);
            }
        }
    }
    cout << -1 << "\n";
}

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

    // 입력
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        string row;
        cin >> row;
        // 시작 지점
        auto zeroIndex = row.find("0");
        if (zeroIndex != string::npos)
        {
            startPos = {i, static_cast<int>(zeroIndex)};
        }
        maze[i] = row;
    }

    BFS(startPos);

    return 0;
}

문제 분석 및 풀이

설계 분석

• 간선의 목록이 주어졌을 때 이들을 그룹화하고 대표를 정하는 문제

  • Union - Find 연산을 통해서 그룹화
  • 대표 선정
    • 문제의 예시에서 1번이 대표면 3번은 3-2-1경로, 2번이 대표면 3-2 경로
    • 각 노드에서 가장 멀리 떨어진 노드까지의 거리가 가장 작은 것을 대표로
    • 플로이드 워셜을 통해 미리 거리를 계산

  $O(N^3)$

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <cmath>
using namespace std;

const int INF = 10e8;

vector<vector<int>> graph;
vector<int> parent;
map<int, vector<int>> group;

int N, M;

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

void Union(int A, int B)
{
    A = Find(A);
    B = Find(B);

    if (A == B) return;
    parent[A] = B;
}


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

    cin >> N >> M;

    // 그래프 + 거리
    graph = vector<vector<int>>(N+1, vector<int>(N+1, INF));
    // 유니온 파인드를 위한 parent
    parent = vector<int>(N+1);

    // 초기에 자신의 부모는 자기 자신
    for (int i=1; i<=N; i++)
        parent[i] = i;

    // 그래프 초기화, Union
    for (int i=0; i<M; i++)
    {
        int u,v;
        cin >> u >> v;
        graph[u][v] = graph[v][u] = 1;
        Union(u,v);
    }

    // 그룹별로 map에 저장
    for (int i=1; i<=N; i++)
    {
        group[Find(i)].push_back(i);
    }

    // 플로이드 워셜
    for (int k=1; k<=N; k++)
    {
        for (int i=1; i<=N; i++)
        {
            for (int j=1; j<=N; j++)
            {
                if (graph[i][j] > graph[i][k] + graph[k][j])
                    graph[i][j] = graph[i][k] + graph[k][j];
            }
        }
    }

    // 정답 출력용 set
    set<int> ans;

    // 각 그룹별로 연산
    for (auto g : group)
    {
        auto key = g.first;
        auto& vec = g.second;

        int rep = -1;
        int best = INF;

        // 각 그룹의 한 노드에서 다른 노드까지의 거리중
        // 가장 긴 거리를 추출
        for (auto from : vec)
        {
            int max_dist = -1;
            for (auto to : vec)
            {
                if (from == to) continue;
                max_dist = max(max_dist, graph[from][to]);
            }

            // 가장 긴 거리중에서 가장 작은것을 가진 노드가 대표
            if (best > max_dist)
            {
                best = max_dist;
                rep = from;
            }
        }

        // 정답 배열에 삽입
        ans.insert(rep);
    }

    cout << ans.size() << "\n";

    for (auto& e : ans)
    {
        cout << e << endl;
    }

    return 0;
}

문제 분석 및 풀이

설계 분석

처음 생각

• 간선 (u,v)를 포함하는 사이클이 있다면 간선 (u,v)는 단절선이 아니다.
• 모든 노드에 대해서 (u,v) 로 시작하는 경로를 DFS로 탐색. u로 돌아 오는 경로가 있으면 (u,v)는 단절선 아님
• 아이디어 자체는 맞는 듯 하지만 구현에서 시간초과
  • https://testcase.ac/problems/11400 기준으로 틀린 케이스 없음
  • $O(V*(E+V)$

찾아본 풀이

• DFS 스패닝 트리를 생성

  • DFS를 어떤 노드 대해서 실행 했을 때 생기는 그래프를 루트가 해당 노드인 트리로 해석
  • 간선 (u,v)이 절단선이려면 v가 루트인 서브트리에서 v를 거치지 않고 u로 도달하는 경로가 없어야함
  • 위에서 말한 간선 (u,v)를 포함하는 사이클이 있다면 간선 (u,v)는 단절선이 아니다. 적용

• 스패닝 트리를 생성하는 과정에서 방문 순서 기록

  • 이미 방문한 노드를 방문하는 경우 (사이클)
  • 부모를 타고 가면서 자신의 방문 순서와, 방문한 노드의 방문순서 중 작은 값으로 갱신 후 경로는 포함 x

• 문제에서 그래프는 항상 연결되어 있다고 했으니까 DFS 1회 진행하면 답을 찾을 수 있음

$O(V+E)$

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <set>
using namespace std;

int V,E;
unordered_map<int ,vector<int>> graph;
vector<int> visited;
set<pair<int, int>> bridges;

int time_count=1;
int dfs(int curent, int parent)
{

    // 방문 여부 + 방문 시간 기록
    visited[curent] = time_count++;

    // 현재 서브트리에서 도달 가능한 가장 낮은 방문 시간
    // 모든 노드는 초기에 자기 자신까지만 도달 가능
    int low_node_value = visited[curent];

    // 이웃 노드를 자식으로 취급
    for (auto child : graph[curent])
    {
        // 바로 되돌아가는 역방향 간선은 차단
        if (child == parent) continue;

        // 이미 방문한 경우 (사이클이 있는 경우)
        if (visited[child] != 0)
        {
            // 자신의 방문 순서와 도달 가능한 가장 낮은 방문 시간 중 작은 값으로 갱신 
            low_node_value = min(low_node_value, visited[child]);
            continue;
        }

        // 재귀를 통해서 서브트리를 탐색
        // 여기서 서브트리가 도달 가능한 가장 낮은 방문 시간 값 나옴
        int subtree = dfs(child, curent);
        // 서브트리 값이랑, 내 방문 순서랑 비교해서 작은걸로 갱신
        low_node_value = min(low_node_value, subtree);

        // 서브 트리의 순번이 부모보다 큰 경우 브릿지임
        if (subtree > visited[curent])
        {
            bridges.insert({min(curent,child), max(curent,child)});
        }
    }

    return low_node_value;
}

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

    cin >> V >> E;
    for (int i=0; i<E; i++)
    {
        int u,v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    visited.resize(V+1,0);

    dfs(1, 0);

    cout << bridges.size() << "\n";

    for (auto p : bridges)
        cout << p.first << " " << p.second << "\n";

    return 0;
}

문제 분석 및 풀이

설계 분석

골드 바흐 추측, 에라토스테네스의 체의 발전된 버젼을 공부할 수 있었던 문제

• 골드 바흐 추측

  • 강한 추측 : 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다.
  • 약한 추측 : 5보다 큰 모든 홀수는 세 소수의 합으로 나타낼 수 있다.
    • 7이상의 소수는 2 + p + q 형태로 나타낼 수 있다.

• 모든 소수는 6k+1, 6k-1 형태로 나타낼 수 있음

$O(MAX log log MAX + T \sqrt n)$

• 앞의 부분은 소수 역수의 합이 $MAX log log MAX$과 비슷하다는 것에서 도출
• n에서 p의 배수를 지운 다는건 $\frac{n}{p}$와 동일
• $\Sigma \frac{n}{p} = n \times n loglog n$

  풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int T;
// 입력 범위가 4 * 10^12 이기 때문에
// 이 수의 제곱근 까지만 판별하면 된다.
constexpr int MAX = 2000001;
bool prime[MAX];
vector<int> primevec;

void change_bool(int start, int acc, bool flag)
{
    for (int i = start; i < MAX; i+=acc)
    {
        prime[i] = flag;
    }
}

// 기존의 방식과는 조금 다르다
// 기존에는 모든 수에서 제거하는 방식
// 이 방식은 가능성이 있는 수를 넣고
// 그 안에서 아닌 것 제거
void eratosthenes()
{
    std::fill_n(prime, MAX, false);
    prime[2] = true;
    prime[3] = true;

    // 모든 소수 p = 6k +- 1 형태로 표현 가능
    // 6k +- 1 형태라고 반드시 소수는 아님

    // 6k - 1
    // 5 11 17 23 29 35...
    change_bool(5, 6, true);

    // 6k + 1
    // 1 7 13 19 25 31 37 43 49 55 61 67...
    change_bool(7, 6, true);

    for (int i=5, j = 25; j < MAX;)
    {
        // i = 5에서 시작
        // next가 2, 4 로 반복
        // i = 5 7 11 13 17 ...
        int next = (i-3) % 6;
        if (prime[i] == true)
        {
            // 25 이후 부터 5의 배수들을 지운다.
            // 5x5 5x11 5x17
            // 5x7 5x13 5x19
            // 이렇개 i와 6의 최소 공배수 만큼마다 반복.
            int addi = i * 6; // x mod 6 인 숫자만 검색
            change_bool(j, addi, false);

            // 위에서 6k+1 패턴 지우면
            // 여기서 6k-1 패턴 지움
            change_bool(next * i  + j, addi, false);
        }
        i += next;
        j = i * i;
    }


    for (int i=2; i<MAX; i++)
    {
        if (prime[i])
            primevec.push_back(i);
    }
}

bool isPrime(long long n)
{
    if (n < MAX)
    {
        return prime[n];
    }
    else
    {
        for (auto p : primevec)
        {
            if (1LL * p * p > n) break;
            if (n % p == 0) return false;
        }
    }
    return true;
}

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

    eratosthenes();

    cin >> T;
    while(T--)
    {
        long long a,b;
        cin >> a >> b;
        if (a+b <=3)
            cout << "NO" << '\n';
        // 골드바흐 추측(강한)
        else if ((a+b) % 2 == 0)
            cout << "YES" << '\n';
        // 골드바흐 추측(약한)
        else 
        {
            if (isPrime((a+b-2)))
                cout << "YES" << '\n';
            else
                cout << "NO" << '\n';
        }
    }

    return 0;
}

문제 분석 및 풀이

설계 분석

별찍기와 비슷한 문제 규칙을 찾아서 재귀로 주어진 형태를 출력하자.

기존에 *로 출력하는 대신에 정해진 모양이 있다는데 조금 달랐고 완성된 프랙탈의 우측에는 공백을 출력하지 않는다는 걸 알아야함. (테스트 케이스의 어디선가 막히는듯)

• 전체 삼각형의 높이와 너비를 구한다.
• 위쪽, 왼쪽 아래, 오른쪽 아래 순으로 재귀적으로 그린다.

풀이

#include <iostream>
#include <vector>
using namespace std;

int N;

void DrawSierpinskiFractal(vector<string>& canvas, int height, int x, int y)
{
    if (height==2)
    {
        canvas[y][x-1] = '/';
        canvas[y][x] = '\\';
        canvas[y+1][x-2] = '/';
        canvas[y+1][x-1] = '_';
        canvas[y+1][x] = '_';
        canvas[y+1][x+1] = '\\';
        return;
    }

    int half = height / 2;
    DrawSierpinskiFractal(canvas, half, x , y);
    DrawSierpinskiFractal(canvas, half, x - half , y + half);
    DrawSierpinskiFractal(canvas, half, x + half , y + half);
}


int main()
{
    while(true)
    {
        cin >> N;

        if (N==0) break;

        int height = 1 << N;
        int width = 1 << (N+1);
        vector<string> canvas(height, string(width, ' '));

        // 높이 x좌표 좌표 (상단 꼭짓점 좌표)
        DrawSierpinskiFractal(canvas, height, height, 0);
        for (int i=0; i<height; i++)
        {
            int end = width - 1;
            while(canvas[i][end] == ' ') end--;
            cout << canvas[i].substr(0, end+1) << "\n";
        }
        cout << "\n";
    }

    return 0;
}

문제 분석 및 풀이

설계 분석

머리로만 생각하니 막막해서 적어보여 접근했다

처음에는 왼쪽처럼 하다가 예제를 생각하며 각 노드의 입장에서 반드시 같은 반이 되어야하는 목록을 만들었고, 그 목록을 통해서 그래프를 만들었더니 예제의 정답과 동일한 형태가 만들어졌다.

• 각 노드에 연결되지 않은 노드들의 관계를 그래프로 나타낸다 (여 그래프)
  • 인접 행렬을 꽉 채우고 입력 받을 때 지운다 (내 생각) (메모리 폭발)
    • 각 노드에서 BFS를 해서 각 그룹의 크기를 구한다.
  • BFS를 연결되지 않은 방향으로 진행 (구글링)
    • 인접행렬 순회가 아니라, 미방문 노드들을 순화하며 큐에 넣음
    • i번 노드를 시작으로 하는 BFS가 끝나면 i와 같은 그룹에 속하는 노드들이 나옴

일반적인 BFS가 아니라 시간복잡도는 조금 간당간당 하다고 생각하는데 테스트케이스가 빡빡하지 않은 듯. 유니온-파인드와 차수를 이용해서 더욱 최적화할 수 있다고...

• $O(N)$

풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <queue>
using namespace std;

int N,M;

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

    cin >> N >> M;

    // 그래프 초기화
    vector<vector<int>> graph(N+1);

    for (int i = 0; i < M; i++)
    {
        int a,b;
        cin >> a >> b;

        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    //방문하지 않은 노드들의 목록을 만든다.
    set<int> unvisited;
    vector<int> groups;
    for(int i=1; i<=N; i++) unvisited.insert(i); 

    // 각 노드에 대해서 BFS
    // 각 노드의 인접 노드를 방문하면서 연결되지 않은 노드를 기록
    for(int i=1; i<=N; i++)
    {
        // i번 노드를 시작점으로
        if (unvisited.count(i) == 0) continue;

        //BFS 진행
        queue<int> q;
        q.push(i);
        unvisited.erase(i);
        int groupSize = 1;

        while(!q.empty())
        {
            int u = q.front();
            q.pop();

            // 현재 노드의 인접노드들
            set<int> adj(graph[u].begin(), graph[u].end());

            vector<int> temp;
            // 방문하지 않은 노드중 현재 노드와 연결되지 않은 노드 추가.
            for (auto v : unvisited)
            {
                if (adj.count(v) == 0)
                {
                    temp.push_back(v);
                }
            }

            // 위에서 찾은 노드들을 같은 그룹에 추가
            for (auto v : temp)
            {
                q.push(v);
                unvisited.erase(v);
                groupSize++;
            }
        }

        // 그룹 추가
        groups.push_back(groupSize);
    }

    sort(groups.begin(), groups.end());

    cout << groups.size() << "\n";
    for (auto v : groups)
    cout << v << " ";

    return 0;
}

문제 분석 및 풀이

설계 분석

평소에 풀던 유형도 아니고 자주 나오는 유형도 아니지만 풀이과정이 재미있어서 기록하는 문제

• $2\leq 10^4$ 이므로 $O(NlogN)$까지가 무난

• $A_{n+1} = \frac{A_{1} + A_{2} + ... + A_{N}}{N}$ 를 만족하는 수열을 만드는 문제

• $A_i$의 범위가 넓어서 무조건 찾을 수 있는데 어떻게 코드로 모든 N에 대해서 찾는지 찾아야함

• 위의 식을 정리해보면 $NA_{n+1} = A_{1} + A_{2} + ... + A_{N}$ 이 식을 간편하게 바꿔보자

• $A_{n+1} = 0$ 이면 $A_{1} + A_{2} + ... + A_{N} = 0$ 이라는 아주 아름다운(?) 식이 만들어진다.

• 그 뒤로는 (-1,1), (-2,2) 처럼 짝을 맞춰서 합이 0이 되도록 추가하면 된다.

• 최종 형태는 i -i j -j k -k 0 형태의 수열을 찾는다.

• 단 홀수인 경우 3개를 더해서 0이 되는 경우를 넣고 남은 개수를 짝수로 만들어 위의 과정을 진행

• $O(N)$

풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int N;

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

    /*
    NAn+1 = A1 + A2 + ... + AN을 만족하는 수열을 찾는 문제
    후보군이 충분히 넓으니 An+1 = 0 을 만족하는 조건을 찾자
    즉 A1 + A2 + ... + AN = 0이 되도록 설정하자
    그렇다면 
    i -i j -j k -k ... 0 형태의 수열을 찾아낼 수 있다.
    여기서 홀수인 경우 -9 8 1같이 3개를 더해 0이 되는 경우을 미리 넣어서 남은 개수를 짝수개로 만들어서
    i-i같이 짝을 맞춰 수열을 구성한다.
    */

    cin >> N;
    // 홀수인 경우
    if (N & 1)
    {
        cout << -100 << ' ' << 1 << ' ' << 99 << ' ';
        N-=3;
    }

    for (int i = 101, cnt = 1; cnt <= N / 2 ; i++, cnt++)
    {
        int pairAi = i;
        cout << pairAi << ' ' << -1 * pairAi << ' ';
    }

    cout << 0 ;

    return 0;
}