반응형 전체 글95 일반 다익스트라 vs. 힙을 활용한 다익스트라: 차이점과 성능 비교 다익스트라 알고리즘(Dijkstra's Algorithm)은 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 대표적인 알고리즘입니다. 이 알고리즘을 구현하는 방법에는 일반적인 방식(배열 기반) 과 힙(Heap)을 활용한 방식 두 가지가 있으며, 성능 차이가 매우 큽니다. 본 글에서는 두 방식의 차이점을 깊이 있게 분석하고, 성능 비교를 통해 어떤 상황에서 어떤 방법이 더 적합한지 알아보겠습니다. 1. 일반 다익스트라 알고리즘 (배열 기반)개념일반적인 다익스트라 알고리즘은 배열(Array) 또는 선형 탐색(Linear Search) 을 이용하여 최단 거리를 찾습니다.2025.02.07 - [알고리즘] - 다익스트라 알고리즘(Dijkstra's Algorithm) 총 정리 - 개념, 원리, .. 2025. 2. 22. 힙을 활용한 다익스트라 알고리즘 (Dijkstra's Algorithm) - 개념, 원리, 동작예시, 시간복잡도, C언어, Java, Python 예제코드 다익스트라 알고리즘은 최단 경로를 찾는 강력한 알고리즘이지만, 기본적인 구현 방식은 시간 복잡도가 O(V^2)로 효율적이지 않을 수 있습니다. 이에 대한 개선 방법으로 우선순위 큐(Priority Queue) 또는 힙(Heap) 을 활용한 다익스트라 알고리즘을 적용하면 시간 복잡도를 O((V + E) log V)로 줄일 수 있습니다. 본 글에서는 힙을 활용한 다익스트라 알고리즘의 개념, 원리, 동작 예시, 그리고 C, Java, Python 예제 코드를 상세히 다룹니다. 0. 힙의 원리오늘 포스팅은 힙에 대한 이해를 바탕으로 작성했습니다. 이 글을 읽기 전에 힙에 대해 먼저 숙지하시고 오시기를 추천드립니다. 힙에 대한 자세한 설명은 아래 링크에 작성했습니다. 2023.03.12 - [자료구조] - H.. 2025. 2. 10. 다익스트라 알고리즘(Dijkstra's Algorithm) 총 정리 - 개념, 원리, 동작 예시, 시간복잡도, 장단점, 주의점, C언어, Java, Python 예시코드 다익스트라 알고리즘은 최단 경로를 찾는 대표적인 알고리즘으로, 그래프에서 하나의 시작 정점에서 다른 모든 정점까지의 최단 거리를 계산하는 데 사용됩니다. 이번 글에서는 다익스트라 알고리즘의 개념, 원리, 동작 과정, 시간 복잡도, 장단점, 주의점, 그리고 C, Java, Python 예제 코드를 자세히 다루겠습니다. 1. 다익스트라 알고리즘이란?다익스트라 알고리즘은 가중 그래프(Weight Graph)에서 특정한 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 탐욕적인 접근법(Greedy Algorithm)을 기반으로 하며, 음의 가중치를 가지지 않는 그래프에서만 사용할 수 있습니다. 2. 다익스트라 알고리즘의 원리다익스트라 알고리즘은 다음과 같은 원리로 동작합니다.출발 노드를 .. 2025. 2. 7. 분할 정복(Divide and Conquer) 알고리즘 총 정리 - 개념, 원리, 동작예시, 장단점, 시간복잡도, C언어, Java, Python 예시코드 1. 분할 정복(Divide and Conquer) 알고리즘이란?분할 정복(Divide and Conquer) 알고리즘은 문제를 더 작은 하위 문제로 나누고(Divide), 각각을 독립적으로 해결한 후(Conquer), 그 결과를 합쳐서(Merge) 원래 문제의 해답을 도출하는 방식의 알고리즘입니다. 이 알고리즘은 재귀(Recursion)를 활용하여 문제를 단계적으로 해결하는 것이 특징입니다. 2. 분할 정복 알고리즘의 동작 원리분할 정복 알고리즘은 다음과 같은 세 가지 단계로 이루어집니다.분할(Divide): 문제를 동일한 유형의 작은 하위 문제로 나눕니다.정복(Conquer): 나눈 하위 문제를 개별적으로 해결합니다. 보통 이 단계에서 재귀적으로 호출됩니다.결합(Merge): 해결된 하위 문제들을.. 2025. 2. 7. 투포인터(Two Pointer) 알고리즘 총 정리 - 개념, 원리, 시간복잡도, 활용, 장단점, 주의점, C언어, Java, Python 예시코드 1. 투포인터 알고리즘이란?투포인터(Two Pointer) 알고리즘은 배열이나 리스트와 같은 선형 자료구조에서 두 개의 포인터를 사용하여 탐색 범위를 조절하며 문제를 해결하는 기법입니다. 주로 정렬된 배열에서 특정 조건을 만족하는 부분을 찾거나, 구간 합을 구하는 등의 문제에서 효과적으로 사용됩니다. 2. 투포인터 알고리즘의 동작 원리투포인터 알고리즘은 두 개의 포인터를 적절히 이동시키며 문제를 해결하는 방식입니다. 다음과 같은 원리로 동작합니다.예제: 정렬된 배열에서 특정 합을 갖는 두 수 찾기예를 들어, 정렬된 배열 [1, 3, 5, 7, 10, 15]에서 합이 12가 되는 두 수를 찾는 문제를 생각해 봅시다.초기 설정left 포인터를 배열의 첫 번째 요소(0번째 인덱스)에 위치시킵니다.right .. 2025. 2. 7. 이전 1 2 3 4 5 ··· 19 다음 반응형
