[Algorithm] 99클럽 코테 스터디 21일차 TIL BOJ 1003

문제

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

풀이

문제 분석

• 피보나치 수열을 생각해보면 이전 수를 이용하기 때문에 각 숫자별로 f(0)과 f(1)의 개수를 미리 계산하여 저장하면 되겠다고 생각했다
• 이에 따라 Fibo라는 클래스를 만들어 fibo(0)과 fibo(1)의 개수를 매번 저장해둘 수 있도록했다
• 또한 fibos 리스트의 index를 주어진 숫자로 사용하여 계산했다

코드

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

class Fibo {
    private int zero;
    private int one;

    public Fibo(int zero, int one) {
        this.zero = zero;
        this.one = one;
    }

    public int getZero() {
        return zero;
    }

    public int getOne() {
        return one;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Fibo[] fibos = new Fibo[41];
        fibos[0] = new Fibo(1, 0);
        fibos[1] = new Fibo(0, 1);

        for(int i=2; i<=40; i++) {
            int zero = fibos[i-2].getZero() + fibos[i-1].getZero();
            int one = fibos[i-2].getOne() + fibos[i-1].getOne();
            fibos[i] = new Fibo(zero, one);
        }

        int N = Integer.parseInt(st.nextToken());

        for(int i = 0; i<N ; i++) {
            st = new StringTokenizer(br.readLine());
            int number = Integer.parseInt(st.nextToken());
            bw.write(fibos[number].getZero() + " " +fibos[number].getOne()+"\n");
        }

        bw.flush();
        bw.close();
    }
}

TIL

• 다이나믹 프로그래밍에 대해 정리해보려 한다

Dynamic Programming

• 하나의 문제는 단 한 번만 풀도록 하는 기법
• 알고리즘이 아니라 기법인 이유는 해당 메모이제이션 방식이 여러 다른 알고리즘과 함께 엮여 다양한 형태로 쓰이기 때문이다

Divide and Conquer (분할 정복)

• 피보나치 수열은 다음 사진과 같이 특정한 숫자를 구하기 위해 그 앞에 있는 숫자와 두 칸 앞에 있는 숫자의 합을 구하는 방식이다

• 사진 상의로 f(5)를 구해야한다는 상황에서, f(4)와 f(3)이 필요한데, f(4)를 구하기 위해서는 또 f(3)과 f(2)가 필요하다
• 이미 해결한 문제를 다시 반복적으로 해결하여 비효율적이라는 것을 확인할 수 있다
• 이러한 중복된 계산을 해결하기 위한 방법이 다이나믹 프로그래밍이다

조건

• 큰 문제를 작은 문제로 나눌 수 있어야 한다
• 작은 문제에서 구한 답을 그것을 포함하는 큰 문제에서도 동일하다

크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어 해결한 뒤에 처리하여 나중에 전체의 답을 구하는 방식이다

• 이 과정에서 메모이제이션이 사용되고, 계산된 결과는 배열에 저장함으로써 나중에 동일한 계산을 해야 할 때 저장된 값을 반환한다

목적

메모리를 사용해서 중복 연산을 줄이고, 중복 연산을 줄여서 수행속도를 개선한다

• 메모리를 사용한다 -> 배열 혹은 자료 구조를 만든다
• 중복 연산을 줄인다 -> 연산한 결과를 배열에 담는다
• 기억하기 알고리즘