Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
반응형
문제
https://www.acmicpc.net/problem/2042
2042번: 구간 합 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
풀이
solved.ac 난이도: Gold 1
부분합을 구하는 문제이지만 단순한 부분합 구현으로는 중간에 배열의 값이 바뀌면 다시 연속합을 구해줘야 하는 문제가 생긴다.
배열의 길이가 n이라면 중간에 바뀐 값으로 다시 연속합을 구하면 O(n)의 시간 복잡도가 소요된다.
해당 문제에서는 중간에 배열의 값 변경이 빈번히 일어나, 단순한 부분합 알고리즘으로 해결할 수 없는 입력 크기가 주어진다.
이런 경우 부분 합을 구하기 위한 자료구조인 세그먼트 트리를 이용한다.
세그먼트 트리에 대해서는 본 문제의 풀이로 세그먼트 트리 소개한 백준님의 게시글을 참고하자.
세그먼트 트리 (Segment Tree) - Baekjoon Online Judge
너무 완벽한 글이라 코드를 배끼다 싶이 푼 본인의 풀이는 생략합니다...
코드
반응형
'알고리즘 공부 > 백준' 카테고리의 다른 글
| [백준] No.11658 - 구간 합 구하기 3 (C++, 펜윅 트리) (0) | 2021.01.24 |
|---|---|
| [백준] No.2357 - 최솟값과 최댓값 (C++, 세그먼트 트리) (2) | 2021.01.23 |
| [백준] No.3020 - 개똥벌래 (C++, 부분합) (0) | 2021.01.20 |
| [백준] No.2098 - 외판원 순회 (C++, 비트마스크) (2) | 2021.01.19 |
| [백준] No.1102 - 발전소 (C++, 비트마스크) (0) | 2021.01.18 |
댓글