연속부분합 찾기
- sliding window 방식을 이용한 연속부분합
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23const slidingWindow = (arr) => {
let N = arr.length;
let answer = Number.MIN_SAFE_INTEGER;
/* 부분합을 구할 배열의 길이를 늘려가며 해답을 찾기
최소값은 1이고 최대값은 배열의 길이만큼 */
for (let len = 1; len <= N; len++) {
let sum = 0
/* scanf로 값을 불러오는 C++ 코드와는 달리
배열을 받아 처리하는 함수로 작성하였기 때문에
i = 0부터 시작해서 i+1값이 length값보다 커지면
앞부분을 잘라내도록 변경 */
for (let i = 0; i < N; i++) {
// i값이 len 보다 길어지면 현재 벗어난 i-len 인덱스 부분의 값을 빼줌
if (i+1 > len) sum -= arr[i-len]
// 슬라이딩하여 추가된 값을 더해줌
sum += arr[i]
/* i+1 >= len, 즉, 해당 부분 배열의 길이가 같고
부분합이 기존의 answer보다 크다면 갱신 */
if (i+1 >= len && answer < sum) answer = sum;
}
}
return answer
} - prefix sum 방식으로 찾기
→ prefix를 사용하기 위해서는 0번째 원소(누산용 초기값 0)가 필요하다
→ 처음에 배열을 그대로 썼을 때 arr의 N번째값이 없어서 preSum의 마지막 값으로 NaN값이 출력됨1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17const prefixSum = arr => {
let answer = Number.MIN_SAFE_INTEGER;
arr = [0, ...arr];
let preSum = Array.from({length: arr.length + 1}, () => 0)
// prefix를 사용하기 위해서는 0번째 원소(누산용 초기값 0)가 필요하다
for (let i = 1; i <= N; ++i) {
preSum[i] = preSum[i-1] + arr[i]
}
// 처음에 배열을 그대로 썼을 때 arr의 N번째값이 없어서 preSum의 마지막 값으로 NaN값이 출력됨
for (let length = 1; length <= N; length++) {
for (let i = length; i <= N; i++) {
if (preSum[i] - preSum[i-length] > answer)
answer = preSum[i] - preSum[i - length]
}
}
return answer;
} - dynamic programming 방식으로 찾기
- D[i]를 i번째 수를 마지막으로 하는 연속 부분합의 최대값으로 정의
- 연속 부분합이므로 A[i]를 새로운 부분합의 시작으로 하지 않는 한 D[i]값은 D[i-1]을 이용할 수 밖에 없다
- D[i-1] <= 0이라면 D[i-1]값을 고려할 필요가 없다
- D[i] = max(A[i], D[i-1] + A[i])
1
2
3
4
5
6
7
8
9
10
11
12
13const dynamicSum = arr => {
let answer = Number.MIN_SAFE_INTEGER;
let N = arr.length
arr = [0, ...arr] // 마찬가지로 0번째에 누산용 0값을 입력
D = Array.from({length: N}, () => 0)
for (let i = 1; i <= N; i++) {
// D[i-1] 값이 음수라면 더해도 최대값이 될 수 없다
D[i - 1] > 0 ? D[i] = D[i - 1] + arr[i] : D[i] = arr[i]
if (D[i] > answer) answer = D[i]
}
return answer
}
- 메모이제이션으로 배열을 사용하지 않고 해결하기(Kadane’s Algorithm)
1
2
3
4
5
6
7
8
9
10
11
12const dynamicSum = arr => {
let answer = Number.MIN_SAFE_INTEGER;
let N = arr.length
arr = [0, ...arr]
let sum = 0;
for (let i = 1; i <= N; i++) {
// D[i-1] 값이 음수라면 더해도 최대값이 될 수 없다
sum > 0 ? sum += arr[i] : sum = arr[i]
if (sum > answer) answer = sum
}
return answer
} - 배우면서 느꼈던 것
→ 상황에 따라 배열의 인덱스 값을 고려하여 코딩해야 한다는 점을 기억하자
→ 0을 맨 앞에 추가했다면 1번째 원소부터 고려해야 한다
회전 초밥 문제
- 손님이 k개의 접시를 연속해서 먹을 경우 할인된 가격으로 제공
- 위 행사에 참여하면 초밥을 선택할 수 있는 쿠폰을 발행
- 회전 초밥 음식점의 벨트 상태 N, 메뉴에 있는 초밥의 가짓수 d, 연속해서 먹는 접시의 개수 k, 쿠폰 번호 c 가 주어짐
- 이 때, 손님이 먹을 수 있는 최대 가짓수를 구하는 문제
1 | // 접시의 수(N), 초밥 가짓수(d), 연속해서 먹는 접시 수(k), 쿠폰번호(c) |