dynamic programming 썸네일형 리스트형 Algospot "PI" 문제풀이. by Python 알고리즘 문제해결 전략의 알고스팟에 올라온 문제 PI의 문제풀이입니다. 다음은 문제 링크 https://www.algospot.com/judge/problem/read/PI 해결 아이디어 1. 기본적으로 동적 계획법을 이용하고 각각의 조건에 대해서 난이도를 메기는 것을 함수로 모듈화 하고 싶다. 2. 동적 계획법을 위해서 cache에 저장할 형태와 함수의 입출력의 성질에 대해서 예상했다. 입력은 주어진 수열의 시작 인덱스로 하고, 시작 인덱스로부터 수열의 끝까지 작은 Sub-sequence의 인덱스를 재귀적으로 함수에 입력할려고 한다. 따라서 cache의 크기는 수열의 길이만큼만 확보한다. (사실 10001으로 해야하는데 지금은 그냥 100으로 해두었다. 작고 소중한 램...) 3. 메모이제이션을 위해 .. 더보기 최적화 문제 동적 계획법(with 최적 부분 구조의 개념 설명) 이 게시글은 알고스팟의 문제("LIS")와 "알고리즘 문제 해결전략"을 공부한 정리글 입니다. 최적 부분 구조란? Optimal substructure. 문제를 해결하는 데에 필요없는 입력을 최대한 줄이고, 완전한 수학적인 의미의 함수를 만든다! 수학적으로 어떤 입력이 들어가면 그 입력에 대해서만 의존적으로 함수의 출력이 반환된다. 이것이 되어야 한다. 다시말해, 지금까지 어떤 경로로 이 문제에 도달했는 지에 상관없이 남은 부분 문제는 항상 최적으로 풀어도 상관없다는 뜻! 이것이 동적 계획법에 가장 중요한 요소이다. 문제를 분할하는데, 그냥 분할하는게 아니라, 최적 부분 구조로 분할하면 제일 좋다. 최적화 문제의 동적 계획법 다음과 같은 일반화된 해결 방법을 따라 해결된다. 1. 완전 탐색 알고리즘 설계.. 더보기 이전 1 다음
