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

위상정렬을 수행하는데 사이클이 존재하면

계속해서 degree가 0이 되지 않기 때문에

#include <bits/stdc++.h>

using namespace std;

int n, m;
int degree[1001];
vector<int> adj[1001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
   
    cin >> n >> m;
    // 그래프 만들기 
    for (int i = 0; i < m; i++) {
        int tmp;
        cin >> tmp;

		int pre = -1;
        for (int j = 0; j < tmp; j++) {
            int now;
            cin >> now;
            if (pre != -1) {
                adj[pre].push_back(now);
                degree[now]++;
            }
            pre = now;
        }
    }

    vector<int> order;
    queue<int> Q;
    for (int i = 1; i <= n; i++) {
        if (degree[i] == 0) {
            Q.push(i);
        }
    }

    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();
        order.push_back(x);


        for (auto nx : adj[x]) {
            if (degree[nx] > 0) {
				degree[nx]--;
                if (degree[nx] == 0) {
                    Q.push(nx);
                }
            }
        }
    }

    if (order.size() == n) {
        for (auto x : order) {
            cout << x << '\n';
        }
    }
    else {
        cout << 0 << '\n';
    }




    return 0;
}

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

#include <bits/stdc++.h>

using namespace std;

int n, m;

int arr[1001][1001];
vector<pair<int, int> > wall;
bool ch[1001][1001];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int num[1001][1001];
int marked[1001*1001]; // cnt[mark] = 개수 


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
   
    cin >> n >> m;
    for (int i = 0; i < n; i++) {

        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            arr[i][j] = s[j]-'0';
            if (arr[i][j]) wall.push_back({ i,j });
        }
    }

    int mark = 1;
	queue<pair<int, int> > Q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            
            if (arr[i][j] == 0 && num[i][j] == 0) {
				int cnt = 1;
                Q.push({ i,j });
                num[i][j] = mark;
                while (!Q.empty()) {
                    int x = Q.front().first;
                    int y = Q.front().second;
                    Q.pop();

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

                        if (nx < 0 || nx >= n || ny < 0 || ny >= m || num[nx][ny] || arr[nx][ny]) continue;
                        Q.push({ nx,ny });
                        cnt++;
                        num[nx][ny] = mark;
                    }
                }
				marked[mark] = cnt;
				mark++;
            }
        }
    }

    for (int i = 0; i < wall.size(); i++) {
        int x = wall[i].first;
        int y = wall[i].second;

        int wall_cnt = 1;
        set<int> s;

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

			if (nx < 0 || nx >= n || ny < 0 || ny >= m || arr[nx][ny] > 0) continue;
            s.insert(num[nx][ny]);
        }

        for (auto k : s) {
            wall_cnt += marked[k];
        }
        arr[x][y] = (wall_cnt % 10);
    }




    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << arr[i][j];
        }
        cout << '\n';
    }
    return 0;
}

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

#include <bits/stdc++.h>

using namespace std;

const int MAX = 60;

const int NODE_MAX = 3001;
const int INF = 1e9;
int n, m , sum, res;
pair<int,int> arr[MAX][MAX]; // node_num, val 

int c[NODE_MAX][NODE_MAX], f[NODE_MAX][NODE_MAX], d[NODE_MAX];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
vector<int> adj[NODE_MAX];


