지난 글에 이어서 더 빠른 최대 유량 알고리즘인 디닉 알고리즘.에드몬즈-카프는 bfs를 활용하며 O(VE2) 안에 문제를 해결할 수 있다. 간선에 대한 지수시간이기 때문에 정점의 수와 무관하게 간선이 여러 개라면 bfs에서 너무 많은 시간을 소모하게 된다. 하지만 디닉은 정점에 대한 지수시간 O(V2E) 안에 문제를 해결한다.디닉 알고리즘의 순서는 이렇다.유량 그래프 = G, source = s, sink = t1. G의 레벨그래프 L을 만든다.  a. s로부터 t까지의 bfs로 깊이는 각 정점의 레벨이 된다.  b. t의 레벨이 정의되지 않으면 모든 작업을 멈춘다.2. L에서 다음 작업을 반복한다.  a. dfs로 s→t의 증가경로를 찾는다.  b. 증가경로의 최소 컷을 찾아 경로에 유량을 생성한다.3..

1. 최대 유량 문제정점 간에 흐를 수 있는 양이 있을 때 그 최대치를 간선으로 표현하면 하나의 방향 그래프가 나온다. 두 정점 사이에 흐를 수 있는 최대 양을 용량(capacity), 두 정점 사이에 흐르고 있는 양을 유량(flow), 현재 남아있는 용량을 잔여용량(residual)이라고 한다. 예를 들어 파주에서 안양에 이르는 수도권 서부의 도로 교통용량을 대충 다음과 같이 표현할 수 있다.(실제로 이런 상황에다가 써먹지는 않는 듯 하다.)그렇다면 이 그래프 외의 다른 연결을 전부 무시하고 모든 도로가 전부 비어있다고 가정했을 때 파주에서 안양까지 이어지는 도로 교통용량의 최대치는 얼마일까?자유로에서 서부간선도로를 타면 파주-일산-고양-서울-안양으로 이어진다. 이 경로에 따르면 일산~고양 구간이 용량..

1. 다익스트라 알고리즘(Dijksrta)시작 정점으로부터 간선으로 연결된 정점들을 순차적으로 방문한다. 간선의 가중치를 포함해 방문한 정점의 거리가 갱신된다면 방문한 정점에서 이 과정을 다시 반복한다. 원리만 따지면 너비우선탐색과 크게 다르지 않다. 모든 간선의 가중치가 1인 그래프가 주어진다면 너비우선탐색을 실시하는 것이 다익스트라와 같은 효과가 있다.이런 무향 그래프가 있다고 할 때 1에서부터 6까지의 최단거리를 구해보자. 먼저 모든 정점의 거리를 충분히 큰 값인 inf로 설정한다. 실제로 무한일 필요는 없고 탐색하고자 하는 모든 상황에 대해 예상되는 최대 탐색 거리보다 크기만 하면 된다. 최대 정점의 수가 V개이고 간선의 최대 가중치가 W라면 inf는 V*W보다 큰 값이면 된다. 탐색의 출발 정점..

선분은 직선 상의 두 점과 그 두 점 사이의 점들로 구성되는 유한인 직선의 부분이다. 간단히 두 점을 잇는 최단거리다. 샤프심 두 개를 책상에 쏟았다. 샤프심을 선분이라고 봤을 때 이 두 가닥의 샤프심의 위치관계를 몇 가지로 나누어 설명할 수 있을까. 우선 두 샤프심이 서로 닿은 경우와 닿지 않은 경우가 있을 것이다. 그리고 닿은 경우에는 겹친 경우도 있을 것이다. 닿지 않은 경우도 나란히 놓여서 샤프심의 길이가 무한히 늘어나도 닿지 않는 특수한 경우와 그렇지 않은 경우로 나눌 수 있다. 1. 벡터의 외적 벡터는 고등수학에 따르면 크기와 방향을 가진 물리량을 의미한다. 쉽게 생각하면 화살표로 볼 수 있다. 길이도 있고 방향도 있다. 선분끼리는 더하거나 뺀다는 연산을 길이만 두고 할 수 있으나 벡터는 방향..

