99클럽 코테 스터디 5일차 TIL - 수열 (백준 2559번)

오늘의 학습 키워드

- 슬라이딩 윈도우

- 연속 부분합

- 시간복잡도 개선

---

공부한 내용 정리

오늘은 주어진 온도 수열에서 연속된 K일 동안의 합이 가장 큰 값을 구하는 문제를 풀었다.

처음에는 이중 for문을 사용하여 모든 구간의 합을 계산했고, 이는 시간복잡도가 O(N*K)로 비효율적이었다.

하지만 이후 슬라이딩 윈도우 기법을 통해 O(N)으로 줄일 수 있다는 걸 알게 되었고, 이를 직접 코드에 적용해 보았다.

---

소스코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        // 온도 수열 입력
        int[] temperature = new int[N];
        for (int i = 0; i < N; i++) {
            temperature[i] = sc.nextInt();
        }
        int max = Integer.MIN_VALUE;
        // 연속적인 K일의 온도의 합이 가장 큰 값을 구하기
        // 슬라이딩 윈도우
        for (int i = 0; i <= N - K; i++) {
            int sum = 0;
            // 연속적인 K일의 온도의 합 구하기
            for (int j = 0; j < K; j++) {
                sum += temperature[i + j];
            }
            // 최대값 갱신
            if (sum > max) {
                max = sum;
            }
        }
        System.out.println(max);
    }
}

---

오늘의 회구

• 어떤 문제가 있었고, 나는 어떤 시도를 했는지

처음에는 단순하게 모든 연속 K일 구간에 대해 합을 구하는 방식으로 접근했다.

이 방식은 간단하지만 비효율적이었다.

 

• 어떻게 해결했는지

슬라이딩 윈도우 기법.

처음 구간의 합을 구한 뒤, 윈도우를 오른쪽으로 한 칸 이동하면서 빠지는 값과 들어오는 값을 조정해 나가는 방식으로 수정.

 

• 무엇을 새롭게 알았는지

반복해서 구간 합을 구할 필요 없이 이전 합에서 한 값만 빼고 새 값을 더하면 효율적인 연산이 가능하다는 점.

 

• 내일 학습할 것은 무엇인지

슬라이딩 윈도우의 실전 적용 연습을 더 해보고, 투포인터와의 차이점 및 활용법도 정리해볼 예정이다.

---