연결 리스트 (Linked List)
개요 연결 리스트는 데이터들을 포인터로 연결시켜 관리하는 자료구조이다. 데이터는 노드에 저장되는데, 각 노드에는 데이터에 대한 정보와 다음 위치에 대한 정보, 그리고 리스트의 종류에 따라 이전 위치에 대한 정보까지 저장된다. 연결 리스트는 여러가지 종류가 있지만 흔히 볼 수 있는 건 다음과 같은 3가지이다.각 노드의 다른 노드를 가리키는 포인터가 다음 노드 하나만을 가리키는 단일 연결 리스트(Singly Linked List)이전 노드와 다음 노드 2개를 가리키는 이중 연결 리스트(Doubly Linked List)head와 tail을 연결시켜버린 원형 연결 리스트(Circular Linked List) 이 중에서 나는 이중 연결 리스트를 기준으로 설명할 것이다. (아래 설명을 잘 이해한다면 나머지 두 ..
[BOJ] 14942 개미
https://www.acmicpc.net/problem/14942 문제 요약 정점의 개수가 N인 트리가 주어진다. 각 정점 사이에는 가중치(거리)가 있고, 모든 정점에는 $a_i$만큼 이동할 수 있는 개미들이 있다. 모든 개미들이 루트(1번 노드)를 향해 갈 때, 얼마나 루트에 가까운 정점까지 갈 수 있나 물어보는 문제이다. 풀이 처음 생각할 수 있는 풀이는 모든 정점에 있는 개미에 대해 에너지가 다 떨어질 때 까지 부모 노드로 한 칸씩 이동하는 방법이다. 이 풀이의 시간복잡도를 생각해보자. N마리의 개미에 대해 각각 $O(N)$의 시간복잡도가 걸리기 때문에 총 시간복잡도는 $O(N^2)$이다. 하지만 N의 범위가 ${1}\leq{N}\leq{100000}$이기 때문에 TLE가 난다. 이를 어떻게 하면..