[C++ 알고리즘] 각종 알고리즘의 외워두면 유용한 정석 코드 모음

이 포스트에서는 C++으로 작성된 각종 알고리즘들의 형식적으로 코드를 정리하였습니다.

코드를 작성할 때마다 그 형태와 구성이 달라지면 불편하기 때문에 이를 해결하고자 작성하게 되었습니다.

- 각 알고리즘은 분야별로 정리되어 있습니다. (분류된 분야가 정확하지 않을 수 있습니다.)

- 같은 분야 내에서는 웬만하면 난이도 오름차순으로 정리하고자 하였습니다.

** 개인적으로 자주 사용하는 알고리즘 위주로 정리하였습니다! (필요한 알고리즘이 없을 수도 있음)

 

알고리즘은 참고용으로만 봐주세요.

문제 풀이를 할 때는, 웬만해서는 직접 다시 생각해보면서 코드를 직접 작성하는 것을 추천합니다.

코드는 포스트의 가독성을 최대화하고자 접은 글에 정리하였으니, 접은 글을 펼쳐서 코드를 복사하시면 됩니다.

+ 일부 알고리즘은 C로 작성된 것도 있으니, 메모리 제한에 걸릴 경우 C++의 vector로 바꿔서 사용하시면 됩니다.

 

 

각종 라이브러리 응용

벡터 Swap Trick & 배열 초기화

int Capacity[MAX][MAX];
vector<int> Line[MAX];

fill(&Capacity[0][0], &Capacity[MAX-1][MAX], 0); // for 2 dimensional array

vector<int>().swap(Line); // for 1 dimensional vector
for(int i=0; i<MAX; i++) vector<int>().swap(Line[i]); // for 2 dimensional vector

 

정수론

유클리드 호제법 (최대공약수)

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

int GCD(int X, int Y) {
    if(X < Y) swap(X, Y);
    while(Y != 0) {
        int Temp = X%Y;
        X = Y;
        Y = Temp;
    }
    return X;
}

int main() {
    int X, Y;
    cin >> X >> Y;
    cout << GCD(X, Y);
}

 

에라토스테네스의 체 (소수 판별)

// A program to find a prime number up to N using a "Sieve of Eratosthenes".
#include <cstdio>
#include <vector>
using namespace std;

vector<int> Arr;

int main() {
    int N;
    scanf("%d", &N);
    Arr.resize(N+1);
    for(int i=2; i*i<=N; i++)
        for(int j=2; i*j<=N; j++) Arr[i*j] = 1;
    for(int i=1; i<=N; i++)
        if(!Arr[i]) printf("%d ", i);
}

 

 

기하

Convex Hull + 회전하는 캘리퍼스

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

struct Point { long long x, y; };
Point operator-(Point A, Point B) {
    Point C;
    C.x = A.x - B.x;
    C.y = A.y - B.y;
    return C;
}
vector<Point> Points;

long long Cross(Point A, Point B, Point C) {
    return A.x*(B.y-C.y) + B.x*(C.y-A.y) + C.x*(A.y-B.y);
}

bool Compare(Point A, Point B) {
    long long Value = Cross(Points[0], A, B);
    if(Value != 0) return Value > 0;
    else if(A.y != B.y) return A.y < B.y;
    else return A.x < B.x;
}

long long DistSq(Point A, Point B) {
    return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);
}

int main() {
    int N;
    scanf("%d", &N);
    Points.resize(N+1);
    for(int i=0; i<N; i++)
        scanf("%lld %lld", &Points[i].x, &Points[i].y);
    for(int i=1; i<N; i++)
        if(Points[i].y < Points[0].y || (Points[i].y == Points[0].y && Points[i].x < Points[0].x))
            swap(Points[0], Points[i]);
    sort(Points.begin()+1, Points.end(), Compare);

    // Convex Hull
    vector<Point> Convex;
    Point Temp1, Temp2, First;
    Convex.push_back(Points[0]);
    Convex.push_back(Points[1]);
    for(int i=2; i<N*4; i++) {
        while(Convex.size() >= 2) {
            Temp2 = Convex.back();
            Convex.pop_back();
            Temp1 = Convex.back();
            if(Cross(Temp1, Temp2, Points[i]) > 0) {
                Convex.push_back(Temp2);
                break;
            }
        }
        Convex.push_back(Points[i]);
    }

    // Rotating Calipers
    int Size = Convex.size(), LPoint = 0, RPoint = 0;
    for(int i=0; i<Size; i++) {
        if(Convex[i].x < Convex[LPoint].x) LPoint = i;
        if(Convex[i].x > Convex[RPoint].x) RPoint = i;
    }
    int DiaSq = DistSq(Convex[LPoint], Convex[RPoint]);
    Point Origin; Origin.x = 0, Origin.y = 0;
    for(int i=0; i<Size; i++) {
        if(Cross(Origin, Convex[(LPoint+1)%Size]-Convex[LPoint], Convex[RPoint]-Convex[(RPoint+1)%Size]) > 0)
            LPoint = (LPoint + 1)%Size;
        else RPoint = (RPoint + 1)%Size;
        if(DistSq(Convex[LPoint], Convex[RPoint]) > DiaSq)
            DiaSq = DistSq(Convex[LPoint], Convex[RPoint]);
    }
    printf("%lld\n", DiaSq);
}

 

