ComDoc ComDoc

배낭 문제는 짐을 쪼갤 수 있느냐 없느냐로 나뉩니다. 쪼갤 수 있는 경우 분할 가능 배낭 문제라고 합니다. 배낭에 담을 수 있는 물건이 분할이 되면 쉽습니다. (금가루, 은가루, 철가루) 부피 (또는 무게) 대비 가치가 높은 물건들부터 담으면 되기 때문입니다. 이것을 탐욕(greedy) 알고리듬이라고 합니다. 부피 대비 가치가 높은 물건 순서대로 담으면 되고, 담을 때 '뒤에 어떤 물건을 넣을지' 고려하지 않아도 되기 때문에 붙여진 이름입니다. (탐욕스럽게) 비싼 것부터 막 넣어~! 어떤 행위가 나중에 어떤 영향을 미칠 지 생각하지 않고 현재 가장 이익이 되는 행위만 취해도 최고의 결과가 나올 때 사용하는 쉬운 알고리듬입니다. 동전 거스름돈의 경우도 대부분의 국가에서 탐욕 알고리듬으로 정답이 나오도록 되..

동적 프로그래밍((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_..