알고리즘10 알고리즘 - 힙 & 우선순위 큐 이번 시간에는 힙&우선순위 큐에 대해서 알아보도록 하겠습니다. 힙은 완전 이진 트리의 일종입니다. 힙은 우선순위 큐를 위해 만들어진 자료구조이며 정렬하기에 따라 Min 힙과 Max 힙으로 나뉘어집니다. 완전 이진 트리의 일종이므로 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있으며, 마지막 레벨에 노드가 있을 때는 항상 왼쪽부터 순서대로 채워나가게 됩니다. 그렇기 때문에 해당 특징을 가지게 됩니다. 1. [부모 노드]가 가진 값은 항상 [자식 노드]가 가진 값보다 크다. 2. 노드 개수를 알면, 트리 구조는 무조건 확정할 수 있다. 완전 이진트리이기 때문에 각각의 노드들은 연결되어 저장되게 된다. (배열의 형태) 힙에 대한 구현은 뒤에서 우선순위 큐를 구현하며 같이 보도록 하겠습니다. 우선순위 큐는 .. 2023. 2. 12. 알고리즘 - 트리, 이진트리 오늘은 트리에 대해서 알아보도록 하겠습니다. 트리란 계층적 구조를 갖는 데이터를 표현하기 위한 자료구조이다. 트리를 이루는 구성요소로는 '노드'와 '간선'으로 이루어져 있다. 간선으로 이루어진 그래프와는 '계층'적인 구조를 가지는 것이 특징이다. 그 외에도 트리는 이러한 성질을 가지고 있다. 1) N개의 노드를 가진 트리는 항상 N-1개의 간선을 지닌다. 2) 트리에 존재하는 한 노드에서 어떠한 노드로 가는 경로는 항상 유일해야 한다. 트리를 잘 사용하기 위해서는 트리와 관련된 용어에 대해서 알아보아야 한다. - 루트 노드 : 최상위 계층의 노드 - 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수 (aka. 몇 층?) - 높이(height) : 가장 깊숙히 있는 노드의 길.. 2023. 2. 12. 다익스트라 알고리즘 다익스트라 알고리즘은 대표적인 최단 경로 탐색을 하는 알고리즘입니다. 다익스트라 알고리즘은 출발 정점을 시작으로 다른 모든 정점으로 향하는 모든 최단 경로 및 비용을 알려줍니다. 하지만 간선의 비용은 음수가 될 수 없습니다. 다익스트라 알고리즘은 하나의 정점에 대한 최단 경로를 알기 위해서 해당 경로에 향하기까지의 모든 정점들에 대해 최단 경로들을 구해야 합니다. 그렇기 때문에 최단 경로를 구하면서 이전에 구해놓은 최단 거리의 정보를 사용하게 됩니다. 처음 정점에서 간선을 통해 연결된 정점에 대한 최단 거리를 구하고, 방문하지 않은 정점들 중에서 가장 작은 거리(비용)을 가진 정점에 대해서 탐색을 하게됩니다. 첫 정점과 마찬가지로 연결된 간선들에 대해서 최단 거리를 구하게 되는데, 도착 정점이 이미 가지.. 2023. 2. 11. BFS - 너비 우선 탐색 BFS ( Breadth-First Search ) 는 너비 우선 탐색이라는 탐색법이다. 이전에 포스팅한 깊이 우선 탐색과는 다르게 한 노드에 대해서 갈 수 있는 모든 노드에 대한 탐색을 같이 진행하므로 최단 거리를 찾거나 최단 루트를 찾는 문제 등에 자주 쓰이는 알고리즘이다. 모든 노드들에 대해서 한번씩 탐색을 시도하고, 해당 노드에서 탐색 가능한 모든 노드들에 대해서도 탐색을 해야하므로 큐 자료구조를 이용하여 모든 노드들에 대한 탐색을 시도하되, 먼저 탐색해야 하는 목록에 오른 노드들부터 탐색을 할 수 있게끔 구현합니다. 만약 BFS를 마치고, 해당 탐색 루트 중에서 원하는 위치로 이동 가능한 최단루트를 저장해두고 싶다면, 해당 노드로 최단 비용으로 올 수 있는 바로 이전의 노드의 값을 저장하여 손쉽.. 2023. 2. 10. 이전 1 2 3 다음
