Algorithm | Dynamic Programming & Greedy Algorithm

 동적 프로그래밍과 탐욕법은 문제를 해결하여 최적의 해를 구하는 방법이다.

Dynamic Programming?

 동적 프로그래밍(Dynamic Programming)은 큰 문제를 하위의 작은 문제들로 나누어 풀어 최적의 해를 구하는 기법이다. 이러면 분할정복 기법과 다를게 없어 보인다. 하지만 분할정복 기법은 작은 문제들을 풀다보면 같은 작은 문제를 반복해서 푸는 경우가 생기게 된다. 이 때, 작은 문제를 매번 다시 계산하지 않고 값을 배열에 저장(Memoization)해두었다가 재사용하는 것이 동적 프로그래밍이다. 

 

 동적 프로그래밍을 이용하여 풀 수 있는 대표적인 문제는 피보나치 수열, 최장 공통부분 수열문제, 배낭 문제 등이 있다.

 

 간단하게 피보나치수열 문제를 풀어보자. 

package fibonacci;

class Main {
  static long memory[] = new long[101];

  public static long fibonacci(int n) {
    if(n <= 2) {	// 2 이하는 1 반환
      return 1;
    }

    if(memory[n] != 0) {	// 이미 푼 적 있는 문제라면
      return memory[n];		// 저장된 값 호출
    }
    
    return memory[n] = fibonacci(n-1) + fibonacci(n-2);
  }
  public static void main(String[] args) {
    System.out.println(fibonacci(100));
  }
}

출처 : https://shoark7.github.io/programming/algorithm/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84-%ED%95%B4%EA%B2%B0%ED%95%98%EB%8A%94-5%EA%B0%80%EC%A7%80-%EB%B0%A9%EB%B2%95

 재귀적으로만 문제를 해결하면 n이 작을 경우엔 별 차이 없겠지만 그 값이 커질 수록 이미 해결한 작은 문제들을 반복해서 푸는 경우가 많아져 속도가 굉장히 느려진다. 따라서 memory[]에 한번 계산한 값은 저장한 후 호출하도록 동적 프로그래밍을 이용하도록 하자.

Greedy Algorithm?

 탐욕법(Greedy Algorithm)은 각 단계에서 가장 최선의 선택을 하는 기법이다. 각 단계에서 최선의 선택을 한 것이 최적의 해가 된다는 것을 전제 하에 진행한다. 동적 프로그래밍 사용 시 지나치게 많은 계산을 하는 것에 착안하여 고안된 알고리즘이다. 

 

 탐욕법은 모든 경우에서 최적의 해를 구할 순 없다. 그러나 구현이 간단하다는 점에서 큰 장점을 가지고 있다.

 

 탐욕법을 시간표 짜기 문제에 적용해보자. 다음과 같은 시간표 목록을 이용하여 되도록 많은 과목을 듣는 알찬 시간표를 짜보자. 

과목명	수업 시작	수업 종료
국어	9:00AM	10:00AM
영어	9:30AM	10:30AM
수학	10:00AM	11:00AM
사회	10:30AM	11:30AM
과학	11:00AM	12:00AM

 탐욕 알고리즘을 이용하여 문제를 풀어보자. 과정은 다음과 같다.

 

1. 최대한 많은 과목을 듣기 위해 가장 빨리 끝나는 과목을 선택하여 첫 번째 과목으로 신청하자. (국어)

2. 신청한 과목이 끝난 후 시작하는 과목들 중 가장 빨리 끝나는 과목을 신청하자. (국어-수학)

3. 2번의 과정을 반복한다. (국어-수학-과학)

 

간단한 과정을 거쳐 정답은 국어-수학-과학 임을 찾을 수 있다.

---

Reference

 

· [도서] Hello Coding 알고리즘

· 그리디 알고리즘 - https://www.youtube.com/watch?v=PNPIk3hc6ic

· 그리디 알고리즘 - https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188

· 동적 프로그래밍 - https://www.zerocho.com/category/Algorithm/post/584b979a580277001862f182