Byeo

목차 개요 설명 코드 개요 이 문제는 효율성까지 평가하는 문제입니다. 쿼리에 (코테 참여 언어, 지원 직군, 지원 경력, 선호하는 소울푸드)를 구분하여 입력 받고 있으며, 다음으로 점수를 입력 받아 해당 점수 이상의 사람이 몇 명 있는지 반환하는 문제입니다. 설명 제가 구현한 것은 segment tree를 활용한 것입니다. 점수를 제외한 항목들을 살펴보면 총 24개(322*2)의 조합이 나오게 되는데, 이 조합들 각각에 segment tree를 이용해 점수를 log N 타임에 구할 수 있도록 하였습니다. Query중에 '-'와 같은 wildcard는 해당하는 조합의 segment tree들을 조사한 뒤에 합하면 될 것입니다. 예를 들어, ('python', -, 'senior', 'pizza', 100)..

목차 개요 요약 개요 설명 코드 테스트 케이스 개요 요약 y좌표가 높은 별부터 시작해서 아래로 sweeping을 합니다. 특정 별 A를 기준으로 좌상단에 별의 개수 $N$, 우상단에 별의 개수 $M$을 각각 segment tree를 통해 구한 후, 곱합니다. $N*M$이 별 A를 기준으로 그릴 수 있는 별자리 개수입니다. $N*M$은 별 A만을 기준으로 삼았을 때입니다. 이를 모든 별에 대해 구해 누적하면 됩니다. 같은 y좌표를 지닌 별들 간에는 별자리를 그릴 수 없습니다. 따라서 같은 y좌표를 가진 별자리들을 batching해서 처리하여야 합니다. 개요 이 문제는 [boj 5419 - 북서풍]을 푸셨다면 쉽게 응용할 수 있습니다. 마찬가지로 이번에는 위에서 아래 방향으로 훑어가면서 등장하는 별들의 x좌..

목차 개요 요약 개요 설명 코드 개요 요약 문제를 풀기위한 key point는 크게 다음과 같습니다. 북서풍을 타고 이동할 수 있는 섬의 쌍을 구하기 위해서는 각 섬마다 자신보다 왼쪽이면서 위에 있는 섬의 개수를 구해서 더하면 됩니다. 섬의 개수가 방대해서 일일이 구하기에는 시간복잡도가 큽니다. 따라서 sweeping과 segment tree를 활용하여 한 방향으로 섬 하나하나 sweep해가야 합니다. 이 과정에서 조건을 만족하는 섬의 개수를 segment tree를 통해 빠르게 알아냄과 동시에 자신을 segment tree에 등록하면 됩니다. Segment tree에 좌표를 사용하기에는 범위가 너무 넓습니다. 따라서 좌표 압축을 한 번 수행해서 20억 개의 원소가 아닌 75,000개의 원소 만으로도 해..

목차 개요 설명 코드 개요 이 문제는 k 번째 원소를 효율적으로 찾는 문제입니다. 이는 segment tree를 사용하여 구할 수 있습니다. 이 문제는 [boj 12899-데이터 구조]와 굉장히 유사하므로 이를 참고하시면 됩니다. k 번째 원소를 segment tree를 이용해 효율적으로 찾는 방법은 [boj 12899-데이터 구조]를 참고하세요. 이 포스트에서는 k를 어떻게 계산해야 할 지에 대해서만 다루겠습니다. 설명 요세푸스 문제는 수열에서 일정한 간격으로 점프해 가면서 숫자들을 하나씩 빼낸 수열입니다. 백준의 예제 N = 7, K = 3의 경우에는 아래 그림을 보면 이해 하실 수 있으리라 생각합니다. 원소를 지우고 나면, 그 원소부터 다시 k개 만큼 뒤로 이동한 뒤에 또 그 원소를 지웁니다. 만약..

목차 개요 설명 코드 개요 해당 문제는 Segment Tree를 변형하여 사용하는 문제입니다. 이 문제에서 Segment Tree는 기존에 알던 부분 합, 부분 곱, 최소값, 최대값 등을 사용하는 것이 아니라 현재까지 어떤 query들이 어떤 구간에 영향을 주는 지를 저장하기 위해 사용합니다. 즉, 1 a b c 의 query가 들어오면, a ~ b 구간에 c라는 값을 더해야 합니다. 그런데 일일이 a, a+1, a+2, ..., b-1, b 까지 더하는 과정은 시간 소요가 크므로, a ~ b 구간을 담당하는 segment tree node에 일단 저장을 해놓습니다. 다음 2 a 의 query가 들어오면, root node부터 leaf node까지 내려가면서 그 동안 저장되어 있던 segment node..

