greentea31's Note

https://www.acmicpc.net/problem/9663

풀이 과정

NxN 크기의 체스판 위에 퀸 N개를 서로 공격할 수 없게 배치하는 경우의 수를 구하는 문제이다.

유명한 백트래킹 문제이다. 체스판 위에 퀸을 하나 하나 놓아가면서 이전에 놓았던 퀸이랑 같은 행, 열, 대각선에 위치하면 여기에는 못놓는다 판정하고 다음 위치에 놓아보는, 이러한 과정을 코드로 구현하면 된다.

체스판에서의 퀸의 위치를 2차원 배열로도 표현할 수 있지만, board[i] = j (i번째 행에 j번째 열에 퀸이 존재함) 과 같이 1차원 배열로도 퀸의 위치를 나타낼 수 있다.

1차원 배열과 재귀함수로 백트래킹을 해가면서 답을 구하였다.

소스 코드

#include <iostream>
using namespace std;

int board[16];
int N, answer;
void nQueen(int y) { // y개의 퀸이 체스판 위에 존재함
    int ko;

    if (y == N) { // N개 다 놓았으면 정답을 증가시킴
        answer++;
        return;
    }

    for (int i = 0; i < N; i++) { // y번째 행의 i번째 행의 칸에 대해서
        ko = 1;
        for (int j = 0; j < y; j++) { // 이미 놓인 퀸들에 대해서
            if (board[j] == i || abs(i - board[j]) == abs(y - j)) {
                ko = 0; // 같은 열에 존재하거나, 대각선에 이미 퀸이 존재해서 배치 불가능
                break;
            }
        }

        if (ko) { // 배치 가능하면
            board[y] = i; // 배치하고
            nQueen(y+1); // y+1개의 퀸이 존재하는 체스판 위에서 알고리즘을 다시 시행함
        }
    }
}

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

    cin >> N;
    nQueen(0);

    cout << answer;
    return 0;
}

https://www.acmicpc.net/problem/2579

풀이 과정

각각의 계단에는 점수가 적혀있고, 계단 1칸 건너기, 1칸 건너뛰고 건너기 두 개의 선택이 가능할 때 세 칸 연속으로 계단을 건너지 않고 마지막 계단을 밟을 때의 가능한 최대 점수 값을 구하는 문제이다.

각 계단을 올랐을 때 가능한 최대 점수 값을 기록해가면서 DP로 해결할 수 있다.

i번째 계단에서의 가능한 점수 최댓값 D[i], i번째 계단을 건널 때의 점수 값 A[i]에서

D[i] = max(D[i-2], D[i-3] + A[i-1]) + A[i]가 성립한다.

i-2번째 계단에서 2칸 건너오거나, i-1번째 계단에서 1칸 건너오거나 해야 하는데 i-1번째 계단에서 건너오는 경우는 i-2번째 계단을 밟지 않았다는 것을 점화식에 반영해 주어야 하기 때문에 D[i] = D[i-3] + A[i-1] + A[i]의 식이 된다.

DP는 언제나 초기 값 설정에 유의해주어야 한다. D[2]는 A[0] + A[2], A[1] + A[2] 둘 중 큰 수로 지정해주자.

소스 코드

#include <iostream>
using namespace std;

int D[301];
int A[301];

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

    int stair, num;
    cin >> stair;

    for (int i = 0 ; i < stair; i++) {
        cin >> num;
        A[i] = num;
    }

    D[0] = A[0];
    D[1] = D[0] + A[1];
    D[2] = max(D[0] + A[2], A[1] + A[2]);

    for (int i = 3; i < stair; i++) {
        D[i] = max(D[i-2], D[i-3] + A[i-1]) + A[i];
    }

    cout << D[stair-1] << '\n';

    return 0;
}

https://www.acmicpc.net/problem/11659

풀이 과정

N개의 수가 주어졌을 때, i번째 수부터 j번째 수 까지의 합을 구하는 문제이다.

개수 N이 최대 10만, 합을 구해야 하는 횟수 M이 최대 10만이다. i부터 j까지 일일이 더해보면서 합을 구하면 0번째 수부터 10만번 - 1째 수까지 다 더하라는 명령이 10만번 들어오면 연산 횟수가 너무 많아진다. O(N^2) 방법으로는 답을 해결할 수 없다.

구간을 입력받고 구간의 누적합을 한번 저장해놓으면 구간 합을 구하는 연산이 O(1)로 줄어든다. D[i]를 i번째 원소까지의 누적합이라고 하면 i번째 수부터 j번째 수까지의 합을 D[j-1] - D[i-2]로 바로 구할 수 있다.

소스 코드

#include <iostream>
using namespace std;

