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

typedef long long ll;
bool ch[200];
bool Prime[200];


bool isPrime(int num){
    for(int i=2; i*i <=num; i++){
        if(num%i==0) return false;
    }
    return true;
}


//소인수분해
vector<ll> factorSimple(ll n){
    vector<ll> ret;

    ll sqrtn = ll(sqrt(n));
    for(ll div = 2; div<=sqrtn; div++){
        while(n%div==0){
            n/=div;
            ret.push_back(div);
        }
    }
    if(n>1) ret.push_back(n);

    return ret;
}

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

    ch[0] = 1;

    for(int i=2; i<100; i++){
        cout << i << ' ';
        if(isPrime(i)) cout << "is Prime" << '\n';
        else cout << "is not Prime" << '\n';
    }

    
    
    //slow erathostenes
    for(int i=2; i<200/2 + 1; i++){
        if(ch[i]==0){
            for(int j=i+i; j<200; j+=i){
                ch[j] = 1;
            }
        }
    }

    //fast erathostenes;
    int sqrtn = int(sqrt(200));
    for(int i=2; i<=sqrtn; i++) {
        if (Prime[i])
            for (int j = i * i; j <= 200; j++) {
                Prime[i] = 1;
            }
    }
    
    
    return 0;
}

i 가 루트 n보다 큰 경우에는

이미 이전에 계산한 적이 있기 때문에 생략할 수 있고,

j가 i*i보다 작은 경우도 마찬가지로

i가 i-1이하일 때 이미 계산된 적이 있기 때문에 생략할 수 있다.

그래서 보다 에라스토테네스 알고리즘을 최적화 할 수 있다.

https://www.youtube.com/watch?v=j_sdjivoPs8 

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

int arr[5][5];
int dp[5][5];
char P[5][5];


void path(int x, int y){
    if(x==1 && y==1){
        cout << x << ' ' << y << '\n';
        return;
    }
    else if(P[x][y]=='^'){
        path(x-1,y);
    }
    else if(P[x][y]=='<'){
        path(x,y-1);
    }

    cout << x << ' ' << y << '\n';
    return;
}


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

    arr[1][1] = 6;
    arr[1][2] = 7;
    arr[1][3] = 12;
    arr[1][4] = 5;
    arr[2][1] = 5;
    arr[2][2] = 3;
    arr[2][3] = 11;
    arr[2][4] = 18;
    arr[3][1] = 7;
    arr[3][2] = 17;
    arr[3][3] = 3;
    arr[3][4] = 3;
    arr[4][1] = 8;
    arr[4][2] = 10;
    arr[4][3] = 14;
    arr[4][4] = 9;



    for(int i=1; i<5; i++){
        for(int j=1; j<5; j++){
            cout << arr[i][j] << ' ';
        }
        cout << '\n';
    }

    for(int i=1; i<5; i++){
        for(int j=1; j<5; j++){
            if(i==1 && j==1) dp[i][j] = arr[i][j];
            else if(i==1) dp[i][j] = arr[i][j] + dp[i][j-1];
            else if(j==1) dp[i][j] = arr[i][j] + dp[i-1][j];
            else dp[i][j] = arr[i][j] + min(dp[i-1][j], dp[i][j-1]);
        }
    }

    cout << '\n';

    for(int i=1; i<5; i++){
        for(int j=1; j<5; j++){
            cout << dp[i][j] << ' ';
        }
        cout << '\n';
    }


    int x=4, y=4;



    for(int i=1; i<5; i++){
        for(int j=1; j<5; j++){
            if(i==1 && j==1) P[i][j] = '-';
            else if(dp[i-1][j] < dp[i][j-1] || j==1){
                P[i][j] = '^';
            }
            else{
                P[i][j] = '<';
            }
        }
    }

    cout << '\n';

    for(int i=1; i<5; i++){
        for(int j=1; j<5; j++){
            cout << P[i][j] << ' ';
        }
        cout << '\n';
    }


    path(4, 4);

    return 0;
}

