알고스팟 썸네일형 리스트형 Algospot 'QUANTIZE' 문제 풀이. by Python 이 게시글은 '알고리즘 문제 해결전략'의 공부 정리입니다. 문제 해결 아이디어 1. 기본적으로 Memoization을 사용한다. 2. Memoization을 위해 cache의 크기를 결정하자. 수열의 인덱스의 개수를 함수의 입력으로 하고 동시에 cache의 인덱스의 개수로 하고자 한다. 3. 이때 이 문제의 어려운 점은, s의 개수가 제한되어 있기 때문에 인덱스만을 함수의 입력으로 하면 더 사용할 수 있는 s가 몇 개인지 알 수 없어서 정답을 찾아낼 수 없다. -> 따라서 남은 s의 개수도 함수의 입력으로 하고, 동시에 cache의 인덱스도 2차원 리스트로 한다. 4. 입력된 수열의 정렬 순서는 상관이 없으므로 오름차순으로 정렬한다. 그러면 지금까지 사용한 s의 구체적인 값을 기억해둘 필요가 없다. 앞으.. 더보기 최적화 문제 동적 계획법(with 최적 부분 구조의 개념 설명) 이 게시글은 알고스팟의 문제("LIS")와 "알고리즘 문제 해결전략"을 공부한 정리글 입니다. 최적 부분 구조란? Optimal substructure. 문제를 해결하는 데에 필요없는 입력을 최대한 줄이고, 완전한 수학적인 의미의 함수를 만든다! 수학적으로 어떤 입력이 들어가면 그 입력에 대해서만 의존적으로 함수의 출력이 반환된다. 이것이 되어야 한다. 다시말해, 지금까지 어떤 경로로 이 문제에 도달했는 지에 상관없이 남은 부분 문제는 항상 최적으로 풀어도 상관없다는 뜻! 이것이 동적 계획법에 가장 중요한 요소이다. 문제를 분할하는데, 그냥 분할하는게 아니라, 최적 부분 구조로 분할하면 제일 좋다. 최적화 문제의 동적 계획법 다음과 같은 일반화된 해결 방법을 따라 해결된다. 1. 완전 탐색 알고리즘 설계.. 더보기 알고스팟: WILDCARD Python 풀이. (동적 계획법 연습문제) 알고스팟의 문제 링크: https://www.algospot.com/judge/problem/read/WILDCARD 문제 와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 포함한다. 와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된 ? 는 어떤 글자와 비교해도 일치한다고 가정하며, * 는 0 글자 이상의 어떤 문자열에도 일치한다고 본다. 예를 들어 와일드 카드 he?p 는 파일명 help 에도, heap 에도 매치되지만, helpp 에는 매치되지 않는다. 와일드 카드 *p*.. 더보기 Divide and Conquer, 울타리 잘라내기 문제(FENCE) 문제출처: Algospot FENCE 문제. https://www.algospot.com/judge/problem/read/FENCE 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요. 단 (c)처럼 직사각형을 비스듬히 잘라낼 수는 없습니다. 판자의 너비는 모두 1이라고 가정합니다. 입력 첫 .. 더보기 완전탐색 알고리즘, Algospot의 CLOCKSINC문제 풀이. 이 게시글은 Algospot의 CLOCKSINC 문제의 풀이입니다. 풀이 과정은 도서 "알고리즘 문제해결 전략"의 풀이법의 큰 틀을 참고하되 최대한 스스로 구현했습니다. 다음은 알고스팟의 문제 링크. https://www.algospot.com/judge/problem/read/CLOCKSYNC 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다. 시계의 시간을 조작하는 유일한 방법은 모두 10개 있는 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계에 연결되어 있다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시.. 더보기 이전 1 다음