int A[100001];
int D[100001];

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

    int N, M, num, i, j;
    cin >> N >> M;

    for (int a = 0; a < N; a++) {
        cin >> num;
        A[a] = num;
    }

    D[0] = A[0];
    
    for (int a = 1; a < N; a++) {
        D[a] = D[a-1] + A[a];
    }

    for (int a = 0; a < M; a++) {
        cin >> i >> j;
        if (i >= 2) {
            cout << D[j-1] - D[i-2] << '\n';
        } else {
            cout << D[j-1] << '\n';
        }
    }

    return 0;
}

https://www.acmicpc.net/problem/1932

풀이 과정

위와 같은 정수 삼각형의 맨 위에서부터, 왼쪽 아래 혹은 오른쪽 아래 숫자를 더하면서 맨 아래까지 내려갈 때 만들 수 있는 최대 값을 구하는 문제이다.

위의 예시에서의 답은 7 + 3 + 8 + 7 + 5 = 30인데, 만약 그리디로 문제를 해결하려고 한다면 2번째 줄에서 3, 8 중에 8을 고르게 되어 답이 나오지 않는다.

DP로 풀어야 한다.

D[i][j]를 i번째 행의 j번째 열까지의 진행경로의 합이라고 하면 다음과 같은 점화식이 성립한다.

D[i][j] = max(D[i-1][j-1], D[i-1][j]) + A[i][j] (1 <= j <= i)

D[i][0] = D[i-1][0] + A[i][0]

D[i][i] = D[i-1][i-1] + A[i-1][i-1]

이를 통해 문제를 해결할 수 있다.

소스 코드

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

int d[501][501];
int a[501][501];

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

    int n, input;
    cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> input;
            a[i][j] = input;
        }
    }

    d[0][0] = a[0][0];

    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) {
                d[i][j] = d[i-1][j] + a[i][j];
            } else if (j == i) {
                d[i][j] = d[i-1][j-1] + a[i][j];
            } else {
                d[i][j] = max(d[i-1][j-1], d[i-1][j]) + a[i][j];
            }
        }
    }

    int maxValue = 0;

    for (int j = 0; j < n; j++) {
        if (maxValue < d[n-1][j]) maxValue = d[n-1][j];
    }

    cout << maxValue << '\n';

    return 0;
}

https://www.acmicpc.net/problem/1753

풀이 과정

방향 그래프를 줄 테니 시작점에서 다른 모든 정점으로의 최단 경로를 구하라는 문제다. 가중치가 자연수라는 조건이 중요하다.

그래프에서 최단 경로를 찾으라고 하면 BFS, 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘이 떠오르는데, 나열한 알고리즘에서 왼쪽으로 갈수록 빠른 알고리즘이지만, 더욱 특수한 조건에서만 사용이 가능하다.

BFS는 모든 간선의 가중치가 1이어야 하고, 다익스트라는 모든 간선의 가중치에 음수가 존재하면 안 된다, 벨만-포드나 플로이드-워셜 알고리즘은 간선의 가중치에 상관없이 사용이 가능하지만 알고리즘이 돌아가는데 더욱 오랜 시간이 걸린다.

이 문제는 가중치가 자연수로 주어지므로 다익스트라 알고리즘을 사용하여 최단 경로를 구할 수 있다.

소스 코드

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

const int INF = 987654321;
int d[20005];

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

    int V, E, u, v, w;
    cin >> V >> E;

    for (int i = 1; i < V+1; i++) { // 무한대 초기화
        d[i] = INF;
    }

    int start;
    cin >> start;

    vector<pair<int, int>> adj[20005];

    for (int i = 0; i < E; i++) { // 인접 리스트
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(w, v));
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 최소 힙
    d[start] = 0;
    pq.push(make_pair(d[start], start)); // 시작 거리 0 최소화후 최소힙 삽입


    while(!pq.empty()) {
        pair<int, int> cur = pq.top(); pq.pop();
        if (d[cur.second] != cur.first) continue;
        for (int i = 0; i < adj[cur.second].size(); i++) {
            pair<int, int> next = adj[cur.second][i];
            if (d[next.second] <= d[cur.second] + next.first) continue;
            d[next.second] = d[cur.second] + next.first;
            pq.push(make_pair(d[next.second], next.second));
        }
    }

    for (int i = 1; i < V+1; i++) {
        if (d[i] == INF) cout << "INF\n";
        else cout << d[i] << '\n';
    }

    return 0;
}

https://www.acmicpc.net/problem/1516

풀이 과정

건물의 여러 종류와 그 건물을 짓는 데 걸리는 시간, 그리고 건물을 지으려면 먼저 지어야 할 건물이 주어질 때, 각 건물을 짓는데 필요한 최소 시간을 구하는 문제이다.

