알고리즘/이론 (46) 썸네일형 리스트형 펜윅 트리 [1. 개요] 구간 합을 빠르게 구하기 위한 구간 트리의 상위 버전으로 볼 수 있는 자료구조 구간 합 대신 부분 합만을 빠르게 계산 할 수 있는 자료 구조를 만들어도 구간 합을 계산 할 수 있다. => 구간 트리가 미리 계산해 저장하는 정보의 상당수가 필요 없다. 하나의 긴 구간 밑에 두 개의 작은 구간이 있을 때, 이 두 구간 중 오른쪽 구간은 항상 지워도 된다. => 필요한 구간의 수는 정확하게 N 개이다. => 구간 트리가 보통 4N 개가 필요하다고 했을 때, 메모리를 조금이라도 덜 사용한다. 또한, 각 구간이 포함하는 오른쪽 끝 원소들이 모두 다르다. => 구간 트리에서 (0, 7) (4, 7) 등 끝나는 구간이 같은 것이 다수 존재함. [2. 구현] tree[i] = 오른쪽 끝 위치가 A[i] .. 구간 트리 - 예제 1 [1. 문제 설명] N 개의 표지판에 각 위치 마다 해발 고도가 적혀있고, Q 개의 구간에서 최대 고도와 최소 고도의 차이가 해당 구간의 난이도 일 때 각 구간 별 난이도를 출력하도록 한다. [2. 풀이 접근] 구간 트리가 각 구간 별 고도의 최대/최소를 저장 하도록 한다. 구간 트리를 초기화 하는데 걸리는 시간 : O(N) Q 개의 구간을 조회하는데 걸리는 시간: O(QlogN) [3. 코드] 우선 순위 큐 - 예제 1 [1. 문제 설명] 수열에 새로운 수가 추가 될 때 마다 수열 내 중간 값들의 합을 출력한다. [2. 풀이 접근] 수열의 중간 값은 정렬 된 수열 내 중앙에 오는 값이며, 수열의 길이가 짝수 개인 경우 둘 중 더 작은 값이다. 원소 추가 때마다 정렬을 하면 N2LogN 이므로 시간초과가 발생한다. maxHeap 에는 정렬된 수열의 왼쪽 값들이 저장되고 minHeap 에는 정렬된 수열의 오른쪽 값들이 저장된다 하면 중간 값은 maxHeap 의 root 와 minHeap 의 root 사이에 존재하게 된다. 수열의 길이가 홀수 개인 경우와 (empty 인 경우 최대 힙의 root 가 중간 값이 된다.) 짝수 개인 경우 더 작은 값이 중간 값이 되는 특성을 이용하여 중간 값 까지 최대 힙에 저장하도록 한다. 여.. 이진 트리 - 예제 2 [1. 문제 설명] [2. 풀이 접근] [3. 코드] 이진 트리 - 예제 1 [1. 문제 설명] https://algospot.com/judge/problem/read/NERD2 [2. 풀이 접근] [3. 코드] 트리 - 예제 2 [1. 문제 설명] [2. 풀이 접근] [3. 코드] 트리 - 예제 1 [1. 문제 설명] tree 에 대해서 전위 순회와 중위 순회가 주어졌을 때, 후위 순회 한 결과를 출력한다. [2. 풀이 접근] 비슷한 문제가 있었으니 자세한 설명은 아래를 참고 https://testkernelv2.tistory.com/354 [3. 코드] 06. 결정 문제 - 예제 2 [1. 문제 설명] N개의 도시를 지나치는데, i 번째 도시까지의 남은 거리를 나타내는 표지판이 도착하기 M 미터 전부터 시작해서 G 미터 간격으로 설치 된다. 시작점으로 부터 각 도시 까지의 거리(L) 와 M, G 에 대한 값이 주어질 때, K번째 표지판의 위치를 찾는다. Li, Mi, Gi (1 06. 결정 문제 - 예제1 [1. 문제 설명] n 개의 탐사기지와 무전기가 존재 모든 무전기의 통신 반경은 d 따라서, 두 탐사 기지 사이의 거리가 d 이하이어야만 연락 가능 항상 모든 기지 간에 서로 연락 가능하다록 하는 무전기의 최소 통신 반경을 계산 [2. 풀이 접근] printf / scanf 서식문자 https://testkernelv2.tistory.com/57?category=513498 [3. 코드] 05. 조합 탐색 - 예제2 [1. 문제 설명] m가지의 음식을 준비할 수 있고, n명의 친구를 초대하려고 한다. 각 친구가 먹을 수 있는 음식, 먹을 수 없는 음식이 주어질 때, 각 친구가 먹을 수 있는 음식이 최소한 하나씩 있게 하려면 최소 몇가지의 음식을 해야하는가? [2. 풀이 접근] NP 완비 문제 중 하나로, 다항 시간에 푸는 방법은 아직 없다. 탐욕적 접근 방법으로 가장 많은 사람들이 먹을 수 있는 음식을 만들어 보는 방식으로 접근 할 수 있지만, 모든 입력에 대해 최적해를 찾아낼 수는 없다. 예제) ??? 완전 탐색으로 접근 해서, 간단한 가지치기를 하면 답을 구할 수 는 있지만, 시간 내에 동작하지 않는다. 이 문제를 푸는 간단한 방법은 탐색의 형태를 바꾸는 것 이다. 매 재귀 호출마다 아직 먹을 음식이 없는 친구를.. 이전 1 2 3 4 5 다음
