빅오 표기법(Big-O Notation)이란 계수와 낮은 차수의 항을 제외하고 수식을 표기하는 방법입니다.이 표기법은 문제를 해결하는데 걸리는 시간과 입력의 함수관계를 뜻하는 시간 복잡도(Time Complexity)와공간과 입력의 함수관계를 뜻하는 공간 복잡도(Space Complexity)를 표현하는데에 사용하며이를 이용하여 문제에서 주어지는 시간 제한과 메모리 제한에 적절한 코드인지 코드를 작성하기 전 확인할 수 있습니다.많이 사용하는 빅오 표기법의 대소 관계는 아래와 같습니다. O(1) < O(lgN) < O(N) < O(NlgN) < O(N^2) < O(N^3) < O(2^N) < O(N!) 문제에서 주어지는 최대 N에 대하여 시간복잡도에 대입하였을 때1초당 1억으로 계산하여 알고리즘이 대략 몇..
회전하는 캘리퍼스 알고리즘(Rotating Calipers Algorithm)은 캘리퍼스로 무언가를 재는 과정을 알고리즘화 한 것 입니다.캘리퍼스는 작은 물건의 지름, 너비등을 측정할 때 쓰는 도구로 두 개의 평행한 변 사이에 물체를 끼우고 변 사이를 측정합니다.기하 문제에서는 이를 볼록 다각형에 완전히 포함하는 가장 긴 선분의 길이를 구하는 용도로 쓸 수 있습니다.이 때 이 길이를 볼록 다각형의 지름이라고도 합니다.회전하는 캘리퍼스 알고리즘은 실제 캘리퍼스와 비슷하게 다각형을 평행한 두 직선 사이에 끼우고다각형을 따라 두 직선을 한 바퀴 돌리면서 두 직선에 닿는 꼭지점들 간의 거리를 구합니다.이를 좀 더 편하게 구현하기 위하여 가장 왼쪽에 있는 점과 오른쪽에 있는 점에 수직선을 붙이고 시작한 뒤,어느 ..
볼록껍질(Convex Hull)은 컨벡스 헐이라고도 불리며 주어진 점들을 모두 포함하는 최소 크기의 다각형을 말합니다.볼록껍질을 구하기 위하여 그라함 스캔 알고리즘(Graham's Scan Algorithm)을 사용합니다.이 알고리즘은 먼저 y좌표가 가장 작고 y좌표가 같다면 x좌표가 가장 작은 점을 선택한 뒤,그 선택한 점을 제외한 점을 반시계 방향으로 정렬하여 순서대로 점을 보며 스택에 push 합니다.이 때 push하기 전 스택에 점이 2개 이상 들어있을 때 그 두 점을 이은 직선 기준으로 왼쪽에 이 점이 있지 않다면스택에서 조건에 만족할 때까지 pop한 뒤 push를 해주며모든 점을 보았을 때 스택에 남아있는 점이 최소 크기의 다각형을 이루는 점입니다.직선 기준으로 왼쪽에 있는 지는 앞서 계산 기..
다각형 클리핑 알고리즘(Polygon Clipping Algorithm)은 다각형으로 다른 다각형을 잘라내는 알고리즘입니다.많이 사용하는 다각형 클리핑 알고리즘으로는 서덜랜드-호지맨 알고리즘(Sutherland-Hodgman Algorithm)으로볼록 다각형으로 다른 단순 다각형을 잘라내는 알고리즘입니다.볼록 다각형의 여러 반평면의 교집합을 구하는 것이 주원리로앞서 계산 기하에서 배운 CCW를 이용하여 각 점이 평면의 어느 쪽에 속하는 지 확인하며직선의 왼쪽에 있는 점들과 변이 직선을 가로지를 경우 변과 직선의 교차점 또한 포함 시키는 과정을 반복합니다.
계산 기하 알고리즘(Computational Geometry Algorithm)은 각종 기하학적 도형을 다루는 알고리즘입니다.계산 기하의 기본 도구로는 방향과 크기의 의미를 모두 포함하는 벡터(Vector)를 자주 사용합니다.이유는 벡터를 사용하였을 때 더 많은 계산을 빠르고 간편하게 할 수 있으며벡터끼리의 연산인 내적과 외적을 활용하여 더 효율적으로 문제에 접근할 수 있기 때문입니다.내적을 이용하여 두 벡터의 사이각, 두 벡터의 직각 여부, 벡터의 사영을 쉽게 구현할 수 있으며외적을 이용하여 삼각형 또는 사각형의 면적, 두 벡터의 방향을 판별할 수 있습니다.이 때 벡터의 방향을 판별하는 기법을 CCW(Counter-Clockwise) 알고리즘이라 하며두 벡터의 방향이 반시계 방향이면 양수, 시계 방향이..
호프크로프트 카프 알고리즘(Hopcroft-Karp Algorithm)은 더 빠른 시간복잡도의 이분 매칭 알고리즘으로앞서 이분 매칭에서 배운 포드-풀커슨 알고리즘을 변형한 방법의 시간복잡도는정점 개수가 V 간선 개수가 E일 때 O(VE)였으나호프크로프트 카프 알고리즘의 시간복잡도는 O(V^(1/2)E)입니다.이 알고리즘에서 아래와 같은 새로운 용어를 사용합니다. 1. 교차 경로(Alternating Path) : 그래프 위의 경로 중 매칭되어 있지 않은 정점으로부터 시작하여매칭을 이어주고 있지 않은 간선과 이어주고 있는 간선이 교차하는 규칙이 반복되는 경로2. 증가 경로(Augmenting Path) : 양 끝 정점이 매칭되어 있지 않은 교차 경로 증가 경로가 존재하면 이를 뒤집어 반드시 매칭 크기를 1..
디닉 알고리즘(Dinic's Algorithm)은 더 빠른 시간복잡도의 최대 유량 알고리즘으로네트워크 유량의 기본 알고리즘인 포드-풀커슨 알고리즘의 시간복잡도는정점 개수가 V 간선 개수가 E이며 문제의 답이 f일 때 min(O(Ef), O(VE^2))이였으나디닉 알고리즘의 시간복잡도는 O(V^2E)입니다.이 알고리즘에서 아래와 같은 새로운 용어를 사용합니다. 레벨 그래프(Level Graph) : 모든 정점에 대하여 소스로부터 거쳐야하는 최소 간선 수를 값으로 가지는 그래프(이 때 여유 용량이 있는 간선만 사용가능)차단 유량(Blocking Flow) : 레벨 그래프 상에서 인접하면서 자신보다 레벨이 1 큰 정점으로만 흐를 수 있을 때소스에서 싱크로 흐를 수 있는 최대 유량 이후 동작원리는 아래와 같습니..
MCMF(Minimum-Cost Maximum-Flow)는 최소 비용 최대 유량이라고도 불리며네트워크의 각 간선마다 유량을 1 흘려보낼 때 드는 비용이 정해져 있을 때최대 유량을 어떻게 흘려보내야 비용의 합을 최소화 할 수 있는 지를 알아내는 방법입니다.그래프파트에서 다뤘던 간선에 비용이 있는 그래프에서의 최단경로를 매번 찾은 뒤이 경로로 흐를 수 있는 최대 유량을 찾아서 흘려보내면서이전에 찾은 경로의 비용 합 * 유량을 반복하여 계속 더해주며 구합니다.이 때의 최단 경로 알고리즘이 유량 그래프의 특성에 따라 음의 가중치가 있는 그래프에서도 가능하여야 하므로앞서 배운 벨만 포드 알고리즘의 변형인 SPFA(Shortest Path Faster Algorithm)을 사용합니다.SPFA의 시간복잡도는 벨만 포..
이분 매칭(Bipartite Matching)문제는 이분 그래프에서 최대 매칭을 구하는 문제입니다.이 때 이분 그래프(Bipartite Graph)란 정점을 두 그룹으로 나눠서 모든 간선이 서로 다른 그룹의 정점들을 연결 할 수 있도록할 수 있는 그래프로 이 그래프에서 끝 점이 공유하지 않는 간선의 집합을 구하는 문제로도 설명할 수 있습니다.이러한 문제를 네트워크 유량 문제로 접근한다면 소스와 한 그룹의 모든 정점을 잇고 다른 그룹의 모든 정점과 싱크를 이은 뒤서로 다른 그룹을 연결하는 간선을 포함해서 모든 간선을 비용이 1인 간선으로 만들어주고 최대 유량을 구하게 된다면최대 매칭을 알아낼 수 있습니다.이 때 네트워크 유량의 포드-풀커슨 알고리즘을 그대로 사용하여 문제를 풀지 않고 이분 그래프의 특성을 ..
최소 컷(Minimum Cut)은 민 컷이라고도 불리며 네트워크에서 용량이 가장 작은 컷을 말합니다.이 때 컷이란 소스와 싱크가 각각 다른 집합에 속하도록 그래프의 정점을 두 개의 집합으로 나눈 것으로소스가 속한 집합을 S, 싱크가 속한 집합을 T라 할 때S에서 T로 가는 간선들의 용량 합을 컷의 용량, 유량 합을 컷의 유량이라고 합니다.컷은 아래와 같이 2가지의 속성은 만족합니다. 1. 컷의 유량은 소스에서 싱크로 가는 총 유량과 같다.2. 컷의 유량은 용량과 같거나 더 작다. 이 때 최소 컷 최대 유량 정리(Max-Flow Min-Cut Theorem)에 의하여최소 컷은 네트워크 유량 문제에서의 최대 유량과 동일하다는 것을 이용하여 문제를 풀 수 있습니다.네트워크 그래프에서 최소 용량의 간선을 자르고..