문제에서 주어진 예시를 그림으로 표현하였다. 1번 건물을 지으려면 10초가 소요된다. 2번 건물을 지으려면 1번 건물이 완성된 이후에 지어야 하니 10 + 10 = 20초가 소요되고, 4번 건물을 지으려면 1번 건물 -> 3번 건물 -> 4번 건물 순으로 지어야 하니 10 + 4 + 4 = 18초가 소요된다.

A라는 건물을 짓는데 필요한 소요 시간은

A를 짓기 위해 먼저 지어야 하는 건물의 소요 시간들의 최대 값 + A를 짓는데 필요한 시간이다.

위의 그림으로 보았을때 Directed Acyclic Graph임을 알 수 있으니 위상 정렬을 시행해준 후, 앞에서 부터 소요시간을 계산하고 뒤의 소요시간을 계산하는 데 사용하는 DP를 시행하면서 문제를 해결할 수 있다.

소스 코드

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

int cost[501];
vector<int> directed[501];
vector<int> r_directed[501];
int inDegree[501];
queue<int> Q;

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

    int N, time, goal, cur;
    cin >> N;
    for (int i = 1; i < N+1; i++) {
        cin >> time;
        cost[i] = time;
        goal = 0;
        while(true) {
            cin >> goal;
            if (goal == -1) break;
            directed[goal].push_back(i);
            r_directed[i].push_back(goal);
            inDegree[i]++;
        }
    }

    for (int i = 1; i < N+1; i++) {
        if (inDegree[i] == 0) Q.push(i);
    }

    while (!Q.empty()) {
        int maxValue = 0;
        cur = Q.front(); Q.pop();

        for (int i = 0; i < r_directed[cur].size(); i++) {
            int prev_cost = cost[r_directed[cur][i]];
            if (prev_cost > maxValue) {
                maxValue = prev_cost;
            }
        }

        if (!r_directed[cur].empty()) cost[cur] += maxValue;

        for (int i = 0; i < directed[cur].size(); i++) {
            goal = directed[cur][i];
            inDegree[goal]--;

            if (inDegree[goal] == 0) {
                Q.push(goal);
            }
        }
    }

    for (int i = 1; i < N+1; i++) {
        cout << cost[i] << '\n';
    }

    return 0;
}

https://www.acmicpc.net/problem/1922

풀이 과정

컴퓨터와 각 컴퓨터를 연결하는 비용을 줄 테니, 모든 컴퓨터를 연결 상태 (모든 컴퓨터 사이의 경로가 존재해야 함)로 만드는데 필요한 최소 비용을 구하는 문제이다.

컴퓨터와 컴퓨터를 연결하는 비용을 방향이 없는 가중치 그래프로 모델링 하면, 문제에서 요구하는 것은 그래프의 최소 신장 트리를 만들라는 것임을 알 수 있다.

최소 신장 트리를 만드는 방법은 크루스칼 알고리즘, 프림 알고리즘 2가지 방법이 있고, 크루스칼 알고리즘을 이용하여 문제를 해결하였다.

간선을 가중치를 기준으로 오름차순으로 정렬하고, 간선의 출발 지점과 도착 지점이 이미 연결되어 있지 않으면 최소 신장 트리에 속하는 간선으로 추가하는 방법이다. 이미 연결되어 있는지 아닌지는 유니온-파인드 알고리즘을 사용하여 판단하였다.

https://greentea31.tistory.com/117

유니온-파인드는 위의 문제를 풀고 공부하면 무엇인지 알 수 있다.

소스 코드

#include <bits/stdc++.h>
using namespace std;

int parent[1001];

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

void uni(int a, int b) {
    int aRoot = parent[a];
    int bRoot = parent[b];
    if (aRoot == bRoot) return;
    parent[aRoot] = bRoot;
}

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

    int N, M, a, b, c;
    int answer = 0;
    cin >> N >> M;

    tuple<int, int, int> edge[100005];

    for (int i = 1; i < N+1; i++) {
        parent[i] = i;
    }

    for (int i = 0; i < M; i++) {
        cin >> a >> b >> c;
        edge[i] = make_tuple(c, a, b);
    }

    sort(edge, edge+M);

    for (int i = 0; i < M; i++) {
        tie(c, a, b) = edge[i];
        if (find(a) == find(b)) continue;
        uni(a, b);
        answer += c;
    }

    cout << answer;

    return 0;
}

https://www.acmicpc.net/problem/2252

풀이 과정

N명의 학생 중 일부 학생의 키의 대소 여부가 주어질 때, 줄을 세우는 프로그램을 작성하는 문제이다.

A와 B의 키의 대소 관계를 비교했을 때, A가 B보다 작으면 정점 A에서 B로 가는 간선이 존재하는 그래프로 모델링할 때, 문제에서 주어진 상황을 모델링하면 Direct Acyclic Grpah(비순환 방향 그래프) 형태로 모델링 된다.

