[C++ 알고리즘] 코딩테스트에 유용한 알고리즘 코드 모음

그래프

DFS, BFS

#include <iostream>
#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;
    cout<< V << endl;
    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> q;
    q.push(V);
    while(!q.empty()) {
        int cur = q.front();
        cout << cur << endl;
        q.pop();
        for(int i = 0; i < Graph[cur].size(); i++) {
            int Next = Graph[cur][i];
            if(!Visit[Next]) {
                Visit[Next] = true;
                q.push(Next);
            }
        }
    }
}

 

DP

첫 번째 방법 : 재귀하되 저장 / 위 부터 계산해서 내려가는 Top-Down 방식

int save[100];
int DP(int x) {
    if(x == 1) return 1;
    if(x == 2) return 1;
    if(save[x] != 0) return save[x];    // 처음 만난 문제가 아닐경우, 기존것 불러오기
    return save[x] = DP(x-1) + DP(x+1);    // 처음 만난 문제라면 계산하기
}

 

두 번째 방법 : 재귀안하고 반복문으로 처음부터 저장 / 아래부터 계산해서 올라가는 Bottom-Up 방식

int save[100];
int DP(int x) {
    save[0] = 0;
    save[1] = 1;
    for(int i = 2; i <= n; i++) {
        save[i] = save[i-1] + save[i-2];
    }
    return save[x];
}