컴공생 일상 블로그 컴공생 일상 블로그

문제1738번 골목길: https://www.acmicpc.net/problem/1738 오랫만에 고통 좀 받은 문제, 얼른 풀고 SCC공부하려 했는데 시간 다 뺏김 ㅜㅜ 양 또는 음의 가중치를 가지는 그래프에서 사이클을 판별하고 경로 추적을 하는 문제 (그래프, 벨만-포드)벨만 포드는 몰라서, SPFA로 품   풀이1. 역방향 그래프를 생성해서 BFS를 돌려 해당 정점에서 N정점에 도달 가능한지 여부를 판단만약 해당 정점이 N정점에 도달하지 않는 정점이라면 1에서 N정점간의 비용을 구할 때 고려하지 않아도 된다. (사이클이 존재하지만 정답을 출력하는 경우!)2. SPFA 돌리기, SPFA 경로추적은 몰라서 그냥 다익스트라처럼 비슷하게 추적함if(check[nxt.n] == 0) continue; 와 같..

문제https://www.acmicpc.net/problem/11406 풀이Network flow 문제, Network flow는 각 제한들을 어떻게 capacity로 줄 것인지 생각하면서 풀어야 하는듯그냥 많이 풀어보면서 다양한 유형을 접해봐야할듯...그래도 이 문제는 금방 풀었다. 각각의 입력(사려하고 하는 책의 개수, 사람이 서점에서 구매할 수 있는 책의 개수, 서점이  가진 책의 개수)을 다음과 같이 간선에 매핑하고, capacity를 준 뒤 풀면 된다. 코드#include #include #include #include #include #include #include #include using namespace std;int N, M;int capacity[401][401];int flow[40..

SPFA, Shortest Path Faster AlgorithmSPFA는 최단 경로 알고리즘으로, MCMF(Mininum Cost Maximun Flow)를 구현할 때 사용된다.BFS와 벨만포드 알고리즘을 섞은 것과 비슷하다. 모든 간선의 가중치가 같은 그래프에서 SPFA를 수행하면 BFS와 똑같이 동작한다. 최단 경로 알고리즘다익스트라: O(ElogV)로 동작하지만, 음수 간선은 처리 불가플로이드-와셜: 음수 간선은 처리 가능하지만, 모든 정점들간의 거리를 구하는데 사용되고 O(V^3)으로 동작벨만-포드: 음수 간선 처리 가능, O(VE) 음수간선이 포함된 사이클이 존재한다면, 비용은 점점 작아져 -INF가 된다.해당 정점이 N번 이상 방문되었는지를 체크하여, 음수사이클의 존재 여부를 확인할 수 있다..

네트워크 유량 문제Network flow네트워크 유량문제는 최대 유량(Maximum flow)라고도 한다.방향이 있는 그래프에서 각 간선에 흐를 수 있는 용량이 정해져 있을 때, 출발점에서 도착점까지 보낼 수 있는 최대 유량을 계산하는 문제 용어= Source(시작점)에서 Sink(도착점)으로 동시에 보낼 수 있는 최대 양을 구하는 알고리즘Source: 시작점Sink: 도착점Capacity: 용량(각 간선에 흐를 수 있는 최대 용량)Augmented Path: 증가 경로(최소 1 이상의 유량이 흐를 수 있는 시작점에서 도착점까지의 경로)Flow: 유량, 해당 간선에 실제로 흐르는 용량 네트워크 유량 문제의 특징1. 용량의 제한, 각 간선에 흐르는 유량을 그 간선의 용량을 넘을 수 없음2. 유량의 보존, ..

가장 긴 증가하는 부분 수열 5: https://www.acmicpc.net/problem/14003 알고리즘: LIS - O(nlogn) + LIS - 경로 추적  코드#include #include #include #include using namespace std;int N;int arr[1000011];int dp[1000011];vector path;int main(){ cin >> N; for (int i = 0; i > arr[i]; } dp[0] = -1111111111;// int level = 0; for (int i = 0; i ans; for (int i = N - 1; i >= 0; --i) { if (level

문제전구: https://www.acmicpc.net/problem/2550 가장 긴 증가하는 부분 수열 5: https://www.crocus.co.kr/681전기줄2: https://www.acmicpc.net/problem/2568  전구 문제 자체는 N LIS 경로추적을 처음 풀어봐서 고생했다.vector path로 LIS 추가 시 마다, 같이 기록하면서 LIS의 길이를 구하고, 역추적 해주면 된다.  코드#include #include #include using namespace std;int N;int a[10011];int b[10011];int bb[10011];int ab[10011];vector dp;vector path;vector ret;int main(){ cin >> N; ..

볼록 껍질, Convex Hull?2차원 평면 위에 N개의 점들이 있을 때, N개의 점을 모두 에워싸는 가장 작은 볼록 다각형으로 그림과 같다.일반적으로 Convex Hull을 구하기 위해, 모든 점들을 서로 비교해가면서 모든 경우를 구해 볼 수 있다.하지만 이 경우 점의 개수가 10,000 개만 넘어가도 엄청난 시간이 소요된다. 그레이엄 스캔, Graham Scan 볼록 껍질을 구하는 알고리즘으로, O(nlogn)의 시간에 Convex Hull을 구할 수 있다.* 선행 알고리즘 : CCW, Counter Clockwise3개의 점의 위치 관계를 알아내는 기하 알고리즘, 세 점이 일직선 상에 있으면 0, 반시계 방향이면 양수, 시계 방향이면 음수를 반환한다. 그레이엄 스캔 알고리즘 과정1. 주어진 점들을..

LCS, Longest Common Subsequence : 가장 긴 공통된 부분 수열두 수열에서 각각의 부분 수열 중, 서로 같은 부분 수열 중에서 가장 긴 부분 수열을 의미한다.DP의 Well-known 유형 중 하나이다.   점화식수열(문자열) S1, S2이 있다고 하자S1의 길이는 N이고, S2의 길이가 M이고, i, j가 각각 S1, S2의 인덱스 일 때int dp[N][M];dp[i][j]는 S1을 i까지 S2를 j까지 봤을 때, 가장 긴 공통 부분 문자열의 길이  그냥 아래 표로 한 번 그려보는 것이 이해가 편하다.즉 S1[i]와 S2[j]가 같다면, dp[i][j] = dp[i-1][j-1] + 1 이고, 값이 다르다면 dp[i][j] = max(dp[i][j-1], dp[i-1][j]) ..