메모이제이션 썸네일형 리스트형 Algospot 'QUANTIZE' 문제 풀이. by Python 이 게시글은 '알고리즘 문제 해결전략'의 공부 정리입니다. 문제 해결 아이디어 1. 기본적으로 Memoization을 사용한다. 2. Memoization을 위해 cache의 크기를 결정하자. 수열의 인덱스의 개수를 함수의 입력으로 하고 동시에 cache의 인덱스의 개수로 하고자 한다. 3. 이때 이 문제의 어려운 점은, s의 개수가 제한되어 있기 때문에 인덱스만을 함수의 입력으로 하면 더 사용할 수 있는 s가 몇 개인지 알 수 없어서 정답을 찾아낼 수 없다. -> 따라서 남은 s의 개수도 함수의 입력으로 하고, 동시에 cache의 인덱스도 2차원 리스트로 한다. 4. 입력된 수열의 정렬 순서는 상관이 없으므로 오름차순으로 정렬한다. 그러면 지금까지 사용한 s의 구체적인 값을 기억해둘 필요가 없다. 앞으.. 더보기 Algospot "PI" 문제풀이. by Python 알고리즘 문제해결 전략의 알고스팟에 올라온 문제 PI의 문제풀이입니다. 다음은 문제 링크 https://www.algospot.com/judge/problem/read/PI 해결 아이디어 1. 기본적으로 동적 계획법을 이용하고 각각의 조건에 대해서 난이도를 메기는 것을 함수로 모듈화 하고 싶다. 2. 동적 계획법을 위해서 cache에 저장할 형태와 함수의 입출력의 성질에 대해서 예상했다. 입력은 주어진 수열의 시작 인덱스로 하고, 시작 인덱스로부터 수열의 끝까지 작은 Sub-sequence의 인덱스를 재귀적으로 함수에 입력할려고 한다. 따라서 cache의 크기는 수열의 길이만큼만 확보한다. (사실 10001으로 해야하는데 지금은 그냥 100으로 해두었다. 작고 소중한 램...) 3. 메모이제이션을 위해 .. 더보기 이전 1 다음
