Jonyo Programming

[BOJ 13537(P4)리뷰] 유명한 수열과 쿼리 1번문제다. 세그먼트 트리 + 이분탐색을 이용하여 문제를 해결할 수 있다. 세그먼트 트리를 구성할때 각 부모노드들은 자식의 값들을 정렬된 상태로 갖는 형태여서 머지소트 트리 라고도 불리는 것 같다. 이렇게 트리를 구성함으로 우리는 각 구간별 정렬된 값들을 가질 수 있다. 쿼리가 들어오면 구간을 확인한 후에 K보다 큰 값들의 개수를 출력하면 된다. 정렬된 상태이기 때문에 upper_bound를 통해 쉽게 구할 수 있다. 1. 구간에 맞지 않는 경우 2. 구간에 걸친 경우 3. 구간에 완전히 속하는 경우 위 세가지의 경우로 처리하여 반환되는 값들의 합을 출력하면 정답처리를 받을 수 있다. /* 21.01.25 BOJ : 13537 수열과 쿼리 1 (http..

[BOJ 11505(G1)리뷰] N개의 값이 1번 index부터 차례대로 주어진다. 그 후에 명령을 입력받는데 "1 a b"의 형태라면 a를 b라는 수로 바꿔야하고, "2 a b"의 형태라면 a번 index부터 b번 index까지의 곱을 출력해야 한다. 값을 update하는 작업이 있으므로 단순히 구간의 곱을 저장하는 것으로는 시간내에 해결 할 수 없다. 따라서 값을 update하고 구하는 과정을 O(logN)에 수행할 수 있는 세그먼트 트리 자료구조를 이용했다. 일반적으론 구간의 합을 세그먼트 트리 구조로 저장하지만, 이번 문제는 구간의 곱을 저장해주면 된다. 따라서 값에 영향을 주지 않도록 비어있는 노드는 1로 초기화 해주어야하며, 값을 update할때는 botoom-up방식으로 구현 하는 것이 깔끔..

[BOJ 2243(P5)리뷰] 세그먼트 트리를 응용하는 문제다. 사탕상자에서 사탕을 넣거나 뺄 수 있고, 동생에게 N번째로 맛있는 사탕을 줘야할 때도 있다. 사탕의 맛은 1부터 100만이다. 이걸 배열로 기록하여 값을 업데이트 한다면 시간복잡도O(N^2)으로 시간초가가 나게 된다. 따라서 업데이트를 O(logN)에 가능하게 하여 최종적으로 O(NlogN)으로 풀어야 정답처리를 받을 수 있다. 일반적으로 세그먼트 트리에는 구간의 합을 저장한다. 가장 리프노트에는 본래의 값이 들어있고, 리프노드에서 부모노드로 올라갈 수록 자식노드의 합들을 저장하며 루트노드까지 올라간다. 최종적으로 루트노드에는 전체범위의 합이 저장되어 있다. 이 문제는 이러한 구조를 갖는 세그먼트 트리를 응용하여 풀어야 하는 문제다. 사탕의..