우선순위 큐와 벡터 정렬 시간복잡도 차이

가끔 알고리즘 문제를 풀다보면 정렬하는 과정이 필요한 문제가 있습니다.

우선순위 큐

문제를 푸는 과정 중에서 원소의 삽입과 삭제를 할 때마다 정렬이 필요한 경우에는

Priority Queue 자료구조를 이용하여 쉽게 구현할 수 있습니다.

벡터

정렬된 결과가 필요할 때 array나 vector을 sort함수를 이용해 쉽게 정렬해줄 수 있습니다.

우선순위 큐 VS 벡터 Sort

그런데 특정 결과를 얻기 위해서 모든 원소를 한번 정렬해준 결과가 필요할 때

과연 우선순위 큐를 이용해서 pop해주면서 순서대로 사용하는 것과

벡터를 이용해서 한번 nlogn 으로 sort 해주는 것 중

어떤게 더 시간복잡도 상에서 빠른지 궁금해졌습니다.

https://stackoverflow.com/questions/3759112/whats-faster-inserting-into-a-priority-queue-or-sorting-retrospectively

결론

내용을 간단히 정리하면

자료 형태나 문제에 따라 다르겠지만

우선순위 큐에 n개의 항목을 삽입 하는 것은

점근적 복잡도 O(nlogn)를 가지므로 복잡도 측면 에서 결국 한 번 사용하는 것보다 효율적이지 않습니다.

즉 정렬이 최종적으로 한번 만 필요한 경우에는

vector 나 array를 한 번 sort 해주는 게 효율적입니다.

반대로 원소의 삽입과 pop이 빈번한 경우는 우선순위큐를 이용해

효율적으로 알고리즘을 구성할 수 있습니다.

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

#include <bits/stdc++.h>
#include <unordered_set>

#define MAX 800
#define INF 1e9;

using namespace std;

int n, 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) {
                    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;
        }

        res += flow;
    }
}

int CtoI(char c) {
    if (c <= 'Z') {
		return c - 'A';
    }
    else {
        return (c - 'a') + 26;
    }
}

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

    cin >> n;

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

        int u = CtoI(a);
        int v = CtoI(b);
        c[u][v] += q;
        c[v][u] += q;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    maxFlow(0, 25);

    cout << res << '\n';

    return 0;
}

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

int arr[100001];
bool vis[100001];
bool done[100001];

int cnt= 0;
void DFS(int x) {
    vis[x] = 1;
    int nx = arr[x];

    if (!vis[nx]) {
        DFS(nx);
    }
    else if(!done[nx]) {
        for (int i = nx; i != x; i = arr[i]) {
            cnt++;
        }
        cnt++;
    }

    done[x] = 1;
}


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

        memset(arr, 0, sizeof(arr));
        memset(vis, 0, sizeof(vis));
        memset(done, 0, sizeof(done));

        cnt = 0;

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

        
        for (int i = 1; i <= n; i++) {
            if (!vis[i]) {
                DFS(i);
            }
        }

        cout << n - cnt << '\n';
    }


    return 0;
}

DFS로 O(n)으로 cycle을 찾아 낼 수 있다

struct SegmentTree {
	int N;
	vector<int> tree;

	int merge(int left, int right) {
		return left + right;
	}

	int buildRec(const int arr[], int node, int nodeLeft, int nodeRight) {
		if (nodeLeft == nodeRight)
			return tree[node] = arr[nodeLeft];

		int mid = (nodeLeft + nodeRight) / 2;
		int leftVal = buildRec(arr, node * 2, nodeLeft, mid);
		int rightVal = buildRec(arr, node * 2 + 1, mid+1, nodeRight);

		return tree[node] = merge(leftVal, rightVal);
	}

	void build(const int arr[], int Size) {
		N = Size;
		tree.resize(N*4);
		buildRec(arr, 1, 0, N - 1);
	}