다각형 내부의 점 판정

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#define N 3
using namespace std;

struct Point { int x, y; };
Point operator-(Point A, Point B) {
    Point C;
    C.x = A.x - B.x, C.y = A.y - B.y;
    return C;
}
vector<Point> Poly;

int Abs(int A) { return A>=0?A:-A; }

int Cross(Point A, Point B, Point C) {
    Point AB = B-A;
    Point AC = C-A;
    return AB.x*AC.y - AB.y*AC.x;
}

bool CompareCross(Point A, Point B) {
    int Value = Cross(Poly[0], A, B);
    if(Value) return Value > 0;
    else if(A.y != B.y) return A.y < B.y;
    else return A.x < B.x;
}

bool isInPoly(vector<Point> &Poly, Point P) {
    int Size = Poly.size();
    Point Origin; Origin.x = 0, Origin.y = 0;
    Point LeftV = Poly[Size-1] - Poly[0];
    Point RightV = Poly[1] - Poly[0];
    Point PointV = P - Poly[0];
    if(Cross(Origin, LeftV, PointV) > 0) return false;
    if(Cross(Origin, RightV, PointV) < 0) return false;

    int Left = 1, Right = Size - 1;
    while(Left+1 < Right) {
        int Mid = (Left + Right)/2;
        Point MidV = Poly[Mid] - Poly[0];
        if(Cross(Origin, MidV, PointV) > 0) Left = Mid;
        else Right = Mid;
    }
    Point V1 = P - Poly[Left];
    Point V2 = Poly[Left+1] - P;
    return Cross(Origin, V1, V2) <= 0;
}

int main() {
    Poly.resize(N);
    for(int i=0; i<N; i++) scanf("%d %d", &Poly[i].x, &Poly[i].y);
    for(int i=1; i<N; i++)
        if(Poly[i].y < Poly[0].y || (Poly[i].y == Poly[0].y && Poly[i].x < Poly[0].x))
            swap(Poly[0], Poly[i]);
    sort(Poly.begin()+1, Poly.end(), CompareCross);

    stack<Point> Convex;
    Convex.push(Poly[0]);
    Convex.push(Poly[1]);
    for(int i=2; i<N; i++) {
        while(Convex.size() >= 2) {
            Point Temp2 = Convex.top();
            Convex.pop();
            Point Temp1 = Convex.top();
            if(Cross(Temp1, Temp2, Poly[i]) > 0) {
                Convex.push(Temp2);
                break;
            }
        }
        Convex.push(Poly[i]);
    }
    vector<Point> SortedPoly;
    int Size = Convex.size();
    SortedPoly.resize(Size);
    for(int i=Size-1; i>=0; i--) {
        SortedPoly[i] = Convex.top();
        Convex.pop();
    }

    int M, Cnt = 0;
    scanf("%d", &M);
    for(int i=0; i<M; i++) {
        Point P;
        int x, y;
        scanf("%d %d", &x, &y);
        P.x = x, P.y = y;
        if(isInPoly(SortedPoly, P)) Cnt++;
    }
    printf("%.1lf\n", (double)Abs(Cross(SortedPoly[0], SortedPoly[1], SortedPoly[2]))*0.5);
    printf("%d", Cnt);
}

 

 

자료 구조

세그먼트 트리 (Min, Max)

#include <cstdio>
#include <vector>
#include <algorithm>
#define INF 1000001
using namespace std;

