ComDoc ComDoc

동적 프로그래밍((dynamic programming)을 적용하기 쉬운(?) 예제로 가장 긴 공통 문자열 찾기(LCS, Longest Common Substring)가 있습니다. 두 개의 문자열 'abcde'와 'cdefg'에서 가장 긴 공통 문자열은 'cde'입니다. 먼저 전수조사(brute force)로 답을 찾아보고 문제점을 알아봅니다. def make_set(s): result = set() for i in range(len(s)): for j in range(i + 1, len(s) + 1): result.add(s[i:j]) return result def lcs(s1, s2): max_len = 0 max_str = '' for each in make_set(s1) & make_set(s2)..

막대기 자르기(Rod cutting) 하나의 막대기가 있다. 막대기의 길이에 따라 가격이 다르다. 최고의 수익을 얻도록 막대기를 자르라. 이때 최고의 수익은? 파이프 전체의 길이, 잘랐을 때 길이에 따른 가격이 들어간 배열이 주어짐. length : i 1 2 3 4 5 6 7 8 9 price : Pi 1 5 8 9 10 17 17 20 24 재귀로 구현 def cut_rod(price, n): max_val = price[n] for i in range(1, n): max_val = max(max_val, price[i] + cut_rod(price, n - i)) return max_val print(cut_rod([0, 1, 5, 8, 9, 10, 17, 17, 20, 24], 8)) # 22 어..

피보나치 수(Fibonacci numbers)의 역사는 적어도 기원전 700년경으로 거슬러 올라가며, 1202년 이탈리아의 수학자인 레오나르도 피보나치가 피보나치 수로 토끼의 개체 수 증가를 설명한 것을 계기로 피보나치라는 이름이 붙었다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55....이전의 두 숫자를 더해서 다음 숫자를 만드는 수열입니다.  이제 문제만 읽어도 아 이건 재귀 문제구나 느낌이 오죠?물론 재귀로만 이 문제를 풀 수 있는 것은 아닙니다만...알고리듬은 역시 재귀. 재귀가 제 맛 아니겠습니까? 재귀 1자 이제 코딩을 해봅시다. def fibonacci(a, b): print(a) return fibonacci(b, a+b)fibonacc..

정렬된 데이터에서 검색할 때는 이진(이분) 검색이 더 효율적입니다. 친구가 1부터 100까지 숫자 중 하나를 고르고, 나는 그 숫자를 맞추는 게임을 한다고 가정합니다. 친구는 "고른 숫자가 내가 제시한 숫자보다 크다, 작다, 맞다."를 대답해 줘야 합니다. 이때 가장 빨리 정답을 찾는 법은 절반인 50을 제시하는 것입니다. 여기서 친구가 작다고 하면 25를 불러보고... 한번 검색할 때마다 절반이 날아갑니다. 엄청난 효율이죠. 실제로 32라는 숫자를 찾아보겠습니다. 1. 50? 작아 2. 25? 커 3. 37? 작아 4. 31? 커 5. 34? 작아 6. 32? 정답 6번 만에 찾을 수 있습니다. from random import randint print("Guess the number!") secret..

자체 정렬 데이터 (self-organized data) 순차 검색 시 자주 검색하는 데이터를 앞부분에 저장해 검색 속도를 높이는 방법입니다. 검색될 때마다 앞쪽으로 한 칸씩 교환해 주면 됩니다. def search(item): for idx, element in enumerate(array): if element == item and idx > 1: array[idx], array[idx - 1] = array[idx-1], array[idx] print(idx-1, element) return idx-1 print('False') return False array = [4, 10, 0, 14, 5, 8, 15, 19, 9, 3, 2, 1, 12, 17, 16, 7, 13, 6, 18, 11] sear..

앞서 만들었던 3가지 정렬과 파이썬의 기본 정렬을 비교해 보겠습니다. 파이썬 내장 정렬 함수 비교 전에 파이썬의 내장 정렬 함수에 대해 살짝만 알아봅시다.... 어짜피 한 번은 다루고 넘어가야 하기 때문에... 파이썬의 내장 정렬은 array.sort()와 array = sorted(array)가 있습니다. array.sort()는 내부적으로 정렬합니다. array = sorted(array)는 새로운 리스트를 만들어 줍니다. 함수형으로 프로그래밍할 때는 sorted가 필요합니다. 공식 문서에는 새로운 리스트를 만드는 sorted 보다 sort가 더 효율적이라고 했는데, 테스트 결과는 그와 달라서 혼란스럽습니다. 데이터 셋이 작아서 그런가? 파이썬의 공식 문서도 한글화 되어 읽을만합니다. https://..

삽입 정렬은 손안에 카드를 정렬하는 방식과 유사합니다. [8, 5, 2, 4, 6] 카드가 있다면.. 첫 번째 카드는 해줄 게 없고, 두 번째 카드인 5를 뽑아서, 5보다 큰 카드는 pass 하고, 8 앞에 삽입하고... [5, 8, 2, 4, 6] 세 번째 카드인 2를 뽑아서, 2보다 큰 카드는 pass, 5 앞에 삽입하고... [2, 5, 8, 4, 6] 4를 뽑아서, ..., 5 앞에 삽입하고... [2, 4, 5, 8, 6] 8을 뽑지만, 8 앞은 8보다 작은 수만 있으니.... 바로 stop [2, 4, 5, 8, 6] 6을 뽑아서, 8 앞에 삽입합니다. [2, 4, 5, 6, 8] 원리는 뽑고 큰 수는 pass 하고 삽입이지만, 구현은 뽑고 큰 수는 밀고 삽입입니다. def insertion_..

불안정 정렬입니다. ([A1, A2]를 'A를 기준'으로 '숫자를 무시'하고 정렬했을 때 A1, A2의 순서가 바뀔 수 있습니다.) [A, B, A, C, A] 를 정렬하면 [A, A, A, B, C]가 되는데.. A,A,A 간 순서가 어떻게 되든 무슨 상관이냐 라고 생각할 수 있는데.. [A1, B2, A2, C1, A3] 의 경우 숫자를 기준으로 한번 정렬한 뒤, [A1, C1, B2, A2, A3] 문자를 기준으로 한번 정렬해서, [A1, A2, A3, B2, C1] 를 만들어야 할 경우도 있기 때문에 중요합니다. 1. 선택 정렬은 리스트의 첫 요소를 최저값으로 정한 뒤 2. 리스트의 끝까지 최저 값을 찾습니다. 3. 최저값이 있으면 최저값과 첫 요소를 교환합니다. 4. 첫 요소는 최저값이 되었으니..