728x90 반응형 소프트웨어13 다익스트라 알고리즘(Dijkstra's Algorithm) 정의 동작방식 복잡도 사용예시 안녕하세요, 이번 포스팅에서는 자주 쓰이는 소프트웨어 알고리즘 중 하나인 다익스트라에 대해 알아보겠습니다. 다익스트라 알고리즘(Dijkstra's Algorithm)은 가중치가 있는 그래프에서 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 음의 가중치를 허용하지 않으며, 주로 길 찾기 문제 등에 사용됩니다. 1. 그래프 초기화: 시작 정점을 기준으로 모든 정점까지의 거리를 무한대로 설정하고, 시작 정점의 거리를 0으로 설정합니다. 2. 우선순위 큐(최소 힙) 초기화: 시작 정점을 우선순위 큐에 넣습니다. 이때, 시작 정점의 거리를 우선순위 큐의 우선순위로 설정합니다. 3. 최단 경로 탐색: 우선순위 큐에서 가장 거리가 짧은 정점을 꺼내고, 해당 정점과 연결된 모든.. 2023. 7. 26. 이진 탐색(Binary Search) - 정의 / 예시 코드(C++) 이진 탐색은 정렬된 배열에서 특정한 값을 찾는 알고리즘으로, 탐색 범위를 반씩 줄여가며 원하는 값을 찾아내는 방법입니다. 이 알고리즘은 배열이나 리스트 등의 데이터 구조에서 효율적인 탐색을 수행할 수 있습니다. 이진 탐색의 동작 원리는 다음과 같습니다. 1. 주어진 배열을 오름차순으로 정렬합니다. 2. 탐색할 값과 배열의 중간 값을 비교합니다. - 중간 값이 탐색할 값과 일치하면 탐색 성공입니다. - 중간 값이 탐색할 값보다 크면, 배열의 왼쪽 절반에 대해 이진 탐색을 수행합니다. - 중간 값이 탐색할 값보다 작으면, 배열의 오른쪽 절반에 대해 이진 탐색을 수행합니다. 3. 탐색 범위가 축소될 때까지 위의 과정을 반복합니다. 4. 탐색 범위가 더 이상 없거나, 탐색할 값이 발견되지 않으면 탐색 실패입니다.. 2023. 6. 4. 기수 정렬(Radix Sort) - 정의 / 예시 코드(C++) 기수 정렬(Radix Sort)은 비교 정렬 알고리즘이 아닌 정렬 알고리즘 중 하나로, 비교 대상의 특정한 속성을 이용하여 정렬하는 방법입니다. 기수 정렬은 숫자나 문자열과 같은 자료를 정렬하는 데에 주로 사용되며, 각 자릿수나 문자의 위치를 기준으로 정렬을 수행합니다. 기수 정렬의 동작 방식은 다음과 같습니다. 1. 가장 낮은 자릿수부터 시작하여 가장 높은 자릿수까지 반복적으로 정렬 작업을 수행합니다. 2. 각 자릿수를 기준으로 정렬하기 위해, 0부터 9까지의 버킷(또는 큐)을 생성합니다. 이 버킷은 해당 자릿수의 값을 가진 요소를 저장하는 용도로 사용됩니다. 3. 정렬할 자료를 순회하면서 각 요소의 해당 자릿수 값을 확인하고, 그에 맞는 버킷에 요소를 넣습니다. 예를 들어, 첫 번째 반복에서는 일의 .. 2023. 6. 3. 힙 정렬(Heap Sort) - 정의 / 예시 코드 힙 정렬(Heap Sort)은 힙 자료구조를 기반으로 동작하는 정렬 알고리즘입니다. 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 구성하여 배열을 정렬하는 방식으로 동작합니다. 힙 정렬은 주로 배열 기반의 힙 자료구조를 사용하여 구현됩니다. 아래는 힙 정렬의 동작 과정을 단계별로 설명한 것입니다. 1. 주어진 배열을 최대 힙 또는 최소 힙으로 구성합니다. 이 단계를 힙 구성(Heapify) 단계라고 합니다. 최대 힙을 구성하는 경우, 부모 노드는 항상 자식 노드보다 큰 값을 가지며, 최소 힙을 구성하는 경우에는 그 반대입니다. 2. 힙에서 최상단에 있는 노드(최대 힙의 경우 최댓값, 최소 힙의 경우 최솟값)를 꺼내어 배열의 마지막 위치로 이동시킵니다. 이 단계를 반복적으로 수행하면, 배열은.. 2023. 6. 2. 이전 1 2 3 4 다음 728x90 반응형
