Development Artist

백준 단계별 풀기에서 분할정복 다섯 번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 절대 단순한 문제가 아니다. 설계를 어떻게 하느냐에 따라 연산의 성능이 확연히 차이가 난다. 방법은 3가지가 있다. 1. 점화식을 이용한 방법 -> O(N^2)으로 시간 초과 2. 이항계수의 정의를 활용한 방법 2.1. 확장 유클리드(호제법) 2.2. 페르마 소정리 우리는 확장 유클리드 알고리즘과 페르마 소정리를 이용하고자 한다. (실제 백준 추천 알고리즘) 일..

도입 백준 단계별 풀기에서 분할정복 두 번째 문제이다. 풀이 1. 앞의 '색종이 만들기' 문제와 유사하다. 재귀함수를 활용한다. 정사각형을 4개씩 쪼개면서 재귀함수를 호출하는 방식은 같으나, 출력에서 '('와 ')'를 해주어야 하는데 어디서 해야할까? 4개씩 재귀를 호출하는 곳에서 시작에서 '('를 해주고 재귀를 마칠때 ')'를 출력해주면 된다. 함수call의 특성에서 a라는 함수가 수행 되는 중 b라는 함수가 call이 되면 a 함수는 사라지는 것이 아니다. stack구조 처럼 생각하자. a함수 수행 중 b함수가 call이 되면 a함수는 stack에 push된다(대기한다). 그리고 b가 다 수행이 되면 a함수가 stack에서 pop되면서 이전의 수행지점을 찾아 그 이후부터 수행이 된다. 따라서, a함수..