Algorithm & Problem Solving/구간 합(Prefix Sum)
-
[백준 2208] 보석 줍기 (Python)Algorithm & Problem Solving/구간 합(Prefix Sum) 2021. 1. 4. 23:39
www.acmicpc.net/problem/2208 2208번: 보석 줍기 화영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1≤N≤100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 화영이는 가급적 많은 이득을 www.acmicpc.net 문제풀이 N, M, arr : 입력값 prefix_sum : 구간합 단순하면서도 어려운 구간 합(Prefix Sum) 문제였다. 머리로는 이해가 되는데, 설명하기가 굉장히 어려운 풀이이다.. 조금 더 풀이 해설 보완이 필요할 것 같다.. ㅠㅠ 1. arr 입력을 받으면서 구간 합을 구한다. 2. 인덱스 M - 1 부터 N 까지 최소 구간합을 구하고, 최소 구간합을 뺴주면서 최대 구간합을 구한다. - 인덱스..
-
[백준 13398] 연속합 2 (Python)Algorithm & Problem Solving/구간 합(Prefix Sum) 2020. 12. 27. 23:48
www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제풀이 N, arr : 입력값 dp : 연속합을 구하기 위한 누적합 - dp[0][i] : 특정 원소를 제거하지 않은 경우 - dp[1][i] : 특정 원소를 제거한 경우 dp를 이용한 누적 합 문제이다. N 제한이 100,000 이기에 O(N^2) 이 아닌 그보다 빠른 방식으로 해결해야 한다. 1. dp[0][0] 을 arr[0]으로 초기화 한다. - 최소 1개의 원소는 반드시 선택해야 하기 때문에 dp[0][..
-
[백준 11660] 구간 합 구하기 5 (Python)Algorithm & Problem Solving/구간 합(Prefix Sum) 2020. 12. 27. 15:20
www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제풀이 N, M : 입력값 board : 입력 배열(2차원 리스트) dp : 특정 좌표 (i, j) 까지의 누적 합 사실 이 문제는 DP 문제(?) 라고 봐도 무방할 것 같다. 특정 좌표 (i, j) 까지의 누적 합을 구한 다음 필요한 영역만 잘라서 출력하면 해결할 수 있다. 시간복잡도는 O(N^2 + M) 으로, 약 100만 정도이기 때문에 1초 안에 해결할 수 있..
-
[백준 11659] 구간 합 구하기 4 (Python)Algorithm & Problem Solving/구간 합(Prefix Sum) 2020. 12. 27. 15:10
www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000), 합을 구해야 하는 횟수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에 www.acmicpc.net 문제풀이 N, M : 입력값 arr : 입력 배열 sum_value : 누적 합 prefix_sum : 누적 합의 값들을 저장할 리스트 N 과 M 제한이 100,000이기에 O(NM)으로는 해결할 수 없다. 구간 합을 효율적으로 구하기 위한 누적 합(Prefix Sum)을 통해 O(N+M)으로 효율적으로 해결할 수 있다. 1. sum_value에 배열의 원소..
-
[백준 3020] 개똥벌레 (Python)Algorithm & Problem Solving/구간 합(Prefix Sum) 2020. 12. 27. 15:01
www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 문제풀이 N, H : 입력값(가로, 세로) top : 종유석 bottom : 석순 N 제한이 200,000 H 제한이 500,000 으로 단순하게 일일이 비교하는 O(NH) 방식으로는 절대 해결할 수 없다. (20만 * 50만 = 1000억 => 1초안에 불가능) 조금 더 효율적인 방식으로 해결해야 하는데, 종유석과 석순을 구분지어서 생각해 볼 수 있다. 종유석만 보았을 때, 그림에서 높이가 작아질수록(H => 0..