[백준 알고리즘]피보나치 수열(1003)

https://www.acmicpc.net/problem/1003 문제에 제시된 재귀함수를 수정하여 파이썬코드로 간단하게 해결해봤습니다.
알고리즘 2018. 2. 18. 21:07
[백준 알고리즘]패션왕 신해빈(9375)

https://www.acmicpc.net/problem/9375 이 문제의 경우 간단한 방법을 이용해서 조합을 구현하지 않아도 해결할 수 있는 문제입니다. 각 의상의 종류마다 n1, n2, n3, ...가지를 가지고 있다면 의상을 입지 않는 경우를 포함하여 경우의 수를 계산할 수 있습니다. $$_{n_{1}+1}C_{1}\times _{n_{2}+1}C_{1}\times _{n_{3}+1}C_{1}\times ...$$ 여기서 모든 종류의 의상을 입지 않는 경우 한 가지만 빼면 모든 경우의 수를 구할 수 있습니다. 따라서 코드로 구현해야할 식을 다음과 같습니다. $$(n_{1}+1)\times (n_{2}+1)\times (n_{3}+1)\times ... - 1$$ 파이썬 코드로 구현해보겠습니다. n..
알고리즘 2018. 2. 18. 18:42
[백준 알고리즘] 조합(2407)

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)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 ..
알고리즘 2018. 2. 11. 03:36
[백준 알고리즘] 팩토리얼 0의 개수(1676)

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..
알고리즘 2018. 2. 11. 03:15
[백준 알고리즘] 팩토리얼(10872)

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에 곱하면 되겠습니다.
알고리즘 2018. 2. 11. 02:16
[백준 알고리즘] 이항계수3(11401)

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)은 여러 알고리즘의 기본이 되..
알고리즘 2018. 2. 10. 17:37
[백준 알고리즘] 이항계수2(11051)

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$$ 위 공식..
알고리즘 2018. 2. 10. 00:44
[백준 알고리즘] 이항계수1(11050)

https://www.acmicpc.net/problem/11050 이항계수 문제를 풀기 위해서 이항계수 수식을 먼저 알아야 합니다. $$\binom{N}{K} = \frac{N!}{K!(N-K)!}$$ 파이썬 코드로 풀어봤습니다. def factorial(x): if x == 1: return 1 else: return x * factorial(x-1) 재귀함수를 이용하여 팩토리얼을 계산합니다. 위 함수가 실행되면 x * (x-1) * (x-2) * ... * 2 * 1 을 계산하게 됩니다. def binomial(N, K): return factorial(N) / (factorial(K) * factorial(N - K)) 이항계수를 계산하는 함수입니다. 이전에 작성한 팩토리얼 함수를 이용하면 간단하..
알고리즘 2018. 2. 9. 01:22
1