Developer/Algorithm

벨만포드(Bellman-Ford) - 그래프 상에 존재하는 두 노드간의 최단거리를 구할 때 사용하는 알고리즘 - Dijkstra 알고리즘과의 차이점은 음의 가중치를 포함할 때 사용가능하다는 점! - 간선(Edge)의 개수와 노드(Vertex)의 개수에 따라 유동적으로 알고리즘을 사용해야 된다! 전제조건 1. 최단 경로는 사이클을 포함하지 않는다. 따라서 |V| - 1 개의 간선만 사용할 수 있다! 2. 최단 경로가 업데이트 되는 노드가 없어질 때까지 반복해서 구한다! 3. 만약 무한히 업데이트 한다면 이는 조건에 맞지 않으므로 불가능으로 탈출한다! * 고찰 - 매 라운드마다 모든 Edge를 검사하고, |V| - 1의 라운드 동안 전체 Edge |E|개를 검사하므로 - 시간복잡도는 O(|V||E|), |E..

위상정렬이란? - DAG(Direct Acyclic Graph) 그래프에서 Node간의 정렬을 이루기 위해 사용하는 알고리즘 * DAG ? 방향성이 있고 사이클이 없는 그래프 - 그래프에 대한 모든 Node를 진입 차수가 짧은 순서대로 노드를 정리하는 방법이다. - 진입차수가 0인 Node부터 순차적으로 검색하여, 최종적으로 제일 높은 진입차수가까지 정렬하는 방식 위상정렬 순서 1. 인접 리스트 방식으로 그래프를 만들고, 노드별로 진입차수를 기록한다. 2. 큐를 2개 만든다. ( 로직이 진행되는 큐, 결과가 저장되는 큐 ) 3. 진입 차수가 0인 Node들에 대하여 '탐색 큐'에 저장한다. 4. '탐색 큐'에서 Node를 하나씩 poll()을 한 뒤, 해당 Node를 '결과 큐'에 삽입한다. 5. '탐색..

Insertion Sort? - 가장 기본적인 정렬방법 중(Bubble Sort, Selection Sort)와 같이 시간복잡도 O(N^2)를 가진다. - 안정적인 정렬 방법이다. - 최선의 경우 O(N), 최악의 경우 O(N^2)이다. - N의 크기가 작을수록 O(N^2)의 정렬 방법이 효율이 좋다 * Why ? - Quick, Merge의 경우 Function Call 에 들어가는 비용이 더 커지므로! 시간복잡도에 대한 고찰 - 최선의 경우 : 주어진 key값에 대하여 한번만 비교하고 끝날 때!!!! ( 땡기는 작업 X ) - 최악의 경우 : 주어진 key값에 대하여 모든 원소를 비교해야 할 때!! 정렬 순서 1. 0번째 index는 제외하고, 1번째부터 index를 시작한다! 2. 해당 범위내에 마..

QuickSort? - 말 그대로 빠른 정렬이다. - 퀵 소트는 평균적인 시간복잡도는 O(NlogN), 최악의 경우 O(N^2) 이다. - 따로 메모리를 저장하여 정렬하지 않아서 공간복잡도는 O(1)이다! - 이러한 불규칙적 성질 때문에 불안정 정렬이라 한다. - 일단 이론이 굉장히 어려우므로 바로 설명을 가보도록 하자 과정 1. 리스트 안에 있는 한 요소(pivot)를 고르자! 2. pivot을 기준으로 큰 값은 오른쪽, 작은 값은 왼쪽으로 정렬하자~! 3. pivot의 왼쪽 부분과 오른쪽 부분을 다시 재귀로 정렬하자! 4. 단 리스트의 크기가 0, 혹은 pivot 자신만 있을 때 (1) 이면 하지 않는다! Quick 정렬에 대한 고찰 - 파티션을 나누는 과정이 MergeSort와 동일하게 2분할이다...

MergeSort? - 대표적인 분할정복 정렬 알고리즘 중의 하나 cf> 분할정복(Divide And Conquer) ? : 문제를 작은 2개의 문제로 분리하여, 해결하고 결과를 합치는 전략이다. - 메모리를 잡아먹는 특징 때문에, 안정성이 많이 보장되는 정렬 알고리즘이다. - 시간복잡도는 O(NlogN), 공간복잡도는 O(N) 이다. ++ 배열을 1개로 될 때까지 각각을 n/2로 줄이니 당연히 logN 이다. ++ 합칠 때는 총 N번의 비교연산이 들어가므로 N*logN 이 되는 시간복잡도이다! - 보통 정렬의 공간복잡도는 O(1)인데, 병합정렬의 경우 복사할 배열이 새로 필요하다! 언제 써야될까? 1. 많은 데이터를 정렬할 때, 여분의 메모리가 충분할 때! 2. 반대로, 많은 데이터를 정렬하고 싶은데 ..