계단오르기

코드

//계단을 오를 땐 한 번에 1개, 2개씩 오를 수 있다.

public class 계단오르기 {
	static int[] dy;
	static int[] memo;
	
	static int cnt = 0;
	
	public static void main(String[] args) {
		int goal = 10; //10계단까지 가는 방법
		dy = new int[goal+1];
		memo = new int[goal+1];
		
		System.out.println("answer = " +dy(goal));
		System.out.println(cnt);
		cnt=0;
		System.out.println("answer = "+noDy(goal));
		System.out.println(cnt);
		cnt=0;
		System.out.println("answer = "+noDyMemo(goal));
		System.out.println(cnt);
		
	}

	private static int dy(int goal) {
		dy[1] = 1;
		dy[2] = 2;
		for(int i=3;i<=goal;i++,cnt++) {
			dy[i] = dy[i-1]+dy[i-2];
		}
		return dy[goal];
	}
	
	static int noDy(int goal) {
		cnt++;
		if(goal==1) return 1;
		else if (goal==2) return 2;
		else return noDy(goal-1)+noDy(goal-2);
	}
	
	static int noDyMemo(int goal) {
		cnt++;
		if(goal==1) return 1;
		else if (goal==2) return 2;
		else if(memo[goal]>0) return memo[goal];
		else return memo[goal]=noDyMemo(goal-1)+noDyMemo(goal-2);
	}
}

---

결과

answer = 89
8
answer = 89
109
answer = 89
17

---

큰 문제의 본질을 그대로 유지한 상태로 작게 축소하여 계산해 이를 이용해 큰 문제를 해결하는 방법

 

동적 계획법으로 풀었을 때는 8번 반복(1,2는 수동으로 입력했음) 

 

그냥 큰 문제로 바로 풀었을 경우 109번의 반복(재귀)

 

큰 문제를 메모이제이션으로 풀었을 경우 17번의 반복(재귀)

 

 

public class 계단오르기 {
	static int[] dy;
	static int[] memo;
	
	static int cnt = 0;
	
	public static void main(String[] args) {
		int goal = 50;
		dy = new int[goal+1];
		memo = new int[goal+1];
		
		long start = System.nanoTime();
		System.out.println("answer = " +dy(goal));
		System.out.println(cnt);
		System.out.println(System.nanoTime()-start);
		
		start = System.nanoTime();
		cnt=0;
		System.out.println("answer = "+noDy(goal));
		System.out.println(cnt);
		System.out.println(System.nanoTime()-start);
		
		start = System.nanoTime();
		cnt=0;
		System.out.println("answer = "+noDyMemo(goal));
		System.out.println(cnt);
		System.out.println(System.nanoTime()-start);
		
	}

	private static int dy(int goal) {
		dy[1] = 1;
		dy[2] = 2;
		for(int i=3;i<=goal;i++,cnt++) {
			dy[i] = dy[i-1]+dy[i-2];
		}
		return dy[goal];
	}
	
	static int noDy(int goal) {
		cnt++;
		if(goal==1) return 1;
		else if (goal==2) return 2;
		else return noDy(goal-1)+noDy(goal-2);
	}
	
	static int noDyMemo(int goal) {
		cnt++;
		if(goal==1) return 1;
		else if (goal==2) return 2;
		else if(memo[goal]>0) return memo[goal];
		else return memo[goal]=noDyMemo(goal-1)+noDyMemo(goal-2);
	}
}

answer = -1109825406
48
648700
answer = -1109825406
-597265727
40278105300
answer = -1109825406
103
37300

50을 줬을때 반복횟수와 소요시간