인덱스 트리 (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 메소드를 재정의해야 되는데 거기서 우선순위 조건을 리턴해주면 우선순위 큐에서 알아서 우선순위대로 정렬해준다. 우선순위 큐는 일반적으로 힙을 이용하여 구현한다. 데이터를 삽입할 때 우선순위를 기준으로 최대 힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭..
문제 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 설명 A와 B의 임의의 부 배열 두 개의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구해야 한다. 먼저 A와 B의 원소를 저장할 배열인 arrA와 arrB를 만든다. 그 다음, A와 B의 모든 부 배열의 각 원소의 합을 저장할 리스트인 sumA와 sumB를 만든다. 모든 부 배열의 각 원소의 합을 저장 한..
문제 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 설명 다음 줄로 내려갈 때에는 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다. DP만 사용해 문제를 풀면 모든 숫자를 배열로 담고 활용해야 하므로 메모리 제약에 걸린다. 따라서, 슬라이딩 윈도우 알고리즘을 같이 사용하면 dp 배열을 계속해서 초기화하면서 문제를 풀 수 있다. 먼저 처음에 maxDP와 minDP를 첫 줄의 숫자들로 초기화한다. 다음 줄부터 들어갈 m..
투 포인터 리스트에서 원하는 값을 얻기 위해 두 개의 포인터를 이용해 각 위치를 기록하면서 처리하는 알고리즘이다. 반복문을 사용해 리스트를 단순 탐색하는 것보다 투 포인터를 사용하면 시간 복잡도를 낮출 수 있다. 리스트의 크기가 N일 때, Worst Case일 경우 시간복잡도를 알아보자. 전자의 경우에는 반복문을 N번씩 두번 돌려서 시간복잡도는 \(O(N \times N) = O(N^2)\) 이 된다. 후자의 경우에는 두 포인터가 모두 N번 탐색하여 시간복잡도는 \(O(2N) = O(N)\) 이 된다. 투 포인터는 위의 그림처럼 두 가지 방식으로 쓰인다. 앞에서부터 시작하는 포인터와 끝에서부터 시작하는 포인터가 중간에서 만나는 방식 둘 다 앞에서 시작해서 하나의 포인터가 다른 포인터보다 앞서면서 끝에 도..