	int queryRec(int left, int right, int node, int nodeLeft, int nodeRight) {
		if (nodeRight < left || right < nodeLeft) return 0;

		if (left <= nodeLeft && nodeRight <= right) return tree[node];

		int mid = (nodeLeft + nodeRight) / 2;
		int leftVal = queryRec(left, right, node * 2, nodeLeft, mid);
		int rightVal = queryRec(left, right, node * 2 + 1, mid + 1, nodeRight);

		return merge(leftVal, rightVal);

	}

	int query(int left, int right) {
		return queryRec(left, right, 1, 0, N - 1);
	}

	// 하나만 업데이트
	int updateRec(int index, int newValue, int node, int nodeLeft, int nodeRight) {
		if (index < nodeLeft || nodeRight < index) {
			return tree[node];
		}
		if (nodeLeft == nodeRight) {
			return tree[node] = newValue;
		}


		int mid = (nodeLeft + nodeRight) / 2;
		int updateLeft = updateRec(index, newValue, node*2, nodeLeft, mid);
		int updateRight = updateRec(index, newValue, node*2+1, mid + 1, nodeRight);

		return tree[node] = merge(updateLeft, updateRight);
	}


	int update(int index, int newValue) {
		return updateRec(index, newValue, 1, 0, N - 1);
	}

	// 여러개 업데이트 
	int updateRec(int left, int right, int newValue, int node, int nodeLeft, int nodeRight) {
		if (nodeRight < left || right < nodeLeft) {
			return tree[node];
		}
		if (nodeLeft == nodeRight) {
			return tree[node] = newValue;
		}


		int mid = (nodeLeft + nodeRight) / 2;
		int updateLeft = updateRec(left,right, newValue, node * 2, nodeLeft, mid);
		int updateRight = updateRec(left,right, newValue, node * 2 + 1, mid + 1, nodeRight);

		return tree[node] = merge(updateLeft, updateRight);
	}


	int update(int left, int right, int newValue) {
		return updateRec(left , right, newValue, 1, 0, N - 1);
	}
};

처음엔 그래프 거리를 구하는 걸 냅색 알고리즘을 어떻게 응용해야할지 모르겠어서

우선순위큐 BFS를 이용해 풀어봤다.

답은 맞았다.

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

int n, m;

int arr[101][101], ch[101];

struct Edge{
	int node, dist;
	Edge(int a, int b){
		node = a;
		dist = b;
	}
	bool operator<(const Edge &e) const{
		return dist > e.dist;
	}
	
};

priority_queue<Edge> Q;

int DIST(int s,int e){

	int res = INT_MAX;
	Q.push(Edge(s,0));
	
	while(!Q.empty()){
		int cur_node = Q.top().node;
		int cur_dist = Q.top().dist;
		Q.pop();
		ch[cur_node] = 1;
		if(cur_node == e){
			res = min(res, cur_dist);
		}
		
		for(int i=1; i<=n; i++){
			if(arr[cur_node][i]!=INT_MAX && ch[i]==0){
				Q.push(Edge(i, cur_dist+arr[cur_node][i]));
			}
		}
		
	}
	
	for(int i=1; i<=n; i++){
		ch[i] = 0;
	}
	
	
	return res;

}

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

	cin >> n >> m;
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(i==j) continue;
			arr[i][j] = INT_MAX;
		}
	}
	
	for(int i=1; i<=m; i++){
		int a,b,c;
		cin>> a >> b >> c;
		arr[a][b] = c;
	}

	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			int ans = DIST(i,j);
			if(ans==INT_MAX) cout <<"M ";
			else cout << ans << " ";
		}
		cout <<'\n';
	}
	
}

플로이드워샬 알고리즘이란?

플로이드워샬 알고리즘은 모든 정점에서 모든 정점으로 가는 최단 거리를 구하는 알고리즘이다.

다익스트라 벨만포드 알고리즘과 플로이드워샬 알고리즘의 차이는?

다익스트라, 벨만포드 알고리즘은 한 정점에서 다른 정점으로 가는 최단 거리를 구한다는 점에서

