문제 설명

N개의 층이 주어진다. 각 층마다 3개의 숫자가 나열되어있다. 각 숫자는 0~9 사이다.
이때, 꼭대기 층부터 시작해서 아래층까지 내려올건데, 아래층으로 내려갈때는 현재 위치의 바로 아래 숫자 혹은 그와 이웃한 숫자들로만 이동가능하다. 아래 사진을 참고하자.

이런 방식으로 내려갈때의 모든 숫자의 합의 최댓값과 최솟값을 구해라.

문제 접근 1차 풀이

우선, 아래층부터 역으로 올라가는걸 생각했을때 중복이 너무 많이 발생해서 DP라는건 바로 알았으나 최대 최소 두 번을 구해야했다. 솔직히 숫자가 10만 밖에 안되기 때문에 시간제한이 1초여도 그냥 DP 두번하면 된다고 생각하고 구했다.

하지만, 시간이 좀 오래걸린것 같아서 다른 사람들의 풀이시간을 봤는데 다른 사람들 풀이를 보니 나의 절반 정도였다. 이게 무슨일인가 하고 찾아봤다.
알고보니 이 문제의 조건의 핵심은 시간이 아니라 공간복잡도였다. 다시 보니 4MB가 한계였는데 내가 통과한 이유는 이 문제가 자바나 코틀린에서 공간 복잡도를 256MB까지 허락해주기 때문이다.

개인적으로 이 문제에서 왜 자바에 공간을 훨씬 더 많이 줬는지가 궁금해서 지인들에게 물어본 결과, JVM이 메모리에 올라와서로 결론났다. 그 외에도 자바는 기본적으로 메모리가 널널한 문제에서도 다음과 같은 특혜를 받고 있다. 사실 내가 1차적으로 푼 방법은 자바였기에 통과되는 것이였다. 언어에 종속돼서 문제를 푸는 것은 바람직하지 않다고 생각하므로 이 문제를 정석으로 푸는 방법을 알기 위해 아래와 같이 슬라이딩 윈도우 기법을 공부해봤다.

슬라이딩 윈도우

아, 슬라이딩 윈도우 기법을 써야한다고 한다. 그런데, 이 용어를 운영체제랑 네트워크 수업 때 들었던 기억은 어렴풋 나지만 정확히 기억이 안나서 찾아봤다.
https://ji-musclecode.tistory.com/37
위 블로그에서 너무 잘 설명해줬는데, 말이 생소한거지 투포인터 알고리즘의 고정크기 편이라고 생각하면 된다.
그러다면 위 문제에서 어떻게 쓸 수 있는거고, 이걸로 어떻게 메모리 공간을 절약한다는걸까?

https://www.youtube.com/watch?v=ySECi-s5fQY
이 문제 풀이영상에서 온라인 알고리즘 기법이라는 용어와 슬라이딩 윈도우 기법을 연관지어 설명해줬다.
온라인 알고리즘이란 일반적으로 들어오는 데이터들을 저장안하고 쭉 지나가며 입력받으면서 그때 그때 연산처리하는 것을 표현하는 용어라고 한다. 그리고 슬라이딩 윈도우가 바로 그 기법 중 하나라고. 그냥 입력받으면서 바로 바로 필요한 구간만 연산처리하는 것.

