컴공과고씨

https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 이 문제를 보고 나는 수학적으로 풀어야겠다고 생각했다. 물론 dynamic programing (동적계획법)으로도 풀 수 있지만 딱 처음 떠오른것이 수학적으로 푸는것이였다. 어떤 생각을 했냐면 일단 최대한 5원짜리를 쓰고 남은 돈에서 만약 2로 나눴을 때 나머지가 0이 안되면 5원짜리를 한 개 덜 쓴 후 2로 나누어 주도록 반복하여 2로 나눈 나머지가 0이 되도록 하면 쉽게 풀릴거라고 생각했다. 그리고 예외처리로 처음 최대한 5원짜리를 쓰고 점점 5원짜리를 줄여갈건데 이것이 음수가 되면 거슬러 줄 수 없는 것이므로 ..

https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 피보나치 수를 구하는 문제. 문제를 보면 처음 들어야할 생각은 동적 계획법(dynamic programing)를 떠올려주면 쉽게 풀린다. 재귀로 구현하면 아마 시간초과가 걸릴것이다. 그렇기 때문에 dp 배열을 이용하여 각 값을 저장해주고 다음 값을 구할때 계산하는 대신 앞에 계산한 값을 가져와주면 된다. 현재 값은 그 전의 값 + 그 전전 값 이 식을 구현해 주..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 이 문제를 처음 보고 위 보기에 있는 코드를 써서 카운트를 한다면 아마 시간초과가 날 것이다. 재귀 함수는 기본적으로 시간을 많이 쓰기 때문에... 그렇기에 다른 방법을 사용해야 하는데 나는 동적 계획법을 사용하여 풀었다. 동적 계획법은 이제 처음 연산은 기록해서 이미 했던 연산일 경우 연산을 하지않고 기록한 값을 가져오는 방식으로 위 문제를 재귀함수로 푸는 것 보다 훨씬 빠르다. 원리는 0 1 f(0) = 1번 0번 f(1) = 0번 1번 f(2) = f(0)의 0번 개수 + f(1)의 0번..