[Data Structure] 우선순위 큐와 힙(Priority Queue and Heap) 이해하기

인트로 본 포스팅을 이해하기 위해선 힙 자료구조 배경지식이 필요합니다. 본 포스팅은 1)우선순위 큐 설명 2)우선순위 큐와 힙의 관계 3)구현 코드로 구성되어 있습니다. 우선순위 큐란? 큐(Queue)란 먼저 들어간 데이터가 먼저 나오는 선입 선출(First In First Out, FIFO) 구조의 자료구조를 말한다. 우선순위 큐(Priority Queue)는 일반 큐와 이름은 비슷하지만 동작하는 방식이 다르다. 우선순위 큐의 각 원소(데이터)는 저마다의 우선순위를 가지고 있으며 들어간 순서에 상관없이 높은 우선순위를 가진 원소가 순서대로 나온다는 특징이 있다. 우선순위 큐와 힙 (우선순위 큐 ≠ 힙) 당신에게 음료수 자판기를 만들라는 과제가 주어졌다. 당신은 자판기를 만들기 위한 고민을 하기 시작할 ..

• format_list_bulleted Data structure
• · 2021. 9. 2.
• textsms

[Algorithm] BFS (Breadth First Search, 너비 우선 탐색) 알고리즘

인트로 그래프의 탐색 알고리즘인 BFS(Breadth First Search, 너비 우선 탐색)를 구현해보려 한다. DFS와 다르게 BFS는 주로 한 가지 목적으로 사용된다. 그것은 가중치가 없는 그래프의 최단 경로를 구할 때 사용된다. 본 포스팅에선 C# 기반 배열과 리스트(List)로 BFS를 구현하는 간단한 코드와 최단 경로 출력 코드를 소개하려 한다. 결론부터 말하면 Queue를 사용해서 BFS를 구현했다. DFS가 궁금하다면? DFS (Depth First Search, 깊이 우선 탐색) 알고리즘 [Algorithm] DFS (Depth First Search, 깊이 우선 탐색) 알고리즘 인트로 그래프의 탐색 알고리즘인 DFS(Depth First Search, 깊이 우선 탐색)를 구현해보려 한..

• format_list_bulleted Algorithm/탐색
• · 2021. 8. 23.
• textsms

[Data Structure] 트리(Tree)와 그래프(Graph) 이해하기

인트로 그래프 탐색 알고리즘인 BFS, DFS와 트리 탐색 알고리즘인 전위 중위 후위 순회를 정리하기 전에 배경지식인 트리와 그래프의 관계 그리고 특징을 정리하려 한다. 결론부터 말하면 트리는 특정 조건을 만족하는 그래프이다. 즉, 트리는 그래프이지만 그래프는 트리가 아니다. 그래프(Graph) 그래프는 현실에 존재하는 개체 간의 관계를 표현하는 하나의 표기법일 뿐이다. 현실에서도 그래프를 찾아볼 수 있으며 흔히 보는 지하철 노선도가 그래프이다. 기흥이라는 점이 개체, 기흥과 강남대를 이어주는 선이 관계이다. 컴퓨터공학적인 시선으로 그래프를 바라보면 개체는 노드(Node)로, 관계는 간선(Edge)으로 표현된다. 그래프도 여러 종류가 존재한다. 대표적으로 1) 무방향 그래프 (Undirected Grap..

• format_list_bulleted Data structure
• · 2021. 8. 16.
• textsms