이번 알고리즘 문제에 트리 순회 관련 문제가 있어 정확히 트리가 무엇인지, 트리 순회가 무엇인지 알아보고자 포스팅을 하게 되었다. Graph 트리에 대해 알아보기 전에, 조금 더 넓은 개념인 그래프를 살펴보고 가자. 그래프는 노드와 노드를 연결하는 간선으로 구성되어 있는 자료구조이며, 정확히는 노드 간의 관계를 간선을 통해 표현할 수 있는 자료구조이다. 그림으로 보면 다음과 같은 구조를 그래프라고 한다. 그림을 보면 몇 가지 특징을 알 수 있는데, 정리하자면 다음과 같다. 특정 노드에서 어떤 특정 노드로 가는 경로가 하나가 아닐 수도 있다. 계속 같은 경로를 도는 순환이 발생할 수 있다. 가장 최상위 노드가 존재하지 않는다. 부모-자식의 관계가 없다. 간선의 방향이 있을수도 있고, 없을 수도 있다. Tr..
Queue 오늘은 큐에 대해 공부했다. 큐의 구현 방식에는 Linear Queue, Circular Queue, Double Ended Queue 등 다양한 방식이 있는데, 오늘은 Circular Queue의 구현을 집중적으로 다뤄볼 예정이다. 큐는 후입선출 구조인 스택과는 다르게, 선입선출 구조를 가진 자료구조이다. 선입선출 구조란? 영어로는 First In First Out, 줄여서 FIFO라고 부르기도 하며, 자료구조에 먼저 삽입된 데이터가 먼저 빠져나온다는 의미이다. 우리가 맛집 웨이팅을 할 때 대기줄이 먼저 온 사람부터 들어가는 구조와 같다! 가장 기본적인 큐 자료구조는 리스트를 활용하여 구현한다. 리스트의 맨 앞부터 원소를 하나하나 쌓아나가고, 큐에서 원소를 삭제하면 가장 앞에 있는 원소부터 ..
https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 이번에 풀 문제는 가장 가까운 두 점이다. 2차원 평면상에 n개의 점이 주어졌을 때, 가장 가까운 두 점의 거리를 구하는 간단한 문제이다. 설명은 아주 간단하지만 풀이는 그렇지 않다! n의 범위가 최대 100,000 이기 때문에 완전 탐색으로 문제를 풀게 되면 시간 초과를 피하지 못한다... 나는 이 문제를 분할 정복 방식으로 풀었는데, 풀이가 이전에 풀었던 히스토..
