요리하는 개발자

https://www.acmicpc.net/problem/2407 이 문제는 메모이제이션이라는 방법을 이용하여 조합의 공식에 따라 구해보겠습니다. 조합$$_{n}C_{r}=_{n-1}C_{r-1}+_{n-1}C_{r}$$ 여기 파스칼의 삼각형이라 불리는 형태가 있습니다. $$_{4}C_{2}=_{3}C_{1}+_{3}C_{2}$$위와 같은 예시를 통해 원하는 값을 좌우측 상단을 더하면 일치한다는 것을 알 수 있습니다. 이 과정이 계속 반복되면 결국 0C0 1C0 1C1의 합으로 모든 조합을 표현할 수 있다는 것을 알 수 있습니다. 메모이제이션메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 ..

https://www.acmicpc.net/problem/1676 이 문제는 팩토리얼을 구한 후 문자열을 역순으로 정렬하면 쉽게 구할 수 있습니다. 팩토리얼$$N! = N\times (N-1)\times (N-2)\times \cdots \times 3\times 2\times 1$$ 바로 파이썬 코드로 확인하겠습니다. def factorial(N): result = 1 for i in range(1, N + 1): result *= i return result 팩토리얼을 함수로 구현했습니다. 1부터 입력값까지의 정수들을 result 변수에 곱하여 반환합니다, N = int(input()) N = str(factorial(N))[::-1] 팩토리얼 계산된 값을 문자열로 변환합니다. 파이썬에서는 [::-1..

https://www.acmicpc.net/problem/10872 아주 간단한 팩토리얼을 구하는 문제입니다. 팩토리얼$$N! = N\times (N-1)\times (N-2)\times \cdots \times 3\times 2\times 1$$ for문을 이용하여 1부터 입력값까지 곱한 값을 출력하면 되겠습니다. 파이썬코드로 구현해보겠습니다. N = int(input()) result = 1 for i in range(1, N+1): result *= i print(result) for문을 이용하여 1, 2, 3, ..., (N-1), N을 result에 곱하면 되겠습니다.

https://www.acmicpc.net/problem/11401 이번 문제는 11050, 11051번 문제와는 달리 굉장히 큰 입력을 처리해야 합니다. 특히 ( 큰 수 / 큰 수 ) 를 실행해야 하는데 이는 쉽지 않으므로 간단한 방법을 생각해보겠습니다. $$_{n}C_{k}\textrm{ mod }1000000007 = \frac{n!}{k!(n-k)!}\textrm{ mod 1000000007}$$ 이 식을 풀어야 하는데 단순히 큰 수끼리의 나눗셈이 힘들기 때문에 페르마의 소정리를 이용한 분할정복법을 이용하겠습니다. 페르마의 소정리를 이용하여 위 식을 변형하기 위해서는 나머지연산 곱셈의 역원에 대해서 알아야 합니다. 분할정복분할 정복법(Divide and Conquer)은 여러 알고리즘의 기본이 되..

https://www.acmicpc.net/problem/11051 이 문제를 풀기 위해서는 먼저 이항계수에 대해 알아야 합니다. 11050번 문제와는 달리 메모이제이션이라는 방법을 이용하여 풀어보겠습니다. 메모이제이션이라는 방법은 간단히 설명하면 메모를 해두어 메모가 되어있는 정보들은 바로 이용하는 방법입니다. 더 자세히 아시고 싶은 분은 나무위키를 참조하시기 바랍니다. (https://ko.wikipedia.org/wiki/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98) 먼저 이항계수를 구하는 방법을 11050번 문제와 다른 공식을 이용하겠습니다. $$n\mathbf{C}r = n-1\mathbf{C}r-1 + n-1\mathbf{C}r$$ 위 공식..