void maxFlow(int start, int end) {
    while (1) {
        memset(d, -1, sizeof(d));
        queue<int> Q;
        Q.push(start);

        while (!Q.empty() && d[end] == -1) {
            int x = Q.front(); Q.pop();

            for (auto nx : adj[x]) {
                if (d[nx] == -1 && c[x][nx] - f[x][nx] > 0) {
                    Q.push(nx);
                    d[nx] = x;
                    if (nx == end) break;
                }
            }
        }

        if (d[end] == -1) break;
        int flow = INT_MAX;
        for (int i = end; i != start; i = d[i]) {
            flow = min(flow, c[d[i]][i] - f[d[i]][i]);
        }

        for (int i = end; i != start; i = d[i]) {
            f[d[i]][i] += flow;
            f[i][d[i]] -= flow;
        }

        res += flow;
    }
}

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

    int t;
    cin >> t;
    for (int T = 0; T < t; T++) {
        memset(c, 0, sizeof(c));
        memset(f, 0, sizeof(f));
        
        sum = 0, res = 0;
        for (int i = 0; i < NODE_MAX; i++) adj[i].clear();

        cin >> n >> m;

        int Node_num = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int tmp;
                cin >> tmp;
                sum += tmp;

                arr[i][j].first = Node_num;
                arr[i][j].second = tmp;

                if ((i + j) % 2 == 0) {
                    adj[0].push_back(Node_num);
                    adj[Node_num].push_back(0);
                    c[0][Node_num] = tmp;
                }
                else {
                    adj[3000].push_back(Node_num);
                    adj[Node_num].push_back(3000);
                    c[Node_num][3000] = tmp;
                }

                Node_num++;
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {

                if ((i + j) % 2 == 0) {
					int now = arr[i][j].first;

					for (int k = 0; k < 4; k++) {

						int nx = i + dx[k];
						int ny = j + dy[k];

						if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;

						int next_node = arr[nx][ny].first;

						adj[now].push_back(next_node);
						adj[next_node].push_back(now);
						c[now][next_node] = INF;
					}
                }

            }
        }


        maxFlow(0, 3000);

        cout << sum - res << '\n';
    }



    return 0;
}

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

1.문제접근 및 알고리즘

최대 유량이 흐르는 상태를 구현한 뒤

간선마다 검사를 해주면서 더이상 유량이 흐를수 없는 상태라면

즉 해당 간선의 용량과 흐르는 유량이 일치하는 상태라면

그 간선은 완전 중요한 간선이 된다.

2. 주의할점

1.

 a 에서 b 로 가는 간선이 여러개 있을 수 있으니

용량을 계속 더해주어야한다

2.

계속 푸는데 시간초과가 나서 for문을 auto로 바꿔주니 시간초과가 해결되었다.

앞으로는 웬만하면 auto를 사용해주어야겠다.

3. 문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;

const int MAX = 333;

int c[MAX][MAX], f[MAX][MAX], d[MAX];
vector<int> adj[MAX];
vector<pair<int, int> > edge;
int n, m;

void maxFlow(int start, int end) {
    while (1) {
        memset(d, -1, sizeof(d));
        queue<int> Q;
        Q.push(start);

        while (!Q.empty() && d[end] == -1) {
            int x = Q.front();
            Q.pop();

            for(auto nx : adj[x]){
                if (c[x][nx] - f[x][nx] > 0 && d[nx] == -1) {
                    d[nx] = x;
                    Q.push(nx);
                    if (nx == end) break;
                }
            }
        }

        if (d[end] == -1) break;
        int flow = INT_MAX;

        for (int i = end; i != start; i = d[i]) {
            flow = min(flow, c[d[i]][i] - f[d[i]][i]);
        }

        for (int i = end; i != start; i = d[i]) {
            f[d[i]][i] += flow;
            f[i][d[i]] -= flow;
        }
    }


}

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

    int k;
    cin >> k;
    for (int T = 0; T < k; T++) {
        memset(c, 0, sizeof(c));
        memset(f, 0, sizeof(f));
        for (int i = 0; i < MAX; i++) adj[i].clear();
        edge.clear();
        cin >> n >> m;

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

            c[a][b] += d;
            adj[a].push_back(b);
            adj[b].push_back(a);
            edge.push_back({ a,b });
        }


        maxFlow(1, n);

        int ans = 0;

        for (int i = 0; i < edge.size(); i++) {
            int S = edge[i].first;
            int T = edge[i].second;
            int prev[MAX];
            memset(prev, -1, sizeof(prev));

            queue<int> Q;
            Q.push(S);

            while (!Q.empty()) {
                int x = Q.front();
                Q.pop();

                for (auto nx : adj[x]) {
                    if (prev[nx] == -1 && c[x][nx] - f[x][nx] > 0) {
                        prev[nx] = x;
                        Q.push(nx);
                    }
                }
            }

            if (prev[T] == -1) ans++;
        }

        cout << ans << '\n';
    }


    return 0;
}

