🐢 11. Recursion & Dynamic programming

⭐ 무식한 방법 (brute force)

countWay(n-1) + countWays(n-2) + countWays(n-3)

• 초기 사례(base case) 중요함
• 현재 딛고 있는 계단이 0번째 계단이라고 하면, 여기까지는 0개의 경로가 있는걸까? 1개의 경로가 있는걸가?
  • 정답은 정의하기 나름
• 1로 정의하는 것이 문제 풀기 더 쉽다

  int countWays(int n) {
  	if (n < 0) {
  		return 0;
  	} else if (n == 0) {
  		return 1;
  	} else {
  		return countWays(n-1) + countWays(n-2) + countWays(n-3);
  	}
  }
  

  • 알고리즘의 수행 시간은 지수적으로 증가한다
  • 재귀 호출 세번 함

⭐ 메모이제이션 방법

• countWays가 불필요하게 중복 호출되는 경우 있음
• n을 이전에 본 적이 있다면 캐시에 저장된 값을 반환해주면 된다
• 값을 새로 계산할 때마다 이를 캐시에 저장해둔다
• 일반적으로 캐시를 사용할 때 HashMap 사용함
  • 키 값이 정확하게 1부터 n까지의 정수값이므로 정수 배열을 사용하는 게 공간 면에서 더 효율적이다

⭐ 연관 문제: 중복된 값을 허용한다면 어떻게 풀겠는가

• 원소들이 중복되어 나타나면 알고리즘은 제대로 동작되지 않는다
  • 해법 1: 재귀
    • 초기 사례로부터의 확장
    • 최적화를 원한다면 재귀가 아닌 반복문 사용
  • 해법 2: 조합론
    • 집합 생성할 때 원소 각각에 대해 두 가지 중 한 가지 결정해야 함
    • 집합에 속하는지 or 속하지 않는지
    • 2^n 개의 모든 가능한 부분 집합을 구할 수 있다