목록Algorithm/Algorithm Concept (10)
S E P H ' S
다익스트라 알고리즘(Dijkstra) 그래프에서 여러 개의 노드가 있을 때, 한 노드에서 각 모든 노드 까지의 최단거리를 구하는 알고리즘이다. 다만 '음의 간선' 즉, 가중치가 0보다 작은 값이 아닌 경우에 정상 작동한다. 동작과정을 살펴보면 그리디 알고리즘(매번 비용이 가장 적은 노드를 선택하기 때문)과 다이나믹 프로그래밍(DP) 기법을 함께 사용한다. 이 두 단계를 반복하면서 임의의 노드에서 각 노드까지의 최단 거리를 구하게 된다. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다. (그리디 알고리즘) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다. (다이나믹 프로그래밍) 작동 방식에 대해서 그림으로 알아보자. 그림 1은 주어진 그래프 상태이다. 출발점은 A, 도착점은 E라고 할 때..
시간 복잡도 주어진 문제를 해결하기 위한 연산 횟수. 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측함. 시간 복잡도 유형 1. 빅-오메가 (Ω(n)) : 최선일 때(best case)의 연산 횟수를 나타낸 표기법 2. 빅-세타 (Θ(n)) : 보통일 때(average case)의 연산 횟수를 나타낸 표기법 3. 빅-오 (O(n)) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법
BOJ 2750, 2751 수 정렬 문제를 풀면서 여러 정렬 알고리즘에 대해 알아둘 필요를 느끼게 되었습니다. 이번 포스트에서는 2751에서 사용된 정렬 알고리즘에 대해 학습하고 여러 정렬 알고리즘에 대해서는 이어질 다음 포스트에서 자세히 다루겠습니다. 문제 원인 파악 2750 문제와 달리 2751은 Java의 Arrays.sort() 를 사용하면 시간초과가 날 수 있습니다. Arrays.sort()의 경우 dual-pivot Quicksort 알고리즘을 사용한다고 합니다. 이 알고리즘은 평균 시간복잡도가 \(O(nlogn)\)으로 매우 빠른 알고리즘이지만 최악의 경우는 \(O(n^2)\)이기 때문에 주의해야 합니다. 그렇기 때문에 최악의 경우에도 \(O(nlogn)\) 혹은 \(O(n)\) 에 가까운 ..
정의 정렬되어 있는 리스트에서 어떠한 데이터를 찾을 때, 순차 탐색과 같이 모든 값을 대조하여 찾는 것이 아니라 탐색 범위를 절반씩 줄여가면서 찾는 방법입니다. 작동원리 예를 들어서 1,2,3,4,5,6 가 들어있는 배열에서 찾으려고 하는 값이 6이라고 한다면 배열의 중간 값(= mid)인 3과 6을 비교합니다. 6은 3보다 크기 때문에 3보다 작은 값들과는 비교할 필요가 없으므로 3보다 큰 값들인 4,5,6 중에서 대조를 합니다. 다시 이 중의 중간 값인 5와 6을 비교하고 6은 5보다 크므로 5보다 작은 값들과는 비교할 필요가 없습니다. 이제 5보다 큰 값과 비교하면 되는데 5보다 큰 값은 이제 6밖에 없으므로 결과를 찾은 것입니다.