Leo.K | To become a cooler Developer

취업을 하고 자사의 솔루션을 학습한다는 핑계로 미뤄두었던 알고리즘 학습을 다시금 천천히 시작해보려 한다. 오늘은 트리부터 시작해서 간단한 개념 정리와 문제풀이를 하려고 한다. 트리는 노드와 에지로 연결된 그래프의 특수한 형태로, 주요 특징은 아래와 같다. 순환 구조를 가지고 있지 않고, 1개의 루트 노드가 존재한다. 루트 노드를 제외한 나머지 노드는 반드시 단 하나의 부모노드를 가진다. 2개 이상의 부모 노드가 있다면 순환구조가 생길 수 밖에 없음 트리의 부분 트리 역시 트리의 모든 특징을 따른다. 트리의 구성요소 구성 요소 설명 노드 데이터의 index와 value를 표현하는 요소 에지 노드와 노드의 연결관계를 나타내는 선 루트 노드 트리에서 가장 상위에 존재하는 노드 부모 노드 두 노드 사이의 관계에..

오늘은 다익스트라 문제를 본격적으로 풀어보기 전에 먼저 그래프 문제에서 자주 사용하는 우선순위 큐라는 자료구조에 대해 정리를 해보겠다. 결국에 큐이기 때문에 add, poll, peek 등의 연산을 수행하지만, 하는 일과 내부 구조는 기존의 큐와 완전히 다르다. poll이나 peek의 연산으로 추출되는 원소는 기존 큐의 연산순서인 FIFO에 따라서 제일 먼저 들어온 요소가 나오는 것이 아니라, 말 그대로 현재 큐 안에서 제일 우선순위가 높은 요소가 먼저 나온다. 이는 우선순위 큐가 기존 알던 큐가 아닌 힙(heap)이라는 자료구조로 구현되기 때문에 가능하다. 가장 많이 사용하는 형태는 클수록 우선순위가 높은 형태 or 작을수록 우선순위가 높은 형태이다. 어떤 우선순위 큐의 front에 위치하는 원소가 가..