문제 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 설명 배열에 자연수 x를 넣는다. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 최대 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙이다. 최대 힙을 구현하기 위해 MaxHeap 클래스를 만들고 추가 기능과 제거 기능을 추가한다. class MaxHeap { List list; public MaxHeap() { list = new Arra..
문제 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 설명 1. 중간에 수의 변경이 빈번히 일어난다. 2. 그 중간에 어떤 부분의 합을 구하려 한다. N개의 수가 있고 위의 두 조건을 M번 실행한다고 가정한다. 매번 연산을 새로 하는 일반적인 방법으로는 1번 조건의 수행시간은 O(1) 이고 2번 조건의 수행시간은 \(O(N)\) 이다. 최종적으로 \(O(NM)\) 의 시간복잡도를 가진다..
트라이 (Trie) 문자열을 빠르게 검색할 수 있는 K진 트리 구조의 자료구조 단어 사전을 트라이로 생성한 후 찾을 단어가 생기면 트라이를 사용하여 검색한다. 트라이의 루트 노드는 항상 공백문자열 상태를 의미한다. 트라이에 단어 삽입하기 루트 노드부터 시작하여 삽입할 단어의 첫 글자부터 트라이를 탐색 만약 현재 노드의 자식 중 현재 입력 중인 철자에 해당하는 자식이 있다면 해당하는 자식 노드로 이동하고, 없다면 새로운 자식을 추가 단어를 삽입한 후에, 탐색된 마지막 노드에 현재 입력된 단어의 정보를 추가 트라이에 존재하는 가장 긴 문자열의 길이를 L이라 하고 총 문자열들의 수를 M이라 하자. 처음 트라이를 구축할 때에는 M개에 대해서 L만큼 걸리기 때문에 수행시간은 \(O(L \times M)\) 이다...
인덱스 트리 (Indexed Tree) 포화 이진 트리 형태의 자료구조 순서를 갖는 정보들이 주어졌을 때, 구간의 대표 값이나 연산 결과를 빠르게 얻을 수 있는 자료구조 구간 합, 구간 내 최댓값, 구간 내 카운트 등을 구할 때 많이 쓰인다. 세그먼트 트리는 인덱스 트리가 포함하고 있는 한 종류이다. 리프 노드 : 배열에 적혀 있는 수 내부 노드 : 왼쪽 자식과 오른쪽 자식의 합 리프 노드의 개수가 S개인 포화 이진 트리는 높이가 logS 이고 총 노드 개수는 (2 x S - 1) 개이다. 인덱스 트리 구현 방법 Top-Down 방식 : DFS 기반 트리 탐색 (재귀 호출) 인덱스 트리 개념을 그대로 코드로 수행 왼쪽 자식 = 2 x node, 오른쪽 자식 = 2 x node + 1 이용 가지치기가 가능..
힙 (Heap) 완전 이진 트리 형태의 자료구조 일반적으로 그룹을 정렬하거나 입력된 데이터 안에서 최소/최대 값을 찾을 때 사용한다. 또한, 우선순위 큐를 구현할 때에도 힙 자료구조를 사용한다. 데이터의 삽입과 삭제가 빠르며 각각의 수행시간은 \(O(logN)\) 이다. 최소 힙 (Min Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작다. 최대 힙 (Max Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크다. 힙의 삽입 연산 트리의 가장 마지막 위치에 노드를 삽입한다. 추가된 노드와 그 부모 노드가 힙 조건을 만족하는지 확인한다. 만족하지 않다면 부모와 자식의 키 값을 바꾼다. 조건에 만족하거나 추가된 노드가 루트에 도달할 때까지 2번~3번을 반복한다. 힙의 삭제 연..
트리의 정의 자료들 사이의 계층적 관계를 나타내는데 사용하는 자료구조로 부모-자식 관계로 표현된다. 트리는 1개 이상의 노드를 갖는 집합으로 루트 노드가 존재해야 하며 부분트리 또한 트리 구조를 따라야 한다. 트리의 용어 루트 노드 : 트리의 최상위 노드로써 유일함 깊이 : 루트 노드에서 해당 노드까지 도달하는데 사용하는 간선의 개수 레벨 : 노드의 깊이 + 1 높이 : 루트 노드에서 해당 노드까지 도달하는데 지나간 정점의 개수 트리의 높이 : 노드 중 가장 높이가 높은 노드의 높이 노드의 차수 : 노드의 자식 수 트리의 차수 : 해당 트리 내 모든 노드의 차수 중 최댓값 부모 노드 : 부모-자식 관계에서 상위 계층에 있는 노드 자식 노드 : 부모-자식 관계에서 하위 계층에 있는 노드 형제 노드 : 부모..
문제 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 설명 각 보석은 무게 M와 가격 V를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 C이다. 가방에는 최대 한 개의 보석만 넣을 수 있다. 먼저 보석의 무게와 가치를 저장할 Dia 클래스를 만든다. 가방마다 담을 수 있는 최대 무게가 있으므로 무게가 낮은 보석부터 넣으면서 판단하기 위해 무게..
우선순위 큐의 특징 큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. 우선순위 큐(Priority Queue)는 먼저 들어온 데이터가 아닌 우선순위가 높은 데이터가 먼저 나가는 자료구조이다. 우선순위 큐를 사용하기 위해서는 Comparable 인터페이스 또는 Comparator 인터페이스를 재정의해야 한다. 각각 compareTo 메소드와 compare 메소드를 재정의해야 되는데 거기서 우선순위 조건을 리턴해주면 우선순위 큐에서 알아서 우선순위대로 정렬해준다. 우선순위 큐는 일반적으로 힙을 이용하여 구현한다. 데이터를 삽입할 때 우선순위를 기준으로 최대 힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭..
