[백준] 1003 (피보나치 함수)

#1 알고리즘

#1-1

동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근

하향식 동적 프로그래밍을 구현해 풀었다.

 

#1-2

 

#1-3

 

#2 코드

#2-1 자바

import java.util.*;

public class Main {
    public static Map<Integer, Integer[]> map = new HashMap<>();
    
    public static void main(String[] args) {
        Integer[] seedData0 = {1, 0};
        Integer[] seedData1 = {0, 1};
        map.put(0, seedData0);
        map.put(1, seedData1);
        
        Scanner sc = new Scanner(System.in);
        String loopCountStr =  sc.nextLine().trim();
        int loopCount = Integer.parseInt(loopCountStr);
        
        for(int i = 0; i < loopCount; i++) {
            String testCaseStr =  sc.nextLine().trim();
            int testCase = Integer.parseInt(testCaseStr);
         
            Integer[] result = fibonacci(testCase);
            System.out.println(Integer.toString(result[0]) + " " + Integer.toString(result[1]));
        }   
    }
    
    public static Integer[] fibonacci(int n) {
        Integer[] result = {0, 0};
        
        if(map.containsKey(n)) { // 캐싱(메모) 되어있는지 확인
            Integer[] cachedData = map.get(n);
            result[0] += cachedData[0];
            result[1] += cachedData[1];
           
        } else {
            result[0] += fibonacci(n-1)[0] + fibonacci(n-2)[0];
            result[1] += fibonacci(n-1)[1] + fibonacci(n-2)[1];
            map.put(n, result);
        }
        
        return result;
    }
}

 

#2-2 코틀린

val map = HashMap<Int, Array<Int>>()

fun main() {
    val seedData0 : Array<Int> = arrayOf(1, 0)
    val seedData1 : Array<Int> = arrayOf(0, 1)
    map.put(0, seedData0)
    map.put(1, seedData1)
    
    val loopCount = readLine()!!.trim().toInt()
    
    for(i : Int in 1..loopCount) {
        val testCase = readLine()!!.trim().toInt()
        
        val result = fibonacci(testCase)
        println(result[0].toString() + " " + result[1].toString())
    }
}

fun fibonacci(n : Int) : Array<Int> {
    var result : Array<Int> = arrayOf(0, 0)
    
    if(map.containsKey(n)) { // 캐싱(메모) 되어있는지 확인
        val cachedData = map.get(n)
        result[0] += cachedData!![0]
        result[1] += cachedData!![1]
        
    } else {
        result[0] += fibonacci(n-1)[0] + fibonacci(n-2)[0]
        result[1] += fibonacci(n-1)[1] + fibonacci(n-2)[1]
        map.put(n, result)
    }
    
    return result
}