오늘의 키워드
•
메모이제이션
•
누적합
•
시간 복잡도 개선
문제 파악 및 풀이
이 문제는 1년 전 파이썬을 사용해 풀었던 경험이 있어 반가운 문제였다. 처음에는 이중 for문을 이용한 간단한 방식으로 풀이했으나, 예전에 비해 시간이 매우 오래 걸렸다. 그래서 메모이제이션(누적합)을 이용한 효율적인 풀이를 추가하여 O(N)의 시간 복잡도로 단축할 수 있었다.
첫 번째 풀이 (이중 for문 - 비효율적)
import java.util.Scanner;
class Main {
public static final int MAX_N = 100000;
public static int n, k;
public static int ans = Integer.MIN_VALUE;
public static int[] arr = new int[MAX_N];
public static int[] memo;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
memo = new int[n - k + 1];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
for (int i = 0; i < n - k + 1; i++) {
for (int j = 0; j < k; j++) {
memo[i] += arr[i + j];
}
ans = Math.max(ans, memo[i]);
}
System.out.println(ans);
}
}
Java
복사
두 번째 풀이 (메모이제이션 - 효율적)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main {
public static final int MAX_N = 100000;
public static int n, k;
public static int ans = Integer.MIN_VALUE;
public static int[] arr = new int[MAX_N];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int num = 0;
for (int i = 0; i < k; i++) {
num += arr[i];
}
ans = num;
for (int i = k; i < n; i++) {
num -= arr[i - k];
num += arr[i];
ans = Math.max(ans, num);
}
System.out.println(ans);
}
}
Java
복사
추가 풀이 (1년 전 파이썬 풀이 - 가장 효율적)
1년 전 파이썬 풀이가 가장 직관적이고 효율적인 것 같아 추가했다.
import sys
input = sys.stdin.readline
def dp():
rst.append(sum(lst[:K]))
start = 0
end = K
while end < N:
rst.append(rst[-1] - lst[start] + lst[end])
start += 1
end += 1
return max(rst)
N, K = map(int, input().split())
lst = list(map(int, input().split()))
rst = []
print(dp())
Python
복사
오늘의 회고
어려웠던 점
•
처음에 단순 반복문으로 구현하니 성능이 좋지 않았다.
개선점
•
메모이제이션(누적합)을 이용하여 시간 복잡도를 개선하는 연습을 해야겠다.
•
파이썬과 자바의 코드 표현 방식이 다름을 확인할 수 있어서 재밌었다.ㅋㅋ