비순환 방향 그래프는 그래프의 방향성을 거스르지 않고 정점들을 나열하는 위상정렬이 가능하다. 위상 정렬은 각 정점을 우선순위에 따라 배치한 것으로, 일반적으로 결과가 유일하지 않은데, 답이 여러 가지인 경우 아무거나 출력하라는 문제 지문을 고려하면 위상 정렬의 결과 중 하나를 출력하라는 의도임을 알 수 있다.

위상 정렬을 시행 후 결과를 출력시켜 주었다. 위상 정렬을 구현할 때 일반적으로

1. 인접 리스트

2. In-degree 저장 배열

3. push, pop이 가능한 자료구조

의 3가지를 활용해서 구현한다.

소스 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, temp;

    cin >> N >> M;
    vector<int> v[32001];
    queue<int> q;
    int inDegree[32001];

    for (int i = 0; i < N+1; i++) inDegree[i] = 0;

    int small, big;

    for (int i = 0; i < M; i++) {
        cin >> small >> big;
        v[small].push_back(big);
        inDegree[big]++;
    }

    for (int i = 1; i <= N; i++) {
        if(inDegree[i] == 0) {
            q.push(i);
        }
    }

    while(!q.empty()) {
        temp = q.front(); q.pop();
        cout << temp << ' ';

        for (int i = 0; i < v[temp].size(); i++) {
            inDegree[v[temp][i]]--;
            if (inDegree[v[temp][i]] == 0) q.push(v[temp][i]);
        }
    }
    return 0;
}

https://www.acmicpc.net/problem/1717

풀이 과정

유니온 파인드의 union 연산과 find 연산을 구현하라는 문제이다.

교집합이 공집합인 서로소 집합의 정보를 확인(find)하고 조작(union)할 수 있는 자료구조를 유니온 파인드라고 하는데, 아래 코드와 같이 연산을 구현할 수 있다.

소스 코드

#include <bits/stdc++.h>
using namespace std;

int parent[1000001];

int find(int a) {
    if (parent[a] == a) return a;
    else return parent[a] = find(parent[a]); // O(N) 예방
}

void uni(int a, int b) {
    int aRoot = find(a);
    int bRoot = find(b);
    if (aRoot == bRoot) return;
    parent[aRoot] = bRoot;
}

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

    int n, m;
    cin >> n >> m;
    int c, a, b;

    for (int i = 0; i <= n; i++) {
        parent[i] = i;
    }

    while(m--) {
        cin >> c >> a >> b;
        if (c == 0) {
            uni(a, b);
        } else {
            if (find(a) == find(b)) {
                cout << "YES" << '\n';
            } else {
                cout << "NO" << '\n';
            }
        }
    }

    return 0;
}

https://www.acmicpc.net/problem/1039

풀이 과정

M자리 숫자 N에서 2개의 숫자의 위치를 K번 바꿨을 때 가능한 최대값을 구하는 문제이다.

한 숫자에서 교환해서 만들수 있는 모든 수를 탐색해가면서, K번 교환해서 만들 수 있는 수 중에서 가장 큰 값을 구해주면 된다. 일종의 BFS 문제이다.

소스 코드

#include <bits/stdc++.h>
using namespace std;

int N, K, M;

int swap(int num, int a, int b) { // a자리 숫자와 b자리 숫자의 교환
    int aDivisor = pow(10, a);
    int bDivisor = pow(10, b);
    int aNumber = (num / aDivisor) % 10;
    int bNumber = (num / bDivisor) % 10;

    if (aNumber == 0 && b == M-1) return -1;

    return num - (aNumber*aDivisor + bNumber*bDivisor) + (aNumber*bDivisor + bNumber*aDivisor);
}

int main() {
    cin >> N >> K;
    int n = N;

    for (M = 1; M < 7; M++) { // N이 몇자리 수인지 M에 저장
        n /= 10;
        if (n == 0) break;
    }

    priority_queue<int> q[2]; // 최대 힙으로 K번째 교환시 가장 큰 수를 top으로 빠르게 탐색
    int t = 0, nt = 1; // 토글

    q[t].push(N);
    int prev = -1;

    for (int k = 0; k < K; k++) {
        prev = -1;
        while(!q[t].empty()) { // BFS
            int num = q[t].top();
            q[t].pop();

            if (num == prev) continue; // 같은 수를 2번 넣을 필요는 없다
            prev = num;

            int next;
            for (int a = 0; a < M; a++) { // 교환해서 만들 수 있는 모든 수를 힙에 저장
                for (int b = a+1; b < M; b++) {
                    next = swap(num, a, b);
                    if(next != -1) q[nt].push(next);
                }
            }
        }

        t = nt;
        nt = (nt + 1) & 1; // 힙 토글
    }

    if (q[t].empty()) cout << "-1\n";
    else {
        int result = q[t].top();
        cout << result << '\n';
    }

    return 0;
}