조합3 [BAEKJOON] 2407번: 조합 (Java) 완전탐색 문제를 풀다가 순열과 조합 유형이 자주 나와서 계속 풀어보고 있다. nCm을 구하는 것이 문제이다. 1. 문제 2. 풀이 과정 2.1 재귀를 통한 접근 첫번째 접근 방법은 고등학교 때 배운 파스칼의 삼각형을 떠올려, 재귀를 이용한 방법으로 풀어보았다. 코드는 아래와 같다. import java.util.Scanner; public class Main { public static long paskal(int n, int m){ if(m == 0 || n == m){ return 1; } return paskal(n-1,m-1) + paskal(n-1,m); } public static void main(String[] args) { Scanner sc = new Scanner(System.in);.. 2020. 7. 16. [BAEKJOON] 2004번: 조합 0의 개수 (Java) 1. 문제 nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 n, m(0≤m≤n≤2,000,000,000, n!=0)이 들어온다. 출력 첫째 줄에 0의 개수를 출력한다. 예제 입력 25 12 예제 출력 2 2. 풀이 처음 이 문제를 접근할 때 nCr = n!/(n-r)!r! 공식을 통해서 접근하려고 했다. 하지만 입력 범위가 m,n이 최대 20억인걸 보고 당연히 이 방식은 아닐꺼라고 생각했다. 그리고 끝이 0이 되려면 2x5 쌍이 1개 일 경우 뒤에 0이 한개 생기므로 2와5가 곱해진 개수를 세서 2와5의 지수 중 작은거를 선택하면 되겠다고 접근했다. 여기서 하나 더 생각해야할 것은 2와 5의 지수의 총합을 어떻게 구할지 였다. 100!을 생각해 봤을 때, 5가 곱해진 개.. 2020. 7. 12. [Algorithm] 조합 코드 구현 (Java) 완전탐색 알고리즘에서 모든 경우의 수를 계산한 후 결과 값을 찾는 방식이 자주 나온다. 그래서 재귀를 통해 조합을 구현하는 방법에 대해서 정리하려고 한다. 이때 기본 형식은 아래와 같다. 1. 조합(Combination) 조합은 고등학교 수학에서 경우의 수를 계산할 때 순열과 조합 파트로 배웠었다. 프로그래밍에서도 수학에서의 순열과 조합과 같다고 생각하면 된다. 잠시 고등학교 수학에서 배운걸 생각해보면 아래와 같다. 순서를 고려하지 않고 선택하는 방법 nCr : n개 중 r개를 순서에 상관없이 선택하는 방법의 수 nCr = nPr/r! / (n-r)!r! 간단히 예시를 들면 {1,2,3} 에서 2개를 뽑는 경우의 수 는 3C2로 3X2/2! = 6. 즉, 3가지가 나온다. {1,2} {1,3} {2,3}.. 2020. 7. 12. 이전 1 다음