vector<int> Min, Max;

void updateTree(int Node, int Begin, int End, int Index, int Value) {
    if(Index < Begin || Index > End) return;
    if(Begin == End) {
        Min[Node] = Max[Node] = Value;
        return;
    }
    int Mid = (Begin + End)/2;
    updateTree(Node*2, Begin, Mid, Index, Value);
    updateTree(Node*2+1, Mid+1, End, Index, Value);
    Min[Node] = min(Min[Node*2], Min[Node*2+1]);
    Max[Node] = max(Max[Node*2], Max[Node*2+1]);
}

int findMin(int Node, int Begin, int End, int Left, int Right) {
    if(Left > End || Right < Begin) return INF;
    if(Left <= Begin && Right >= End) return Min[Node];
    int Mid = (Begin + End)/2;
    return min(findMin(Node*2, Begin, Mid, Left, Right), findMin(Node*2+1, Mid+1, End, Left, Right));
}

int findMax(int Node, int Begin, int End, int Left, int Right) {
    if(Left > End || Right < Begin) return 0;
    if(Left <= Begin && Right >= End) return Max[Node];
    int Mid = (Begin + End)/2;
    return max(findMax(Node*2, Begin, Mid, Left, Right), findMax(Node*2+1, Mid+1, End, Left, Right));
}

int main() {
    int N, Q, H, Left, Right;
    scanf("%d %d", &N, &Q);
    Min.resize(N*4+1), Max.resize(N*4+1);
    for(int i=1; i<=N; i++) {
        scanf("%d", &H);
        updateTree(1, 1, N, i, H);
    }
    for(int i=0; i<Q; i++) {
        scanf("%d %d", &Left, &Right);
        printf("%d\n", findMax(1, 1, N, Left, Right)-findMin(1, 1, N, Left, Right));
    }
}

 

 

그래프

DFS, BFS

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define MAX 1000
using namespace std;

int N;
vector<int> Graph[MAX+1];
vector<bool> Visit;

void DFS(int V) {
    Visit[V] = true;
    printf("%d ", V);
    for(int i=0; i<Graph[V].size(); i++) {
        int Next = Graph[V][i];
        if(!Visit[Next]) DFS(Next);
    }
}

void BFS(int V) {
    Visit[V] = true;
    queue<int> Queue;
    Queue.push(V);
    while(!Queue.empty()) {
        int Pop = Queue.front();
        printf("%d ", Pop);
        Queue.pop();
        for(int i=0; i<Graph[Pop].size(); i++) {
            int Next = Graph[Pop][i];
            if(!Visit[Next]) {
                Visit[Next] = true;
                Queue.push(Next);
            }
        }
    }
}

int main() {
    int M, Begin, X, Y;
    scanf("%d %d %d", &N, &M, &Begin);
    Visit.resize(N+1);
    for(int i=0; i<M; i++) {
        scanf("%d %d", &X, &Y);
        Graph[X].push_back(Y);
        Graph[Y].push_back(X);
    }
    // for(int i=1; i<=N; i++) sort(Graph[i].begin(), Graph[i].end()); // Use when need sorting
    DFS(Begin); printf("\n");
    fill(Visit.begin(), Visit.end(), false);
    BFS(Begin);
}

 

트리 지름

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

int max_cost = 0, deep_node = 1;
vector<pair<int, int>> node[100005];

void DFS(int cur, int prev, int cost) {
    if(cost > max_cost) {
        max_cost = cost;
        deep_node = cur;
    }
    for(int i=0; i<node[cur].size(); i++)
        if(node[cur][i].first != prev) DFS(node[cur][i].first, cur, cost+node[cur][i].second);
}

int main() {
    int V, a, b, c;
    cin >> V;
    for(int i=0; i<V; i++) {
        cin >> a;
        while(1) {
            cin >> b;
            if(b == -1) break;
            cin >> c;
            node[a].push_back(make_pair(b, c));
        }
    }
    DFS(1, 0, 0);
    max_cost = 0;
    DFS(deep_node, 0, 0);
    cout << max_cost;
}

 

LCA (최소 공통 조상)

#include <cstdio>
#include <vector>
#define MAX 100001
using namespace std;
 
int Parent[MAX][20], Depth[MAX], H = 0;
vector<int> Line[MAX];
 
