문제
자연수 과 정수 가 주어졌을 때 이항 계수 를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 과 가 주어진다. (1 ≤ ≤ 1,000, 0 ≤ ≤ )
출력
를 10,007로 나눈 나머지를 출력한다.
예제 입력
5 2
예제 출력
10
힌트
출처
- 문제를 만든 사람: baekjoon
- 데이터를 추가한 사람: emiyagugizzada
이론이해-(출처:위키백과)
1. 동적계획법:
수학과 컴퓨터 공학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
동적 계획법의 원리는 매우 간단하다. 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.
동적 계획 알고리즘은 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용된다. 이것은 동적 계획법은 문제를 해결하기 위한 모든 방법을 검토하고, 그 중에 최적의 풀이법을 찾아내기 때문이다. 이에 우리는 동적 계획법을 모든 방법을 일일이 검토하여 그 중 최적해를 찾아내는 주먹구구식 방법이라고 생각할 수 있다. 그러나 문제가 가능한 모든 방법을 충분히 빠른 속도로 처리할 수 있는 경우, 동적 계획법은 최적의 해법이라고 말할 수 있다.
피보나치 수열과 차이를 통한 이해
보통 피보나치 수열을 구하는 함수는 다음과 같이 작성한다.
function fib(n) if n = 0 return 0 else if n=1 return 1 else return fib(n-1) + fib(n-2)
이때, fib(5)를 구한다고 한다면 계산은 다음과 같이 이루어진다.
fib(5)fib(4) + fib(3)(fib(3) + fib(2)) + (fib(2) + fib(1))((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
여기에서 세 번째 줄의 fib(2)가 중복되어 계산되고, 이것은 전체적인 계산 속도를 떨어뜨린다. 이 알고리즘의 시간 복잡도는 지수 함수가 된다.
여기에서 각 함수의 계산값을 저장하는 객체 m을 추가하면, 이 알고리즘은 다음과 같이 바뀐다.
var m := map(0 → 1, 1 → 1)
function fib(n) if n not in keys(m) m[n] := fib(n-1) + fib(n-2) return m[n]
이렇게 각 계산값을 저장하면, 중복 계산이 줄어들고 시간 복잡도는 O(n)이 된다.
2. 메모이제이션:
메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다. 메모아이제이션이라고도 한다
피보나치 수열과 차이를 통한 이해
피보나치 수열을 구하는 가장 단순한 방법은 다음과 같다.a
fib(n) {
if n is 1 or 2, return 1;
return fib(n-1) + fib(n-2);
}
이때 fib 함수가 재귀적으로 실행되면서 같은 인자값에 대해서 계속해서 반복되므로, 전체 실행시간은 Ω(1.6n)이다. 그러나 fib(n)의 값을 계산하자마자 저장하면(memoize), 실행시간을 Θ(n)으로 줄일 수 있다.
allocate array for memo, setting all entries to zero; initialize memo[1] and memo[2] to 1;
fib(n) { if memo[n] is zero: memo[n] = fib(n-1) + fib(n-2); return memo[n]; }
JAVA: 반복문 이용
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
sc.close();
int[][] list = new int[1001][1001];
list[0][0]= list[1][0] = list[1][1] = 1;//파스칼의 삼각형 생각해보기
for(int i = 2; i<= N; i++){
for(int j = 0; j <= i; j++){//파스칼의 삼각형에서 j의 끝 번호는 = i와 같음(EX: 2C0~~~~2C2)
if(i == j || j == 0){
list[i][j] = 1;
}else{
list[i][j] = list[i - 1][j -1] + list[i - 1][j];//이해 안 될 경우 이항 계수 1번문제 참고
}
list[i][j] %= 10007;
}
}
System.out.println(list[N][K]);
}
}
'알고리즘(Java) > 이항 계수' 카테고리의 다른 글
| 백준 11050 이항 계수 1 (0) | 2017.12.06 |
|---|