devbelly

문제 www.acmicpc.net/problem/15678 알고리즘 세그먼트 트리 + DP 풀이 $N$개의 발판이 주어지고 각 발판마다 점수가 있을 때, 얻을 수 있는 점수의 최댓값을 묻고 있습니다. 흔한 다이나믹프로그래밍 주제입니다. $dp[i]$를 $i$번째 발판까지 밟았을 때, 얻을 수 있는 최댓값이라고 하겠습니다. 각 i번째 발판마다 자신의 최댓값을 구하기 위해서는 $dp[i-D]$ ~ $dp[i-1]$ 사이의 최댓값을 얻으면 $dp[i]$를 구할 수 있습니다. 요구하는 시간 복잡도는 $O(N^2)$ 이므로 시간초과입니다. 눈에 띠는 것은 구간값 중 최대값을 요구하고 있습니다. 반복문을 통해 선형시간에 해결하는 것 말고도 세그먼트 트리를 활용하면 구간값을 $O(logN)$에 구할 수 있습니다. 입..

문제 www.acmicpc.net/problem/2517 알고리즘 세그먼트 트리, 좌표압축 풀이 현재 달리는 사람의 순서가 주어질 때, 자신의 최대등수를 출력하는 문제입니다. 자신보다 능력이 뛰어난 사람이 앞에 달리고 있으면 앞지를 수 없지만, 자신보다 능력이 낮은 사람이 앞에 달리고 있으면 앞지를 수도 있습니다. 쿼리는 달리는 순서대로 세그먼트트리를 업데이트 하며 그 순간 자신보다 앞에 있는 사람의 수를 묻고 있습니다. 누적합으로 자신앞에 있는 사람의 수를 알 수 있으므로 펜윅트리를 활용합시다. 유사한 문제가 많지만 그 문제들과 다른점은 주어지는 능력값이 굉장히 큰 수 라는 것입니다. 이는 좌표압축을 통해 해결가능합니다. 각 쿼리당 요구하는 시간복잡도는 $O(logN)$ 이므로 시간복잡도는 $O(Nlo..

문제 www.acmicpc.net/problem/1321 알고리즘 세그먼트트리 풀이 부대원의 숫자가 계속해서 바뀔 때, 몇번째 병사가 어디 부대에 들어있는지 묻는 문제입니다. 누적배열을 만들어 나이브하게 해결해봅시다. 부대원이 변경될때마다 누적배열을 변경하는데에 최대 $O(N)$의 복잡도를 요구하게됩니다. 업데이트를 더 빠르게 할 수 있는 세그먼트 트리를 요구합니다. 세그먼트 트리를 사용하면 업데이트와 쿼리가 $O(logN)$에 해결가능합니다. 남은 문제는 누적배열에서 몇번째에 해당하는$K$가 어디에 속한지 찾는 문제입니다. 누적배열은 오름차순의 형태를 띠고 있고 이는 이분탐색을 통해 접근할 수 있다는 의미입니다. 펜윅트리에서 쿼리는 누적합을 리턴하므로 펜윅트리 + 이분탐색을 통해 문제를 해결할 수 있습..

문제 www.acmicpc.net/problem/10999 알고리즘 lazy propagation 풀이 구간 갱신, 구간 쿼리를 요구하는 문제입니다. 일반적인 점 갱신, 구간 쿼리를 이용하는 세그먼트 트리를 활용한다면 구간 갱신을 처리할 때, 구간의 길이에 비례한 시간복잡도를 요구합니다. 하지만 lazy propagation을 활용하면 구간 갱신또한 $O(logN)$에 훌륭하게 처리가능합니다. 자세한 설명은 다른 좋은 글들이 많으니 참고 바랍니다. 구현 포인트만 짚고 마치겠습니다. 1. $lazy$를 업데이트 하는 것은 쿼리와 업데이트 둘 다 해당이 된다. 2. 조상노드에서 자식노드로 재귀적으로 $lazy$를 업데이트 해야한다. 3. 자식노드의 $lazy$는 조상노드를 고려해야한다. 4. 세그먼트 트리를..

문제 www.acmicpc.net/problem/5419 알고리즘 스위핑, 세그먼트 트리 풀이 북서풍으로 인해 동쪽과 남쪽에 있는 섬으로만 항해가 가능할 때, 가능한 쌍의 수를 묻고 있습니다. 이전에도 소개했던 문제들 중 inversion count 문제가 있습니다. 그 문제도 inversion이 발생하는 쌍을 count 하는 문제입니다. 브루트 포스로 $O(N^2)$에 해결 가능하지만 세그먼트 트리를 활용하면 $O(NlogN)$에 해결 가능합니다. 이 문제또한 가능한 쌍을 묻고 있으며, 지금까지 지나온 섬들을 세그먼트 트리에 업데이트를 하면 보고 있는 섬마다 $O(logN)$에 지나온 섬의 개수를 알 수 있습니다. 섬을 정렬한 후 순차적으로 쿼리와 업데이트를 진행합니다. x좌표가 같을 때는 y좌표가 큰..

문제 https://www.acmicpc.net/problem/3006 알고리즘 세그먼트트리 풀이 터보소트라는 방법으로 소팅을 할 때, 필요로 하는 교환 횟수를 묻고 있습니다. 일반적인 inversion counting문제는 작은 수부터 inversion들을 세어나가는 문제입니다. 하지만 이 문제에서는 첫 번째로 작은 수, 첫번째로 큰 수, 두 번째로 작은 수, 두번째로 큰 수 와 같이 inversion을 세어나갑니다. 다른 여러 문제들에서도 설명드렸지만, 일반적인 방법으로는 $O(N^2)$의 시간 복잡도가 필요하지만 세그먼트 트리를 이용하게 되면 자신보다 앞에 있는 수, 자신보다 뒤에 있는 수들을 한 임의의 수당 $O(logN)$의 시간 복잡도로 해결 가능합니다. 펜윅트리에는 쿼리를 진행해야 할 인덱스..

문제 https://www.acmicpc.net/problem/1615 알고리즘 세그먼트 트리 풀이 간선들이 주어질 때, 교차점의 개수를 묻고 있습니다. 교차 조건은 두 개의 에지를 (A1, B1), (A2, B2)라 한다면 A1 B2 또는 A1> A2, B1 M; while(M--) { cin >> a >> b; edge.emplace_back(a, b); } sort(edge.begin(), edge.end()); for (auto [A, B] : edge) { ans += query(N) - query(B); update(B,1); } cout

문제 https://www.acmicpc.net/problem/1777 알고리즘 세그먼트 트리 풀이 Inversion counting 문제입니다. 각 숫자의 inversion의 개수가 주어졌을 때, 원래 순열을 구하는 문제입니다. 예제 입력에서 주어지는 inversion의 개수를 풀어서 설명하자면, 나보다 작은 숫자가 뒤에 몇 개나 있느냐를 의미합니다. 순열의 총 크기를 안다면, 나보다 작은 숫자가 앞에 몇 개가 있는지 또한 구할 수 있습니다. 이는 $k$번째가 어디에 위치한 지를 묻는 쿼리와 동등합니다. 이때 여러전략을 선택할 수 있지만, 숫자를 올바른 곳에 배치했다면 해당 인덱스를 제외해야 하므로 삭제 연산 또한 가능한 펜윅트리를 사용했습니다. 시간 복잡도는 $O(NlogN*logN)$입니다. 코드 ..