void findParent(int Par, int Node, int Dep) {
    if(!Line[Node].size()) return;
    Parent[Node][0] = Par;
    Depth[Node] = Dep;
    for(int i=0; i<Line[Node].size(); i++)
        if(Line[Node][i] != Par) findParent(Node, Line[Node][i], Dep+1);
}
 
int findLCA(int A, int B) {
    if(Depth[A] != Depth[B]) {
        if(Depth[A] < Depth[B]) swap(A, B);
        int Diff = Depth[A] - Depth[B];
        for(int i=0; Diff>0; i++) {
            if(Diff%2) A = Parent[A][i];
            Diff >>= 1;
        }
    }
    if(A != B) {
        for(int i=H; i>=0; i--)
            if(Parent[A][i] != 0 && Parent[A][i] != Parent[B][i]) {
                A = Parent[A][i];
                B = Parent[B][i];
            }
        A = Parent[A][0];
    }
    return A;
}
 
int main() {
    int N, M, A, B;
    scanf("%d", &N);
    for(int i=0; i<N-1; i++) {
        scanf("%d %d", &A, &B);
        Line[A].push_back(B);
        Line[B].push_back(A);
    }
    findParent(0, 1, 0);
    int temp = N;
    while(temp > 1) {
        temp /= 2;
        H++;
    }
    for(int i=1; i<=H; i++)
        for(int j=2; j<=N; j++)
            if(Parent[j][i-1]) Parent[j][i] = Parent[Parent[j][i-1]][i-1];
    scanf("%d", &M);
    for(int i=0; i<M; i++) {
        scanf("%d %d", &A, &B);
        printf("%d\n", findLCA(A, B));
    }
}

 

최대 유량 (Network Flow)

#include <bits/stdc++.h>
#define MAX 105
#define INF 1e9
using namespace std;

vector<int> Line[MAX];
int Capacity[MAX][MAX], Flow[MAX][MAX];

void AddEdge(int From, int To) {
    Line[From].push_back(To), Line[To].push_back(From);
    Capacity[From][To] = 1;
}

int MaxFlow(int Sour, int Sink) {
    int FlowSum = 0;
    while(true) {
        int Parent[MAX]; fill(Parent, Parent+MAX, -1);
        queue<int> Queue; Queue.push(Sour);

        while(!Queue.empty() && Parent[Sink] == -1) {
            int Curr = Queue.front(); Queue.pop();
            for(int i=0; i<Line[Curr].size(); i++) {
                int Next = Line[Curr][i];
                if(Capacity[Curr][Next] - Flow[Curr][Next] > 0 && Parent[Next] == -1) {
                    Queue.push(Next);
                    Parent[Next] = Curr;
                }
            }
        }
        if(Parent[Sink] == -1) break;

        int Amount = INF;
        for(int i=Sink; i!=Sour; i=Parent[i])
            Amount = min(Amount, Capacity[Parent[i]][i] - Flow[Parent[i]][i]);
        for(int i=Sink; i!=Sour; i=Parent[i]) {
            Flow[Parent[i]][i] += Amount;
            Flow[i][Parent[i]] -= Amount;
        }
        FlowSum += Amount;
    }
    return FlowSum;
}

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

    int N, M, Sour = 101, Sink = 102;
    cin >> N >> M;
    for(int i=1; i<=N; i++) AddEdge(Sour, i);
    for(int i=1; i<=M; i++) AddEdge(50+i, Sink);
}

 

최소 비용 최대 유량 (MCMF)

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 605
#define INF 1000000000
using namespace std;

int Capacity[MAX][MAX], Flow[MAX][MAX], SinCost[MAX][MAX];
vector<int> Line[MAX];

void AddLine(int From, int To, int Cap, int Cost) {
    Line[From].push_back(To), Line[To].push_back(From);
    Capacity[From][To] = Cap;
    SinCost[From][To] = Cost, SinCost[To][From] = -Cost;
}