내가 너무 전형적인 DP 재귀 풀이법으로 풀은 것 같다. 이런식으로도 DP를 풀 수 있다는 걸 처음 알았다.
이 문제를 다시 잘생각해보면 꼭대기 층에서 1층으로 내려가야 하는데, 최댓값을 찾아가는 과정에서 항상 이전 층의 최댓값들과 연루된 점화식이 나온다. 즉, 이 문제에서 윈도우는 현재층과 그 이전층(최댓값으로 갱신된)이다. 따라서 두 층이므로 2*3의 6개의 정수만 윈도우로 기억하고 층을 계속 쭉쭉 내려가면서 최댓값을 찾아가면 된다.
최솟값도 이와 같은 방식으로 구하면 된다.
코드로 봐보기 전에, 우선 내가 기존에 구한 풀이의 일부는 이렇다.

    static int maxDFS(int curLayer, int curIndex) {
        if (maxDp[curLayer][curIndex] != -1) return maxDp[curLayer][curIndex];

        int curMax = 0;
        if (curIndex == 1) {
            curMax = Math.max(maxDFS(curLayer - 1, 1), maxDFS(curLayer - 1, 2));
        } else if (curIndex == 2) {
            curMax = Math.max(maxDFS(curLayer - 1, 1), maxDFS(curLayer - 1, 2));
            curMax = Math.max(curMax, maxDFS(curLayer - 1, 3));
        } else {
            curMax = Math.max(maxDFS(curLayer - 1, 2), maxDFS(curLayer - 1, 3));
        }
        maxDp[curLayer][curIndex] = curMax + stairs[curLayer].get(curIndex);
        return maxDp[curLayer][curIndex];
    }

    static int minDFS(int curLayer, int curIndex) {
        if (minDp[curLayer][curIndex] != -1) return minDp[curLayer][curIndex];

        int curMin;
        if (curIndex == 1) {
            curMin = Math.min(minDFS(curLayer - 1, 1), minDFS(curLayer - 1, 2));
        } else if (curIndex == 2) {
            curMin = Math.min(minDFS(curLayer - 1, 1), minDFS(curLayer - 1, 2));
            curMin = Math.min(curMin, minDFS(curLayer - 1, 3));
        } else {
            curMin = Math.min(minDFS(curLayer - 1, 2), minDFS(curLayer - 1, 3));
        }
        minDp[curLayer][curIndex] = curMin + stairs[curLayer].get(curIndex);
        return minDp[curLayer][curIndex];
    }

그러다면, 슬라이딩 윈도우 기법을 적용한 DP 풀이는 어떨까?

import java.util.*;
import java.io.*;

public class Main {
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        // 윈도우 선언
        int[] maxPreviousLayer = new int[3];
        int[] minPreviousLayer = new int[3];
        int[] curMaxLayer = new int[3];
        int[] curMinLayer = new int[3];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] input = new int[3];
            input[0] = Integer.parseInt(st.nextToken());
            input[1] = Integer.parseInt(st.nextToken());
            input[2] = Integer.parseInt(st.nextToken());

            if (i == 0) {
                maxPreviousLayer = input.clone();
                minPreviousLayer = input.clone();
                curMaxLayer = input.clone();
                curMinLayer = input.clone();
            } else {
                curMaxLayer[0] = Math.max(maxPreviousLayer[0], maxPreviousLayer[1]) + input[0];
                curMaxLayer[2] = Math.max(maxPreviousLayer[1], maxPreviousLayer[2]) + input[2];
                int curMax = Math.max(maxPreviousLayer[0], maxPreviousLayer[1]);
                curMax = Math.max(curMax, maxPreviousLayer[2]);
                curMaxLayer[1] = curMax + input[1];
                maxPreviousLayer = curMaxLayer.clone();

                curMinLayer[0] = Math.min(minPreviousLayer[0], minPreviousLayer[1]) + input[0];
                curMinLayer[2] = Math.min(minPreviousLayer[1], minPreviousLayer[2]) + input[2];
                int curMin = Math.min(minPreviousLayer[0], minPreviousLayer[1]);
                curMin = Math.min(curMin, minPreviousLayer[2]);
                curMinLayer[1] = curMin + input[1];
                minPreviousLayer = curMinLayer.clone();
            }
        }
        int max = Math.max(maxPreviousLayer[0], maxPreviousLayer[1]);
        max = Math.max(max, maxPreviousLayer[2]);
        int min = Math.min(minPreviousLayer[0], minPreviousLayer[1]);
        min = Math.min(min, minPreviousLayer[2]);
        System.out.println(max + " " + min);
    }
}