분리 집합은 두 집합의 관계르 나타내는 것으로 두 집합 A와 B의 교집합이 공집합일 때 A와 B는 분리 집합이라고 한다. 집합의 요소를 놓고 요소들이 포함된 집합이 같은 집합인지 분리 집합인지 확인하고, 두 분리 집합을 하나로 병합하는 알고리즘을 유니온 파인드라고 한다. 1. 분리 집합(Disjoint set) 두 집합 A = {1, 2, 3, 4, 5}와 B = {5, 6, 7, 8, 9}는 '5'를 공통 원소로 갖는다. 이 경우 A, B는 분리 집합이 아니다. 집합 C = {10, 11, 12, 13, 14}가 있을 때, A∪B와 C는 공통 원소가 없는 분리 집합이다. A와 C도 분리 집합이고 B와 C도 분리 집합이다. 여러 정점을 놓고 간선으로 연결한 상태가 주어졌을 때, 정점과 간선을 거쳐 연결된..

최장 증가 부분 수열 - 나무위키 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. namu.wiki 1. 최장 증가 부분 수열(LIS) LIS 문제를 처음 봤을 때 만능 문제해결 툴 브루트포스를 떠올렸는데 당연히 죽음뿐. LIS 문제의 정해는 보통 두 가지다. O(N2)으로 해결할 수 있는 다이나믹 프로그래밍, O(NlogN)으로 해결할 수 있는 이진 탐색이다. 여기서 또 이진 탐색 해법이 있다는 걸 처음 알았을 때는 "대체 이게 뭔소리냐" 싶었는데 잘 살펴보고 직접 구현해보면 그렇게 어려운 개념은 아니다. 하지만 이 문제를 이미 몇 년 전에 처음 접해서 풀었던 ..

1. 투 포인터(Two pointer)와 슬라이딩 윈도우 리스트에서 데이터에 접근할 때 한 방향으로 탐색하는 선형탐색은 매우 간단하지만 리스트의 크기가 커지게 되면 효율적이지 않다는 문제가 있다. 이를 극복할 수 있는 이진 탐색, 매개변수 탐색 등 다양한 탐색 알고리즘이 있다. 그 중, 두 개의 포인터를 이용해 범위를 좁히거나 이동시키며 탐색하는 방법을 투 포인터라고 한다. 슬라이딩 윈도우는 투 포인터 문제의 특수한 경우로, 두 포인터의 간격이 일정하게 유지되며 이동하는 문제 해결 방법이다. 두 포인터가 움직이는 것이 마치 창틀에 고정된 창문이 움직이는 것과 같아 슬라이딩 윈도우라는 이름이 붙었다. 2. 구현 슬라이딩 윈도우는 간단하게 구현할 수 있다. 두 개의 포인터를 지정하고 한 구간의 탐색을 끝내면..

얼마전 볼록껍질 문제를 해결하고 기하 문제에 관심이 생겨 백준 1077번 넓이 문제에 도전해봤다. 새로 배워야 할 개념이 많았는데 넓이를 구하는 기초적인 아이디어를 잘 구현해낸 것 같아 정리해보고자 한다. 1. 볼록다각형의 정의 이 문제를 연구하다가 새로 알게된 사실이다. 볼록다각형은 이웃하지 않는 두 점을 이은 선분이 도형 내부에 존재하는 단순다각형을 말한다. 단순다각형은 다각형을 이루는 변들이 서로 교차하지 않는 다각형을 말한다. 볼록 집합이라는 것도 있는데, 집합 내에서 어떤 두 점을 선택해도 선분이 집합 내부에 그려지게 되는 집합을 말한다. 볼록다각형은 볼록 집합을 이루는 단순다각형이기도 하다. 엄밀한 볼록다각형은 모든 내각의 크기가 180도 미만이어야 한다. 어떤 문제들은 이 조건을 명시하지만 ..