최대 유량을 찾는 에드몬드 카프 알고리즘(Edmonds-Karp Algorithm) 배우기

1. 유량 네트워크(flow network) A에서 B까지 8명이 지나갈 수 있고, B에서 C까지 3명이 지나갈 수 있다고 해보자. A에서 C까지 1초가 걸린다고 한다면, A에서 B로 8명을 보낼때, 1초 후에 상황은 어떻게 될까 그러면 B에 5명이 대기하고 있고, C에는 3명이 도착해있다. 즉, A에서 B로 8명씩 보내는건 손해라는 의미 A에서 B로 8명씩 보낼 수 있지만, A에서 C까지 막힘없이 데이터를 전송할려면 1초에 3명씩 보내야한다는 소리이다. 위의 그림은 A에서 B로 최대 8명이 갈 수 있는데, 실제로는 3명이 흐르고 있다는 뜻 때때로 네트워크상 특정 지점에서 다른 지점으로 실제로 데이터가 얼마나 흐르고 있는가를 측정하는 것에 관심이 있다. 송유관에서 두 도시 사이 보낼 수 있는 석유의 양,..

• format_list_bulleted 유량 알고리즘
• · 2023. 10. 6.
• textsms

z function 활용법 2 - prefix이면서 suffix인 문자열을 찾는 방법-

1. border 어떤 문자열의 prefix이면서 동시에 suffix이기도 한 부분문자열을 border라고 부른다. 이 border와 관련된 문제를 해결하는데 z function이 매우 강력하다. z function의 정의에 대해 생각해본다면.. z[i]는 s와 s[i,...,n-1]의 가장 긴 공통 접두사의 길이를 뜻한다 https://deepdata.tistory.com/1000 문자열과 접미사의 가장 긴 공통 접두사의 길이를 찾는 z 알고리즘 배우기 1. z - function 길이 n인 문자열 s에 대하여 z[i]는 s의 i번째 접미사 s[i,i+1,...]과 s와의 최대 공통 접두사의 길이를 말한다 정의에 의하면 z[0]는 s와 s의 최대 공통 접두사의 길이로 s 그 자체의 길이 n deepda..

• format_list_bulleted 문자열 알고리즘
• · 2023. 9. 28.
• textsms

꼭짓점이 둥근 볼록껍질(round convex hull)의 둘레의 길이를 구하는 법

1. 문제 10903번: Wall construction (acmicpc.net) 10903번: Wall construction 첫 번째 줄에는 두 개의 자연수 N, R (1 ≤ R ≤ 100)이 공백으로 구분되어 주어진다. N은 기둥의 개수이며, R은 기둥의 반지름으로 모든 기둥은 같은 반지름을 가진다. 이후 N개의 줄에는 미술관의 www.acmicpc.net 2. 풀이 convex hull의 둘레의 길이를 구해야하는데.. 단순히 둘레의 길이만 구한다면.. convex hull의 모든 꼭짓점을 찾고 꼭짓점끼리 거리를 합하면 그만이지만 이 문제는 꼭짓점이 둥근 형태라는게 문제다. convex hull의 꼭짓점을 찾고 꼭짓점끼리 거리를 구한다음, 파란색으로 동그라미 된 둥근 부분의 길이도 구해야한다 이를 ..

• format_list_bulleted 기하학
• · 2023. 9. 27.
• textsms

두 종류 물건을 특정 개수만큼 사면서 최소 가격에 사는 그리디 알고리즘

1. 문제 30022번: 행사 준비 (acmicpc.net) 30022번: 행사 준비 첫째 줄에 정수 $N(2\le N\le 100,000)$과 정수 $A,B(1\le A,B\leq N;A+B=N)$가 공백으로 구분되어 주어진다. 둘째 줄부터 $N$개의 줄에 정수 $p_i,q_i(1\le p_i,q_i\le 10^9)$가 공백으로 구분되어 주어진다. $p_i,q_i$는 www.acmicpc.net 2. 풀이 첫번째 상점 가격을 오름차순 정렬하고, A개만큼 산 다음, 두번째 상점 가격을 오름차순 정렬해서, 이미 산 아이템일때, 첫번째 상점 가격보다 저렴한지 비교해서 저렴하면 두번째 상점 것으로 사보고.. 아니면 첫번째, 두번째 합쳐서 정렬해서 처음부터 순회할때, A개를 맞추면 나머지는 두번째 상점에서 다 ..

• format_list_bulleted 그리디 알고리즘
• · 2023. 9. 25.
• textsms

분할 정복 중요 테크닉 - 히스토그램에서 가장 큰 직사각형 찾기

1. 문제 1725번: 히스토그램 (acmicpc.net) 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자 www.acmicpc.net 2. 풀이 히스토그램이 주어질때, 찾을 수 있는 직사각형중 넓이가 가장 큰 직사각형을 찾는 문제 위와 같은 경우 다음과 같은 직사각형을 찾을 수 있을 것이다. 히스토그램이 높이 배열 A로 주어질 때, 어떤 구간 [i,j]까지 잡았을 경우, 만들 수 있는 직사각형은 높이가 가장 낮은 min(A)에 구간의 길이 j-i+1을 곱한 값이다. 따라서 가능한 모든 경우에 대해 min..

• format_list_bulleted 분할 정복
• · 2023. 9. 22.
• textsms

reduced row echelon form을 구하는 Gauss-Jordan elimination 구현하기

1. reduced row echelon form 한번 쯤 다시 읽어보자 elementary row operation과 reduced row echelon form을 설명하고 있다. elementary row operation은 1) 주어진 행렬의 i번째 행과 j번째 행을 뒤바꾸는 것 2) i번째 행에 0이 아닌 scalar를 곱하는 것 3) i번째 행에 scalar를 곱하고 j번째 행에 더해주는 것 이러한 연산을 하더라도 주어진 행렬의 rank는 변하지 않는다. https://deepdata.tistory.com/34 선형대수학 기본 용어 -상급자편 3- 1. gaussian elimination 1) 주어진 행렬의 $i$번째 행과 $j$번째 행을 뒤바꾼다. 2) 주어진 행렬의 $i$번째 행에 0이 아..

• format_list_bulleted 선형대수학 알고리즘
• · 2023. 9. 21.
• textsms