목차 개요 설명 한계 코드 개요 해당 문제는 배열이 주어져 있을 때, 특정 부분의 구간 합을 구하는 문제입니다. 눈여겨 볼 것은 배열이 주어지고 난 뒤, 배열 값이 변하지 않는다는 사실입니다. 이 문제는 첫 index부터 마지막 index까지 부분합을 모두 계산한 뒤, 결과를 저장해서 빼기 연산으로 쉽게 풀 수 있습니다. 즉, DP 문제입니다. 설명 5 3 5 4 3 2 1 1 3 2 4 5 5 백준 예제로 방법을 간단하게 보겠습니다. 배열의 원소 5, 4, 3, 2, 1로 들어온 값을 arr에 저장해 둡시다. 그리고 0번 ~ i번 까지의 배열 합을 sum[i]에 저장해 놓도록 하죠. 처음 sum[0] 은 단순히 arr[0]이 되겠죠. 이제 다음부터 sum[1]은 arr[1] + sum[0], ... s..

boj 12899 - 데이터 구조 목차 개요 설명 코드 개요 이 문제는 Binary search 과정과 유사한 문제입니다. 다만, "X보다 작은 수는 몇 개 있는가?" 를 쉽게 알아내기 위하여, 이 과정에서 부분 합 segment tree를 사용합니다. 먼저, 2,000,000개의 배열을 관리할 수 있는 segment tree를 구성합니다. 1번 query 가 들어온 경우 : 요청 값을 a라 했을 때, a를 담당하는 leaf 노드를 찾아 그 값에 +1을 해준 뒤 순차적으로 root node까지 update해나갑니다. 2번 query 가 들어온 경우 : 이는 binary search와 유사합니다. Child node 두 개를 살펴 본 뒤에, 내가 몇 번째 원소를 찾느냐에 따라 왼쪽 혹은 오른쪽 중 하나만 ..

boj 9345 목차 개요 설명 코드 개요 boj 9345 - 디지털 비디오 디스크(DVDs) 문제도 segment tree를 응용한 문제입니다. Query 0 이 들어왔을 때는 DVD 배열에서 a번째와 b번째의 값을 바꿔주면 되고, Query 1이 들어왔을 때는 a ~ b 의 구간을 검색하면 됩니다. 얼핏 보기에는 segment tree를 어떻게 응용해야 하는 지에 대해 의문이 들 수 있습니다. 하지만 잘 살펴보면, Query 1이 들어왔을 때는 "a ~ b 의 구간에서 DVD가 a번부터 b번까지 모두 존재하는가" 를 살펴 보면 됩니다. 문제를 바꾸면, a ~ b 구간에서 중간 DVD를 살펴 볼 필요 없이 최솟값과 최댓값을 살펴보면 됩니다. 즉, a ~ b 구간의 최솟값이 a이면서, 최댓값이 b라면 조..

BOJ 2357 - 최솟값과 최댓값 목차 설명 code 이 문제는 segment tree를 변형하면 해결할 수 있는 문제입니다. 기존에 child의 부분 합을 저장했다면, 이 문제에서는 child의 최소값과 최대값을 저장하면 됩니다. Segment tree에 대한 설명은 [세그먼트 트리(Segment tree)]에서 볼 수 있습니다. 설명 BOJ 2357의 예제를 그대로 그려보면 다음과 같은 segment tree를 그릴 수 있을 것입니다! Maximum Segment Tree Minimum Segment Tree 18 ~ 23, 25 ~ 32 node는 segment tree의 코드를 따라 구현하면 관련이 없는 leaf ndoe입니다. Code 1. 코드의 깔끔함을 위하여 같은 class로 구현하되, ..

목차 Solution 1. 선형 탐색 Solution 2. 세그먼트 트리 1) 생성하기 (Initialization) 2) 검색하기 (Search) 3) 수정하기 (Update) 예제) BOJ 2042 세그먼트 트리(Segment tree)는 어떤 수열들의 특정 구간에 대한 부분합, 최소값, 최대값 등을 쉽게 구하기 위하여 사용하는 자료구조 입니다. 보통 부분합, 최소값 등을 구하고자 하는 질의(query)가 여러 번 있을 때 사용합니다. 예를 들어, 배열(int arr[12])에 다음과 같은 값들이 있다고 가정하고 arr[1]~arr[8]의 부분합을 구해보죠. int arr[12] = {10, 7, 9, 0, 11, 7, 6, 5, 2, 13, 8, 6, 9}; Solution 1. 선형 탐색 구간 1..