자료구조와 알고리즘23 다익스트라 알고리즘 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. 또한 특정한 하나의 정점에서 다른 정점으로 가는 최단 경로를 찾는다. 아래의 경우 다익스트라를 활용한다. 한 정점에서 다른 한 정점까지의 최단 경로 한 정점에서 다른 모든 정점까지의 최단 경로 모든 정점에서 다른 모든 정점까지의 최단 경로 여기서 각 정점은 노드로 표현하고, 정점 간 연결된 선은 간선으로 표현한다. 참고로 다익스트라 알고리즘은 가중치 방향그래프에서 활용될 수 있고, 가중치의 값은 절대로 음수값이 나올 수 없다. 또한 다익스트라 알고리즘은 매번 최단 경로 찾는 즉, 최적의 해를 찾는 과정을 거쳐 그리디 알고리즘으로 분류.. 2024. 2. 17. 힙 정렬 (Heap Sort) 힙 정렬 (Heap Sort) 힙 정렬은 기본적으로 힙 자료구조를 사용한다. 따라서 힙 자료구조를 먼저 학습하면 좋다. 간단하게, 힙 자료구조는 최소값 또는 최대값을 빠르게 찾아내기 위해 완전 이진 트리 형태로 만들어진 자료구조이다. 그리고 힙 자료구조는 우선순위 큐(Priority Queue)를 구현하는데 기반이 된다. 힙 정렬 구현하기 가장 먼저 초기 상태의 배열을 별도의 배열 선언 없이 최대 힙(Max-Heap) 또는 최소 힙(Min-Heap)으로 만든다. 가장 작은 서브 트리부터 최대 힙을 만족하도록 순차적으로 진행하면 최대 힙을 만들 수 있다. (최소 힙도 마찬가지이며, 이와 같이 힙을 만드는 과정을 heapify라고 한다.) 최대 힙을 사용하면 오름차순으로, 최소 힙을 사용하면 내림차순으로 정.. 2024. 2. 14. 우선순위 큐(Priority Queue) 우선순위 큐 우선순위 큐 개념 우선순위 큐(Priority Queue)는 큐나 스택과 비슷한 축약 자료형이다. 그러나 각 원소들은 우선순위를 갖고 있다. 우선순위 큐에서 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 만약 두 원소가 같은 우선순위를 가진다면 큐 방식으로 순서에 의해 처리된다. 우선순위 큐가 힙입라는 것은 널리 알려진 오류이다. 우선순위 큐는 리스트나 맵과 같이 추상적인 개념이다. 마치 리스트는 연결 리스트나 배열로 구현될 수 있는 것과 같이 우선순위 큐는 힙이나 다양한 다른 방법을 이용해 구현될 수 있다. 우선순위 큐는 큐와 유사하지만 우선순위가 높은 원소가 먼저 처리된다. 위에서 설명했듯이 우선순위 큐는 추상적인 개념이고, 우선순위 큐의 기능을 사용할 수 있.. 2024. 2. 9. 삽입정렬 (Insertion Sort) 삽입정렬 삽입정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성시키는 알고리즘이다. 삽입정렬 과정 처음 초기 상태이다. 처음 루프인 i는 1부터 시작하고, i번째 원소를 저장하기 위한 tmp를 선언한다. 두번째 루프인 j는 i-1부터 시작해서 0이상 일 때까지 반복한다. 이 j 루프를 돌면서 i번째 원소를 저장한 tmp를 적절한 위치에 삽입하는 방식이다. 여기서는 원소 5를 적절한 위치에 삽입한다. 1, 2번 과정을 거쳐서 원소 22는 적절한 위치를 삽입하는데 그대로 있다. 원소 11은 적절한 위치에 삽입한다. 원소 2를 적절한 위치에 삽입한다. 설명이 많이 부실한데 코드를 보면 바로 이해할 수 있을 것이다. 삽입정렬 코드 i.. 2024. 2. 7. 선택정렬(Selection Sort) 선택정렬 (Selection Sort) 선택정렬은 루프를 돌면서 가장 작은 값부터 앞으로 차곡차곡 옮기는 것을 말한다. 선택정렬 과정 위 배열이 있을 때 루프를 돌면서 가장 작은 값을 찾는다. 그리고 변수 idx에는 처음에 i값으로 초기화하고, 루프를 돌면서 가장 작은 값의 인덱스를 저장한다. 루프가 끝나서 가장 작은 값을 찾으면 i번째인 첫 번째 위치한 8 과 가장 작은 값 2를 서로 swap한다. swap하게 되면 첫번째 원소는 정렬이 된 것이다. (초록색 부분) 1과 2번의 과정을 반복한다. 역시 루프를 돌면서 가장 작은 값을 찾고 idx에는 가장 작은 값의 인덱스를 저장한다. 저장이 완료되면 i번째인 5와 가장 작은 값 5를 swap한다. 물론 이 결과는 그대로 있다. 위 과정을 계속 반복하게 되.. 2024. 2. 7. B Tree B Tree 이진 탐색 트리(BST)의 특징 중 하나는 자식 노드는 최대 2개까지 갖는 형태를 말한다. 그렇다면 자식 노드를 최대 2개에서 더 늘릴 방법이 없는걸까? B Tree 개념 B 트리는 트리 자료구조의 일종으로 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 2개 이상 갖는 트리 구조이다. B Tree 특징 자식 노드의 최대 개수를 늘리기 위해 부모 노드에 Key를 하나 이상 저장한다. 부모 노드의 Key들을 오름차순 정렬한다. 정렬된 순서에 따라 자식 노드들의 Key 값의 범위가 결정된다. 모든 leaf 노드들은 같은 레벨에 있다는 특징을 가지고 있다. 검색 성능해서 최악의 경우에도 Red-Black 트리와 동일하게 최악의 경우에도 O(log N)의 시간복잡도를 같는다 B T.. 2024. 2. 6. 이전 1 2 3 4 다음
