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

네트워크 유량 문제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]) ..

https://www.acmicpc.net/problem/1516 알고리즘다이나믹 프로그래밍 / 그래프 이론 / 위상 정렬 / 방향 비순환 그래프 설명예 ~ 전에 풀려다가 못 풀었었는데, 오랫만에 보니까 금방 풀었다.문제 내용부터 '나 위상 정렬' 이라고 말하고 있기 때문에, 그냥 위상 정렬 후 소요 시간만 잘 계산하여 주면 된다. [각 작업에 대한 최소 소요 시간] = [입력 간선으로 들어오는 노드들 중, 가장 늦게 끝나는(최대 소요 시간)] + [해당 노드의 작업 시간]위상 정렬  코드#include #include #include #include using namespace std;int N;int cost[501];int result[501]; //각 건물을 짓는데 필요한 시간int in[5..

https://www.acmicpc.net/problem/30689 알고리즘그래프 이론 / 그래프 탐색 / 깊이 우선 탐색 / 함수형 그래프설명이전에 풀었던 텀 프로젝트 문제와 비슷한 느낌이 난다.재귀를 통하여 구현해당 유형은 익숙하지가 않아 구현 실수가 많은 것 같다.이번 차례에 방문한 칸과 이전에 방문했던 칸을 체크하는 두 개의 vistied 배열을 사용하여 미로 내의 사이클을 찾는 문제만약 사이클을 발견하게 되면, 사이클을 이루는 칸 중 가장 비용이 작은 칸을 정답에 더해준다.코드#include #include #include #include #include #include #include #include #include using namespace std;int N, M;string arr[200..

문제 - 아리스, 청소합니다 Easy 버전 https://www.acmicpc.net/problem/31404 31404번: 아리스, 청소합니다! (Easy) 첫 번째 줄에 방의 크기를 나타내는 $H, W$가 주어집니다. $(1 \le H, W \le 64)$ 두 번째 줄에 아리스의 처음 위치를 나타내는 $R, C, D$가 주어집니다. 아리스의 좌표는 $(R,C)$이고, 위쪽을 기준으로 시계 www.acmicpc.net - 아리스, 청소합니다 Hard 버전 (크기 빼고, Easy와 완전 동일) https://www.acmicpc.net/problem/31399 31399번: 아리스, 청소합니다! (Hard) 첫 번째 줄에 방의 크기를 나타내는 $H, W$가 주어집니다. $(1 \le H, W \le 1\..