시간이 확 줄었고, 메모리 공간도 덜 쓰는 것을 확인할 수 있다.

느낀점
아, DP 를 구할때, 이전층과 현재층의 관계로 이루어지는 경우같이 윈도우가 적용이 가능하다면 슬라이딩 윈도우 기법도 고려해보자. 시간과 메모리 모두 이득이다.


그 외에도 이 문제를 풀면서 자바의 clone에 대해 다시 알아볼 수 있었다. 코틀린에서는 복사하려면 copy나 toList()를 쓰다보니 잊어버린 것 같다.
배열 내 최댓 최솟값을 구하는 경우는 Arrays.stream(numbers).max().getAsInt(); 를 써도 되지만 코틀린이랑 매일 반복하면 쓰는 내가 기억할 자신이 없어서 그냥 for문과 Math.max를 같이 쓰는 걸로 타협봐야겠다.
그 외에도 이 문제를 처음 풀때 자꾸 ArrayList인데 .get(인덱스) 로 접근안하고 [인덱스] 로 접근하려고 실수했다. 이런것만 주의하자.

추가 수정

위 글의 코드에서 메모리를 좀 더 줄이는 방법으로 동기인 찬x씨가 input변수 선언을 for문 밖으로 빼자고 제안했다.

import java.util.*;
import java.io.*;

public class Main {
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        // 윈도우 선언
        int[] maxPreviousLayer = new int[3];
        int[] minPreviousLayer = new int[3];
        int[] curMaxLayer = new int[3];
        int[] curMinLayer = new int[3];
        int[] input = new int[3]; // 이 녀석을 밖으로 뺐다.
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            input[0] = Integer.parseInt(st.nextToken());
            input[1] = Integer.parseInt(st.nextToken());
            input[2] = Integer.parseInt(st.nextToken());

            if (i == 0) {
                maxPreviousLayer = input.clone();
                minPreviousLayer = input.clone();
                curMaxLayer = input.clone();
                curMinLayer = input.clone();
            } else {
                curMaxLayer[0] = Math.max(maxPreviousLayer[0], maxPreviousLayer[1]) + input[0];
                curMaxLayer[2] = Math.max(maxPreviousLayer[1], maxPreviousLayer[2]) + input[2];
                int curMax = Math.max(maxPreviousLayer[0], maxPreviousLayer[1]);
                curMax = Math.max(curMax, maxPreviousLayer[2]);
                curMaxLayer[1] = curMax + input[1];
                maxPreviousLayer = curMaxLayer.clone();

                curMinLayer[0] = Math.min(minPreviousLayer[0], minPreviousLayer[1]) + input[0];
                curMinLayer[2] = Math.min(minPreviousLayer[1], minPreviousLayer[2]) + input[2];
                int curMin = Math.min(minPreviousLayer[0], minPreviousLayer[1]);
                curMin = Math.min(curMin, minPreviousLayer[2]);
                curMinLayer[1] = curMin + input[1];
                minPreviousLayer = curMinLayer.clone();
            }
        }
        int max = Math.max(maxPreviousLayer[0], maxPreviousLayer[1]);
        max = Math.max(max, maxPreviousLayer[2]);
        int min = Math.min(minPreviousLayer[0], minPreviousLayer[1]);
        min = Math.min(min, minPreviousLayer[2]);
        System.out.println(max + " " + min);
    }
}

결과적으로 메모리 사용량이 꽤나 줄어들었다.
이유를 생각해보면, GC가 수거를 바로바로 해가는 것이 아니기 때문에 input객체를 여러번 생성한게 문제였던듯 싶다.
또한, 이번 문제를 풀면서 앞으로는 메모리 공간 제약을 잘 보고, 함수 콜 스택이나 메타 정보들도 고려해서 풀어야 한다는걸 깨달았다.