동적계획법 썸네일형 리스트형 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. 완전 탐색 알고리즘 설계.. 더보기 알고스팟: WILDCARD Python 풀이. (동적 계획법 연습문제) 알고스팟의 문제 링크: https://www.algospot.com/judge/problem/read/WILDCARD 문제 와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 포함한다. 와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된 ? 는 어떤 글자와 비교해도 일치한다고 가정하며, * 는 0 글자 이상의 어떤 문자열에도 일치한다고 본다. 예를 들어 와일드 카드 he?p 는 파일명 help 에도, heap 에도 매치되지만, helpp 에는 매치되지 않는다. 와일드 카드 *p*.. 더보기 동적 계획법(Dynamic Progamming) - 알고리즘 문제해결 전략 공부 정리. 이 게시글은 알고리즘 문제 해결전략을 읽고 공부한 내용을 정리한 글입니다. 동적 계획법이란? 동적 계획법은 간단히 이야기해서, 완전 탐색법의 비효율성을 개선한 방법으로써, 중복되어 실행되는 부분의 중복을 제거하는 기법이다. 이때, 중복이 되는 부분은 전체 알고리즘의 부분 알고리즘인데, 이 부분적인 알고리즘이 수학적 함수의 성질을 가지고 있어야 한다. 수학적 함수의 성질이란 입력이 주어질 때, 외적인 변수는 함수의 출력에 영향을 주지 않고 오로지 입력만이 출력에 영향을 주는 함수를 뜻한다. (프로그래밍에서 함수는 전역변수 등으로 인해 이런 성질이 없는 경우가 많다.) 이런 수학적 함수의 성질을 가진 함수는 '참조적 투명성(referential transparency)'을 가졌다고 하고, '참조적 투명함수(.. 더보기 이전 1 다음