플로이드워샬 알고리즘과 차이가 있다.

점화식

arr[i][j] 는 i노드에서 j노드로 가는 거리를 저장한다.

arr[i][j] = min(arr[i][j], arr[i][k]+arr[k][j]);

i노드에서 j노드로 가는 거리와

i노드에서 k노드를 거쳐 j 노드를 가는 거리를 비교해서 더 짧은 방법을 선택한다.

k에 대하여 존재하는 모든 노드를 한 번씩 다 적용시켜보면

모든 노드에서 모든 노드로 가는 최단 거리 테이블을 만들 수 있다.

다음과 같은 그림이 있을 때

k노드를 선택하기 이전에

arr[i][j] = 20이었다.

i - > j 노드로 가는 것 보다

i -> k -> j 노드로 가는 게 더 짧다.

arr[i][j] = 18로 선택된다.

추가적으로 t 노드가 있을 때

이제 i ->k ->j 보다

i-> k -> t -> j 노드로 가는 게 더 빠르다.

arr[i][j] = 18에서

arr[i][j] = arr[i][t] + arr[t][j] = 17로 갱신된다.

이런식으로 모든 노드에 대해서 갱신해주면

모든 노드에서 모든 노드로 가는 최단 거리를 구할 수 있다.

arr[i][j] = min(arr[i][j], arr[i][k]+arr[k][j]);

k번째 노드를 계속 선택해줘서 경유점으로 둘 때

최솟값을 계속 갱신해준다는 점에서 냅색알고리즘과 유사하다.

노드를 가방에 담을지 안담을지 선택한다고 보면 된다.

for(int k=1; k<=n; k++){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(arr[i][k]==INT_MAX || arr[k][j] == INT_MAX) continue;
            arr[i][j] = min(arr[i][j], arr[i][k]+arr[k][j]);
        }
    }
}

1부터 n까지 모든 노드 k에 대해서

k를 경유점으로 추가하는 것과 이전의 k를 경유점으로 추가하지 않는 것을 비교하면서

최솟값을 계속 저장해준다.

이러면 결과적으로 arr[i][j]에 i부터 j까지 가는 최단 거리가 저장된다.

(애초에 i에서 j로 갈 수 없는 점들은 INT_MAX로 초기화해두고 시작한다)

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

int n, m;

int arr[101][101];


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

	cin >> n >> m;
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(i==j) continue;
			arr[i][j] = INT_MAX;
		}
	}
	
	for(int i=1; i<=m; i++){
		int a,b,c;
		cin>> a >> b >> c;
		arr[a][b] = c;
	}

	for(int k=1; k<=n; k++){
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				if(arr[i][k]==INT_MAX || arr[k][j] == INT_MAX) continue;
				arr[i][j] = min(arr[i][j], arr[i][k]+arr[k][j]);
			}
		}
	}
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if (arr[i][j]==INT_MAX) cout << "M ";
			else cout << arr[i][j] << ' ';
		}
		cout << '\n';
	}
	
}

플로이드 와샬 알고리즘을 이용하면

맨위처럼 우선순위큐 BFS를 사용하지 않아도

간단하게 모든 노드에서 모든 노드로 가는 최단거리를 구할 수 있다.

2차원

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

int n, m;
int dy[101][1020];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for(int i=1; i<=n ;i++){
		int point, time;
		cin >> point >> time;
		
		for(int j = time; j<=m; j++){
			dy[i][j] = max(dy[i-1][j-time] + point, dy[i-1][j]);
		}
	}

	cout << dy[m];
	

}

1차원

for문을 뒤에서부터 돌면 해결된다

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

int n, m;
int dy[1020];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for(int i=1; i<=n ;i++){
		int point, time;
		cin >> point >> time;
		
		for(int j = m; j>=time; j--){
			dy[j] = max(dy[j-time] + point, dy[j]);
		}
	}

	
	cout << dy[m];
	

}