Hani_Levenshtein

N개의 정수나 실수로 이루어진 한 집합에서 특정 수를 찾는 것은 이진 탐색 트리에서 O(logN)의 시간이 소요됩니다. 하지만 집합이 문자열로 이루어져 있다면, M의 길이를 갖는 문자열을 탐색할 땐 O(M*logN)이 걸릴 것입니다. 트라이(Trie) 자료구조에서는 문자열 집합에서 특정 문자열이 존재하는지 O(M)만에 알 수 있습니다. 트라이 문자열 TABLE, TABLET, TAIWAN, TREE, TRIE, PHONE이 들어있는 문자열 집합을 생각해 봅시다. 문자열 집합에 속한 문자열들은 모두 대문자 알파벳으로 구성되어 있다고 가정하겠습니다. 일반적인 이진 탐색 트리라면 사전 상에서 앞에 있는 문자열이 왼쪽, 뒤에 있는 문자열이 오른쪽이 배치될 것입니다. 트라이는 집합에 포함된 문자열의 접두사들에 대..

Convex Hull 알고리즘은 말 그대로 볼록한 껍질을 만드는 알고리즘입니다. 이번 포스팅에서는 2차원에 대해서만 다룰 것이기 때문에 볼록 다각형만을 다룰 것입니다. 컨벡스 헐 알고리즘을 통해 볼록 다각형을 구성하는 꼭짓점을 얻을 수 있습니다. 먼저 점들의 좌표를 입력받아 배열에 담습니다. 점들 중에서 y좌표가 가장 작은 것을 배열의 맨 앞으로 가져와 기준점 (1번)으로 둡니다. 그중에서 y좌표가 동일한 것이 있다면 x좌표가 가장 작은 것을 기준점으로 삼습니다. 그 후, 기준점과 +x축으로부터 반시계 방향으로 각도가 작은 것부터 큰 순서대로 정렬합니다.(2번 ~ 10번) 그중에서 각도가 동일한 것이 있다면 기준점과 거리가 가까운 것이 앞으로 오도록 정렬합니다. (문제에 따라서 기준 좌표와 정렬 방향을 ..

이번 포스팅의 주제인 이분 매칭 문제는 네트워크 플로우 연장선에 있는 문제입니다. 2020/09/09 - [알고리즘] - 포드 풀커슨 알고리즘 우선, 이분 매칭을 공부하기 위해선 이분 그래프라는 것을 알 필요가 있습니다. 이분 그래프란 두 집합으로 나뉜 그래프의 정점들의 간선이 상대 집합에 속한 정점으로 연결된 그래프입니다. 성별이나, 주종관계, 사람과 작업 등의 관계가 주어진다면 이를 이분 그래프로 표현할 수 있습니다. 여기서 이분 그래프의 각 요소들을 문제의 조건에 맞춰 대응시키는 것이 이분 매칭 문제입니다. 이런 이분 매칭 문제는 앞서 소개한 네트워크 플로우를 이용하면 쉽게 풀 수 있습니다. 이분 그래프의 각 간선을, 연결되지 않은 것(0) 과 연결된 것(1) 인 용량이 1인 간선으로 고려할 수 있..

최단 경로 문제에서는 정점 간 간선의 가중치의 합이 최소가 되는 경로의 길이를 찾으려 했습니다. 네트워크 플로우는 시작점에서 도착점까지 유량을 최대로 흘려보내는 것이 목적입니다. 어떻게 보면 가중치의 합을 최대로 만드는 것인데 여기서 용량이라는 개념이 추가됩니다. 네트워크 유량은 항상 3가지 규칙을 만족해야 합니다. 1. 용량 제한 속성 flow(u,v)

다익스트라와 벨만-포드 알고리즘은 시작점이 정해져 있어서 모든 쌍에 대한 최단 경로를 알아낼 수 없었습니다. 물론, 단일 시작점 알고리즘을 여러 번 돌린다면 모든 쌍에 대한 최단 경로를 찾아낼 수 있지만, 시간 복잡도와 알고리즘 구현 측면에서 한번만 실행해도 되는 플로이드-와샬 알고리즘이 더 적합한 선택일 것입니다. 2020/08/31 - [알고리즘] - 다익스트라 알고리즘 2020/09/07 - [알고리즘] - 벨만포드 알고리즘 2020/09/07 - [알고리즘] - SPFA (Shortest Path Faster Algorithm) 플로이드-와샬 알고리즘은 벨만-포드 알고리즘과 동일하게 음수 가중치가 있어도 사용 가능합니다. 플로이드-와샬 알고리즘의 동작 과정을 알아봅시다. 먼저, 모든 쌍의 최단 경..

SPFA(Shortest Path Faster Algorithm) 라는 알고리즘은 벨만-포드 알고리즘과 유사하게 음수 가중치가 있을 때 사용가능한 단일 시작점 알고리즘입니다. 2020/09/07 - [알고리즘] - 벨만포드 알고리즘 벨만-포드 알고리즘은 총 E 개의 간선을 V 번 방문을 해서 O(VE) 의 시간 복잡도를 갖습니다. 하지만 SPFA 는 경로의 길이가 갱신된 정점에 인접한 간선에 대해서만 다음 방문에서 체크를 하기 때문에 같은 간선을 V 번 방문할 필요가 없어서 평균 시간 복잡도가 O(E) 입니다. 단, 경로의 길이가 갱신되지 않았다면 방문을 계속 해야하기 때문에 최악의 경우엔 O(VE) 의 시간 복잡도를 갖습니다. SPFA 의 동작 원리는 벨만-포드 알고리즘의 동작 원리와 비슷하므로 차이점..