코딩테스트 주요 알고리즘 중 하나인 DP(동적 프로그래밍) 문제입니다. DP에 관한 개념학습을 위해 풀어보았습니다.

https://itstory1592.tistory.com/34 블로그를 참고하여 공부했습니다.

문제

https://www.acmicpc.net/problem/1003

[나의 풀이]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {

    // 동적 프로그래밍을 위해 0과 1이 등장하는 ArrayList 저장
    static ArrayList <Integer> zero = new ArrayList<Integer>(Arrays.asList(1,0,1));
    static ArrayList <Integer> one = new ArrayList<Integer>(Arrays.asList(0,1,1));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static void fibonacci(int num) throws IOException{
        
        int len = zero.size();
        
        // num = 3
        // len = 3
        if (num >= len) {

            // 이전에 저장된 0,1 등장 갯수를 더함
            for (int i=len; i<num+1;i++){
                zero.add(zero.get(i-1)+zero.get(i-2));
                one.add(one.get(i-1)+one.get(i-2));
            }
        }

        bw.write(zero.get(num) + " " + one.get(num)+"\n");
        bw.flush();

    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        int [] testCases = new int [T];

        for (int i=0; i<T; i++){
            testCases[i] = Integer.parseInt(br.readLine());
        }

        for (int i=0; i<T; i++){
            fibonacci(testCases[i]);
        }

    }
}

문제에서 다음과 같이

피보나치 수열 구현의 코드가 주어지고 이때 finbonacci(0), fibonacci(1)의 호출 횟수를 구해야 했습니다. 단순히 주어진 코드를 java로 살짝 변환시켜 정답처리를 받을 순 있었지만 동적 프로그래밍의 원리를 정확히 학습하기 위해 다른 풀이들을 찾아보았습니다.🐨🐨🐨

다른 코드들을 참고한 결과 해당 문제는 다이나밍 프로그래밍을 통해 finbonacci(0), fibonacci(1)의 호출 횟수를 출력하는데 의미가 있는 문제였습니다.

fibonacci(n)을 계산하기 위해서는 finbonacci(n-1), fibonacci(n-2)를 계산하게되고 이는 finbonacci(n-1), finbonacci(n-2)가 각각 finbonacci(0), finbonacci(1) 일 때를 카운팅하면 됩니다. 그 다음으로 입력값별로 카운팅 되는 finbonacci(0), finbonacci(1) 호출을 각각 zero,one 이라는 ArrayList에 저장하며 이미 구한 숫자는 다시 구하는 일이 없도록 하여 시간을 단축시키는 것이 핵심이였습니다.👨‍🌾👨‍🌾👨‍🌾

현재까지 알고리즘 문제풀 때는 스스로 코딩한 소스를 토대로 백준에서 정답처리 되면 넘어갔었습니다. 이번 문제를 통해 느낀점은 정답처리보다도 문제에서 요구하는 알고리즘 핵심 개념임을 알게 되었습니다. 다음부터는 아예 알고리즘 교재를 구매해서 먼저 풀어보고 문제에서 요구하는 핵심 내용을 다시 다져보는 방식으로 학습하겠습니다.

감사합니다.👨‍🚀👨‍🚀👨‍🚀