저 많은 시간초과들은

for문을 auto를 이용해서 돌도록 하니까 해결이 되었다..

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

이 문제에서는 도시를 한번만 방문하면서

최대 유량을 구해야한다.

도시를 한번만 방문해야하는 조건을 구현하기 위해

정점을 분할해주어야한다.

정점을 분할해주고 정점과 정점' 를 연결해주는 간선의 Capacity를 1로 두면

해당 정점을 최대 한 번만 방문하도록 할 수 있다.

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

const int MAX = 810;
int n, p, res;
int c[MAX][MAX], f[MAX][MAX], d[MAX];
vector<int> adj[MAX];

void maxFlow(int start, int end) {
    while (1) {
        fill(d, d + MAX, -1);

        queue<int> Q;
        Q.push(start);
        d[start] = 0;

        while (!Q.empty() && d[end] == -1) {
            int x = Q.front();
            Q.pop();

            for (int i = 0; i < adj[x].size(); i++) {
                int nx = adj[x][i];

                if (d[nx] == -1 && c[x][nx] - f[x][nx] > 0) {
                    Q.push(nx);
                    d[nx] = x;

                    if (nx == end) break;
                }

            }
        }

        if (d[end] == -1) break;
        int flow = INT_MAX;
        for (int i = end; i != start; i = d[i]) {
            flow = min(flow, c[d[i]][i] - f[d[i]][i]);
        }
        for (int i = end; i != start; i = d[i]) {
            f[d[i]][i] += flow;
            f[i][d[i]] -= flow;
        }

        res += flow;
    }
}



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

    cin >> n >> p;

    for (int i = 1; i <= n; i++) {
		int x = 2 * i;
        int x_ = 2 * i - 1;

        c[x][x_] = 1;
        adj[x_].push_back(x);
        adj[x].push_back(x_);
    }

    for (int i = 0; i < p; i++) {
        int a, b;
        cin >> a >> b;
        int u = a * 2;
		int u_ = a * 2 - 1;

		int v = b * 2;
        int v_ = b * 2 - 1;

        c[u_][v] = 1;
        c[v_][u] = 1;
        adj[u_].push_back(v);
        adj[v].push_back(u_);

        adj[v_].push_back(u);
        adj[u].push_back(v_);
    }

    maxFlow(1, 4);

    cout << res << '\n';
    return 0;
}

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

1.문제설명

1번에서 2번으로 갈 수 있는 모든 경로를 구해야 한다.

단 한 경로에 포함된 길이 다른 경로에 포함되면 안된다

2.접근방법[알고리즘]

문제가 처음 접했을 때 DFS로 노드를 순환하면서 풀 수 있을 것 같지만

그럴 수 없다.

이 문제는 Network Flow(최대유량) 알고리즘을 알아야 풀 수 있다.

한 간선을 한 번씩 방문할 수 있을 때 2번으로 갈 수 있는 경우가 몇 개 인지 구해야한다.

한 간선을 한 번씩 방문할 수 있다는 말은

한 간선에 1명만 이동할 수 있다는 말과 같고

이 때 2번으로 총 몇명이 도착 할 수 있는지 최대유량을 구해야 하는 문제다.

3.문제풀이코드 C++

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

const int MAX = 401;

int n, p,res;
int c[MAX][MAX], f[MAX][MAX], d[MAX];
vector<int> adj[MAX];

