후회가 없도록

문제 출처: https://www.acmicpc.net/problem/11444 1. 결과 메모리 29200KB, 시간 88ms 2. 풀이 이 문제는 평범한 재귀 호출이나 동적 계획법과 같은 연산을 통해 구하기가 쉽지 않다. 문제 조건에서 볼 수 있듯이 Fn을 구하는데, 해당 n이 최대 10^17(10의 17제곱)까지 가능하기 때문이다. 또한 피보나치 수열은 궁극적으로 앞의 연속된 두 숫자를 알아야만 그 다음 숫자를 구할 수 있고, 앞의 연속된 두 숫자는 또 해당 숫자의 앞의 연속된 두 숫자를 알아야만 연산이 가능하다. 즉, 기존의 피보나치 수열 개념( Fn = Fn-1 + Fn-2 (n ≥ 2) )은 연쇄적으로 연산이 되기 때문에, 각각의 독립된 소문제 해결을 통해 큰 문제를 해결하는 일반적인 분할 정..

문제 출처: https://www.acmicpc.net/problem/1780 1. 결과 메모리 67648KB, 시간 3592ms 2. 풀이 분할 정복을 최근에 제대로 배워보면서 분할 정복과 재귀 호출을 연습하게 되는 계기가 되었다. 또한, 나로서는 이 문제에서 하나의 함수만으로 재귀 호출 후 답을 반환하는 아이디어가 쉽게 떠오르지 않았기 때문에 전역 변수를 사용했다. 각 함수 내에서 global을 통해 counts가 전역 변수임을 알렸는데, 이런 전역 변수 선언은 가장 함수의 맨 위에서 이루어져야 한다. 파이썬은 위에서부터 순서대로 읽어나가는 경향이 있기 때문에, 함수의 중후반에서 전역 변수 선언을 했을 때는 그 이전 줄에서 이 counts라는 변수를 읽지 못하고 오류가 발생했다. 오히려 전역 변수를 ..