int MCMF(int Sour, int Sink) {
    int CostSum = 0;
    while(true) {
        int Prev[MAX], Cost[MAX];
        fill(Prev, Prev+MAX, -1);
        fill(Cost, Cost+MAX, INF);
        Cost[Sour] = 0;

        queue<int> Queue;
        Queue.push(Sour);

        bool isInQueue[MAX];
        fill(isInQueue, isInQueue+MAX, false);
        isInQueue[Sour] = true;

        while(!Queue.empty()) {
            int Curr = Queue.front();
            Queue.pop();
            isInQueue[Curr] = false;
            for(int i=0; i<Line[Curr].size(); i++) {
                int Next = Line[Curr][i];
                if(Capacity[Curr][Next] - Flow[Curr][Next] > 0
                   && Cost[Curr] + SinCost[Curr][Next] < Cost[Next]) {
                    Cost[Next] = Cost[Curr] + SinCost[Curr][Next];
                    Prev[Next] = Curr;
                    if(!isInQueue[Next]) {
                        Queue.push(Next);
                        isInQueue[Next] = true;
                    }
                }
            }
        }
        if(Prev[Sink] == -1) break;

        int Amount = INF;
        for(int i=Sink; i!=Sour; i=Prev[i])
            Amount = min(Amount, Capacity[Prev[i]][i] - Flow[Prev[i]][i]);
        for(int i=Sink; i!=Sour; i=Prev[i]) {
            CostSum += Amount*SinCost[Prev[i]][i];
            Flow[Prev[i]][i] += Amount;
            Flow[i][Prev[i]] -= Amount;
        }
    }
    return CostSum;
}

int main() {
    int T, N, M, Start, Sour, Sink, From, To;
    scanf("%d", &T);
    for(int t=0; t<T; t++) {
        fill(&Capacity[0][0], &Capacity[MAX-1][MAX], 0);
        fill(&Flow[0][0], &Flow[MAX-1][MAX], 0);
        fill(&SinCost[0][0], &SinCost[MAX-1][MAX], INF);
        for(int i=0; i<MAX; i++) vector<int>().swap(Line[i]);

        scanf("%d %d", &N, &M);
        Start = 2*N+1, Sour = 2*N+2, Sink = 2*N+3;
        AddLine(Sour, Start, 2, 0);
        for(int i=1; i<=N; i++) {
            AddLine(Start, i, 1, 0);
            AddLine(i, i+N, 1, -1);
            AddLine(i+N, Sink, 1, 0);
        }
        for(int i=0; i<M; i++) {
            scanf("%d %d", &From, &To);
            AddLine(From+N, To, 1, 0);
        }
        printf("%d\n", -MCMF(Sour, Sink));
    }
}

 

 

DP

투 포인터 (부분합)

#include <cstdio>
#define INF 100005
using namespace std;

int main() {
    int N, S, left = 0, right = 0, sum = 0, length = INF;
    int arr[100005] = {0, };
    scanf("%d %d", &N, &S);
    for(int i=0; i<N; i++) scanf("%d", &arr[i]);
    sum = arr[0];
    while(left <= right && right < N) {
        if(sum < S) sum += arr[++right];
        else if(sum == S) {
            if(right-left+1 < length) length = right-left+1;
            sum += arr[++right];
        }
        else if(sum > S) {
            if(right-left+1 < length) length = right-left+1;
            sum -= arr[left++];
        }
    }
    if(length == INF) printf("0");
    else printf("%d", length);
}

 

 

문자열

해시맵

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main() {
    int N, M;
    string id, pw;
    map <string, string> account;
    cin >> N >> M;
    for(int i=0; i<N; i++) {
        cin >> id >> pw;
        account[id] = pw;
    }
    for(int i=0; i<M; i++) {
        cin >> id;
        cout << account[id] << '\n';
    }
}

 

KMP (문자열 탐색)

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

vector<int> GetPi(string Pattern) {
    vector<int> Pi(Pattern.length());
    for(int i=1, j=0; i<Pattern.length(); i++) {
        while(j>0 && Pattern[i] != Pattern[j]) j = Pi[j-1];
        if(Pattern[i] == Pattern[j]) Pi[i] = ++j;
    }
    return Pi;
}

vector<int> KMP(string Str, string Pattern) {
    vector<int> Pi = GetPi(Pattern), Pos;
    for(int i=0, j=0; i<Str.length(); i++) {
        while(j>0 && Str[i] != Pattern[j]) j = Pi[j-1];
        if(Str[i] == Pattern[j]) {
            if(j == Pattern.length()-1) {
                Pos.push_back(i-j);
                j = Pi[j];
            }
            else j++;
        }
    }
    return Pos;
}

int main() {
    string Str, Pattern;
    cin >> Str >> Pattern;
    vector<int> Pos = KMP(Str, Pattern);
    cout << !Pos.empty();
}