Cony's Storage

최단 경로 주요 알고리즘 1. 다익스트라 알고리즘http://elfcony.tistory.com/21?category=759549 2. 벨만-포드 알고리즘http://elfcony.tistory.com/22?category=759549 3. 플로이드-워셜 알고리즘http://elfcony.tistory.com/23?category=759549

1837번 암호제작 : https://www.acmicpc.net/problem/1837 char P[n]; int main(){...scanf("%s", P);...} - input으로 long long 범위를 넘는 값을 받는다면, string을 사용!- 예제로 input 값을 '123'을 받으면,P[0] = '1', P[0] - '0' = 1P[1] = '2', P[1] - '0' = 2P[2] = '3', P[2] - '0' = 3=> " - '0'" : Character to Integer!

1256 사전 : https://www.acmicpc.net/problem/1256 - dp[i][j] = 이항계수(i,j) - ex) aazz 오름차순 줄세우기 for (int i = 0; i < len; i++) { // i번째에 'a'가 들어가는 경우의 수 = dp[len-i-1][m] // 를 기준으로 i번째에 'a' 또는 'z'가 위치하는지 판단한다. if (dp[len - i - 1][m] < k) { printf("z"); k -= dp[len - i - 1][m]; m--; } else { printf("a"); //n--; } }

11051번 이항 계수 2 : https://www.acmicpc.net/problem/11051 파스칼의 삼각형- 이항계수 dp(i, j)에 대해, dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; +이항계수값(dp[i][j])이 너무 클 경우, ex) long long을 넘는 순간이 있을 경우...#define MAX 1152921504606846976 (=2^60) if(dp[i][j] > MAX + 1) {dp[i][j] = MAX + 1;}

1644 소수의 연속 합 : https://www.acmicpc.net/problem/1644 투 포인터- 1644번은 맨 앞부터 순차적으로 풀면 시간 초과가 걸리는 문제 (O(N!))- left, right 사용하자! // *****Left, Right 사용으로 시간초과를 막자!// 연속된 소수의 합 구하기while (l

2960 에라토스테네스의 체 : https://www.acmicpc.net/problem/29606588 골드바흐의 추측 : https://www.acmicpc.net/problem/6588 에라토스테네스의 체- p[] : 소수가 저장됨- c[] : 소수일 경우 false. 아닐 경우 true. vector p; vector c(MAX + 1); for (int i = 2; i

1735 분수 합 : https://www.acmicpc.net/problem/1735 유클리드 호제법- 2개의 자연수의 최대공약수를 구하는 알고리즘 int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a%b); }

11404 플로이드 : https://www.acmicpc.net/problem/11404 플로이드-워셜 알고리즘1) D[i][j] : 정점 i에서 j까지의 최단 거리를 저장하는 배열i==j 이면 D[i][j] = 0i!=j 이면 무한대(INF) 2) D[i][j]에 간선정보를 저장// 경유지 K에 대해서for (int k = 1; k

11657 타임머신 : https://www.acmicpc.net/problem/11657 벨만-포드 알고리즘- 다익스트라와 달리, 음의 가중치를 가지는 간선도 가능!- 음의 사이클의 존재 여부를 확인할 수 있음. 1) 정점 N-1번 수행//1번 정점에서 시작d[1] = 0;for (int i = 1; i < n; i++) { //정점 n-1번 수행 for (int j = 1; j d[path[j][0]] + path[j][2]) { d[path[j][1]] = d[path[j][0]] + path[j][2]; } }} 2) 정점을 한번 더 돌아 최단거리가 갱신된다면, 음의 사이클이 존재하는 것// 만약, 시작점에서 도달 가능한 타임머신으로 되어있는 사이클이 존재해// 1번 도시에서 나머지 도시로 가는 ..

1753 최단경로 : https://www.acmicpc.net/problem/1753 다익스트라 알고리즘- dist[k] : 출발점에서부터 k 정점까지의 최단거리를 저장하는 배열- 우선순위 큐에서 맨 위에 있는 정점을 꺼내며, 비어있을 경우 알고리즘 종료- if(dist[next.node] > dist[node] + next.cost)dist[next.node] = dist[node] + next.cost;pq.push(info(next.node, dist[next.node]); - 참고1)struct info { int node; int cost; info(int n, int c) { node = n; cost = c; } // C++에서 우선순위큐는 디폴트로 max_heap이라 min_heap 쓰려..