hellogaon

계산 기하 알고리즘(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 큰 정점으로만 흐를 수 있을 때소스에서 싱크로 흐를 수 있는 최대 유량 이후 동작원리는 아래와 같습니..