[백준 알고리즘] 11051번(이항 계수Ⅱ)

[백준 알고리즘]

이항 계수 문제를 하나씩 풀다 보니 내가 몰랐던 것이 너무 많다는 것을

다시 한번 알게 되었습니다. 그래서 공부 더 열심히 하려고 합니다

힘냅시다

이전에 이항계수를 구하는 것은 재귀함수를 써서 구했습니다.

그리고 시간복잡도 같은 것은 잘모르기도 하고 별 신경을 안쓰고 짰었습니다.

하지만 저번부터 피보나치도 그렇고 이번에 이항 계수도 그렇고 앞으로도 그럴 것 같습니다.

시간이 점점 중요해지고 있다는 것을요 그리고 점점 생각할 것이 많아 진다는 것도요...

여튼 이번에 풀어본 문제는 이항계수 관한 문제입니다.

그리고 여기에서 우리에게 원하는 것은 동적 계획법 / 메모이제이션 으로 풀으라는 것입니다.

그렇습니다 다시 공부해야합니다.

• 동적 계획법(Dynamic Programming) / 메모이제이션                             (출처 :나무위키)

이 동적 계획법은 특정 범위까지 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적인 값을 구하는 알고리즘 설계 기법입니다. 엄밀하게 말해서 알고리즘이라기 보다는 문제해결 패러다임에 가깝다고 합니다. 그래서 네이버에 검색해보면 지식백과에 생명과학 / 교육학 분야에 맞춰서 검색 되서 바로 나오는 것을 알 수 있습니다. 

이런 동적 계획법은 최적 부분 구조(Optimal Substructure)를 갖추고 있어야만 적용이 가능합니다.

쉽게 말하자면 결과 값을 구하기 위해 했던 계산을 또하고 또하고 계속해야하는 문제에 적용할 때 그 효과가 뛰어 나다는 것입니다. 

백과사전을 다 읽고 나서 동적 계획법은 중복 계산을 없애고 계산한 것을 저장해 놓고 나중에 다시 사용한다는 것입니다. 생각보다 쉬운 개념입니다.

제가 이전에 재귀함수로 풀었던 피보나치 수열입니다.

보시다 시피 계산 했던 Fibonacci(1) / Fibonacci(2) 가 2 ~ 3 번 씩 계산 되는 것을 알 수 있습니다.

총 9번의 계산을 거쳐야 계산이 모두 끝이 납니다. 하지만 밑에 있는 것을 보시면

단 5번 만에 계산이 끝납니다. 이렇게 중복된 계산을 없애고 그전에 계산 된 것을 이용하여 굳이 중복된 계산을 하지 않겠다는 것입니다.

그래서 한번 계산 된 것은 배열에 넣고 다음번에 그냥 가져와서 사용하면 됩니다.

그렇게 코딩을 하면 되겠습니다. 

 

import java.util.Scanner;
 
public class Beak11050 {
 
    static int[][] list;
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int r = sc.nextInt();
        list = new int[1001][1001];
        list[1][0] = list[1][1] = 1;
 
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                if(i == j || j == 0)
                    list[i][j] = 1;
                else
                    list[i][j] = list[i-1][j-1] + list[i-1][j];
                
                list[i][j] %=10007;
            }
        }
        System.out.println(list[n][r]);
    }
}
 

이렇게 재귀함수를 사용하지 않고 모든 값을 배열에 넣어 알고리즘을 짰습니다.

재귀함수랑 비슷합니다. 단지 배열에 넣어서 계산을 했을 뿐입니다.

그리고 배열 시작하는 인덱스가 0이여서 그걸 1로 시작하게끔 했습니다.

그것만 주의하시면 금방 해결 하실겁니다.