void maxFlow(int start, int end) {
    while (1) {
		fill(d, d + MAX, -1);
        queue<int> Q;
        d[start] = 0;
        Q.push(start);

        while (!Q.empty() && d[end] == -1) {
            int x = Q.front();
            Q.pop();
            for (int i = 0; i < adj[x].size(); i++) {
                int nx = adj[x][i];

                if (d[nx] == -1 && c[x][nx] - f[x][nx] > 0) {
                    Q.push(nx);
                    d[nx] = x;
                    if (nx == end) break;
                }
            }
        }

        if (d[end] == -1) break;

        int flow = INT_MAX;
        for (int i = end; i != start; i = d[i]) {
            flow = min(flow, c[d[i]][i] - f[d[i]][i]);
        }
        for (int i = end; i != start; i = d[i]) {
            f[d[i]][i] += flow;
            f[i][d[i]] -= flow;
        }

        res += flow;
    }


}

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

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

        c[a][b] = 1;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    maxFlow(1, 2);

    cout << res << '\n';
   

    return 0;
}

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

처음에 재귀함수로 풀다가 계속 시간초과가 나서 

dp로 풀었다

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

int n, ans = INT_MAX;
vector<int> v;

int dp[100001];

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

    fill(dp+1, dp + 100001, INT_MAX);
    cin >> n;

	for (int i = 1; i * i <= n; i++) {
        int tmp = i * i;
        for (int j = 0; j <= n; j++) {
            if (j - tmp >= 0) {
                dp[j] = min(dp[j], dp[j - tmp] + 1);
            }
        }
	}


    cout << dp[n] << '\n';

    return 0;
}

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

시간초과 이유

ios::sync_with_stdio(0);
cin.tie(0);

입출력을 cin, cout으로 할 경우

위 두줄을 써주지 않으면 시간초과가 발생합니다.

위 두줄에 대한 설명은 하단 링크를 참고하시면 됩니다.

https://dingcoding.tistory.com/62

cin, cout을 사용하지 않고

scanf printf 로 입출력을 하면 통과가 되는 것 같아요.

슬라이딩 윈도우 알고리즘

저도 이 문제를 풀면서 이 방법이 슬라이딩 윈도우라고 하는 걸 처음 알았네요

1 2 3 4 5 6 7 8 9 10 11 12 13

1부터 10까지의 합은 55입니다.

그렇다면 2부터 11까지의 합을 구하는 방법은

2 , 3, 4 ... 11까지 더하는 방법과

1부터 10의 합에서 1을 빼고 11을 더해주는 방법이 있습니다.

두번째 방법을 슬라이딩 윈도우 알고리즘이라고 하네요

입력받는 수가 500만 정도 되기 때문에

가능하면 시간 복잡도 O(N)과 가깝게 해결해야합니다.

1 5 2 3 6 2 3 7 3 5 2 6

1에서 최솟값은 1

1 5에서 최솟값은 1

1 5 2 에서 최솟값은 1입니다

5 2 3의 최솟값은 2

2 3 6 의 최솟값은 3

3 6 2의 최솟값은 2

...

하다보면 작은 수만 중요하다는 걸 알게 됩니다.

숫자를 덱에 입력받으면서,

현재 입력받은 숫자보다 앞에 등장한 수가 크다면

앞에 있는 큰 수 들을 pop 해주면서 작은 숫자 위주로 저장합니다.

그러다보면 자연적으로 덱의 front로 작은 숫자가 밀리게 되는데

작은 숫자의 값이 구간에 해당하지 않는다면 역시 pop 해주면 됩니다.

숫자를 하나씩 받아가면서 필요없는 건 제거해주는 과정이

슬라이딩 윈도우 알고리즘과 동일합니다.

문제풀이코드 C++

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

int n, l, arr[5000001];

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

    cin >> n >> l;

    deque<int> dq;

    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        arr[i] = t;

        if (dq.empty()) {
            dq.push_back(t);
        }
        else {
            while (!dq.empty() && dq.back() > t) {
                dq.pop_back();
            }
            dq.push_back(t);
        }

        if ((i - l >= 0) && (arr[i - l] == dq.front())) {
            dq.pop_front();
        }

        cout << dq.front() << ' ';
    }

}