[Java] 백준(브론즈-1) 11050번 - 이항 계수 1
문제 풀이
문제 풀이에 앞서 이항 계수가 무엇인지 알아보자.
이항계수란?
위키백과를 보면 조합론에서 이항 계수(inomial coefficient)는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수라고 한다.
전체 집합에서 원소개의 개수 n에 대해 k개의 아이템을 뽑는 이항계수(조합의 수)는 다음과 같다.
이항식 (x+y)^2 을 이항정리로 전개한다면 (x+y)^2 = x^2 + 2xy + y^2 인데, 이 때의 각 항의 계수인 [1,2,1]이 이항계수이다.
그리고 이항계수는 조합을 통해 구할 수 있는데, 단순하게 위 공식을 이용하면 5개의 집합 중에서 2개를 순서없이 고르는 이항계수는 5! / (2! * 3!)이며 5!는 120이고, 2!는 2, 3!는 6이다. 120/12가 되어 답은 10이된다.
파스칼의 삼각형
이항계수를 구하는 방법 중에 파스칼의 삼각형이 있다. 파스칼의 삼각형은 아래의 그림과 같은 관계가 성립한다.
아이디어 도출 - 팩토리얼
- 특별한 아이디어 없이 위에서 본 점화식을 그대로 팩토리얼로 구현하면 된다.
바로 코드를 작성해보자.
1
2
3
4
5
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
bw.write(factorial(N) / (factorial(K) * factorial(N-K)) + "\n");
N과 K를 입력받고 이항계수 공식대로 N! / K! * (N-K)! 를 factorial 함수로 표현한다.
factorial 함수 코드의 내용은 다음과 같다.
1
2
3
4
public static int factorial(int N) {
if(N == 0) return 1;
return N * factorial(N-1);
}
팩토리얼을 사용한 무난한 이항계수 알고리즘이다.
팩토리얼을 통해 구현할 떄 주의할 점은 factorial 함수가 ‘0!’ 일 경우 1을 반환하도록 해야한다.
팩토리얼을 구현하여 제출하면 정답을 낼 수는 있지만 문제에서 요구하는 N과 K의 범위가 작기 때문이라고 생각이 들었다.
팩토리얼을 통한 풀이는 기본적으로 시간복잡도가 크기에 수의 범위가 작은 이번 문제에서나 가능한 접근방식인 것 같다.
아이디어 도출 - 재귀
- 이항계수 알고리즘을 점화식 그대로 재귀로 구현한다.
바로 코드를 작성해보자.
1
bw.write(binomial(N, K) + "\n");
binomial 함수에 N과 K를 주어 호출한다.
binomial 함수의 내용은 다음과 같다.
1
2
3
4
public static int binomial(int N, int K) {
if(K == 0 || N == K) return 1;
return binomial(N-1, K-1) + binomial(N-1, K);
}
재귀로 구현한 방식인데 이 방식의 경우 N의 범위가 커질수록 O(n!)의 시간복잡도를 가지기에 제한시간이 빠듯하다면 시간초과가 발생할 가능성이 매우 높다.
그래서 재귀를 사용하여 부분 문제를 풀 경우 중복되는 부분 문제가 나오더라도 다시 풀게 되기에 효율적이지 않다.
메모이제이션(memoization)이란?
메모이제이션은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이라고 한다. - 위키백과
아아디어 도출 - 동적계획법 풀이(DP)
파스칼의 삼각형을 통해, 이항계수를 구하는 알고리즘은 중복 부분문제와 최적 부분구조를 만족하므로 동적계획법으로 이항계수를 구할 수 있다.
그렇게 재귀로 풀었던 알고리즘에 동적계획법을 이용한다.
- 메모이제이셔을 할 배열을 초기에 선언한다.
- 재귀로 각 부분 문제들에 접근하여 문제가 풀리면 메모이제이션을 할 배열에 저장해 나가도록 구현한다.
재귀 풀이 방식에 동적계획법을 코드로 적용해보자.
1
static int[][] DP;
main 메서드 바깥에, 즉 전역으로 2차원 배열 DP를 선언하자.
1
2
3
// main 메서드
DP = new int[N+1][K+1];
bw.write(binomial_coefficient(N, K)+"\n");
그리고 main 메서드 안에서 DP 배열을 초기화한후 binomial_coefficient 함수에 N과 K를 주어 호출한다.
binomial_coefficient 함수의 내용은 다음과 같다.
1
2
3
4
5
public static int binomial_coefficient(int N, int K) {
if (DP[N][K] > 0) return DP[N][K]; // recycle
if (K == 0 || N == K) return DP[N][K] = 1;
return DP[N][K] = binomial_coefficient(N-1, K-1) + binomial_coefficient(N-1, K);
}
첫번째 if문이 중요한데, 이미 풀었던 부분 문제일 경우 값을 재활용하기 위해 해당 배열의 값을 return해야 한다.
작성코드
작성코드 - 팩토리얼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
bw.write(factorial(N) / (factorial(K) * factorial(N-K)) + "\n");
bw.flush();
bw.close();
br.close();
}
public static int factorial(int N) {
if(N == 0) return 1;
return N * factorial(N - 1);
}
}
작성코드 - 재귀
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
bw.write(binomial(N, K)+"\n");
bw.flush();
bw.close();
br.close();
}
public static int binomial(int n, int k) {
if(k == 0 || n == k) return 1;
return binomial(n - 1, k - 1) + binomial(n - 1, k);
}
}
작성코드 - 동적계획법(DP)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.io.*;
import java.util.*;
class Main {
static int[][] DP;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
DP = new int[N+1][K+1];
bw.write(binomial_coefficient(N, K)+"\n");
bw.flush();
bw.close();
br.close();
}
public static int binomial_coefficient(int N, int K) {
if (DP[N][K] > 0) return DP[N][K];
if (K == 0 || N == K) return DP[N][K] = 1;
return DP[N][K] = binomial_coefficient(N - 1, K - 1) + binomial_coefficient(N - 1, K);
}
}
회고
- 이항계수에 대해서 알아보고 공부할 수 있었으며, nCr 공식을 통해 쉽게 문제를 풀 수 있었다.
- 이항계수를 구하는 점화식을 통해 팩토리얼로 푸는 방식, 재귀로 푸는 방식을 생각해낼 수 있었지만 이는 주어진 N,K의 범위가 매우 작기에 가능한 방법이었고, 성능을 향상시키기 위해선 동적계획법(DP)를 통해 중복되는 부분 문제들을 넘기고 풀도록 구현할 수 있었다.