ComDoc ComDoc

피보나치 수(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. 첫 요소는 최저값이 되었으니..

다양한 소팅을 애니메이션으로 보여줍니다. 볼만합니다. https://www.toptal.com/developers/sorting-algorithms Sorting Algorithm Animations Animation, code, analysis, and discussion of 8 sorting algorithms on 4 initial conditions. www.toptal.com 미리 알아야할 지식 파이썬에서는 2개의 변수의 값을 교환할 때 a, b = b, a를 쓸 수 있습니다. 다른 프로그래밍 언어에서는 temp를 동원해서 temp = a a = b b = temp 를 사용하는 것에 비해 상당히 간편합니다. 무식한 정렬법 다들 처음 정렬을 배울 때 이런 식의 무식한 정렬 알고리듬 하나씩 만들어..

위상 정렬(topological sorting)이란 방향성(유향) 그래프의 모든 방향성 간선이 한쪽을 가리키도록 모든 정점을 배치하는 방법입니다. 위키에는 다음과 같이 설명합니다. ㅇㅇ 같은 말입니다. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 쉽게 말해서 위 그래프를 빠지지 않고 모두 이수할 수 있도록 순서를 정하는 것이 위상 정렬입니다. 입학 -> 개론 -> (어셈블리) -> 자료구조 -> 운영체제 -> 알고리듬 입학 -> 개론 -> 자료구조 -> (어셈블리) -> 운영체제 -> 알고리듬 입학 -> 개론 -> 자료구조 -> 운영체제 -> (어셈블리) -> 알고리듬 입학 -> 개론 -> 자료구조 -> 운..