ITeus

이번 포스팅은 욕심쟁이 방법론 입니다. 욕심쟁이 방법론은, 작은 문제에 대한 최선의 선택을 하는 알고리즘 방법론입니다. 무슨소리인지 감이 잘 안옵니다. 아래 예시를 보겠습니다. 1달러당 무게가 1이라고 가정해 봅시다. 이때 집게사장님은 욕심쟁이 이기 때문에, 무조건 큰 돈은 우선으로 줍습니다. 그러면 5달러를 모두 담고, 남은 공간에 3달라를 담는것이 주어진 상황에서 최선의 선택이겠죠? 하지만 이렇게 하면 최적의 이익을 얻을 수는 없습니다. 욕심쟁이 방법론은 동적 프로그래밍 방법론과 유사하게 작은 소문제에 대한 해를 찾아서, 전체 문제의 해를 찾는 알고리즘 계획 방법론입니다. 동적프로그래밍 방법론은 이전 단계의 최적해를 기억해서 전체 문제의 최적해를 찾는다면 욕심쟁이 방법론은 욕심을 부려서 모든 소문제의..

이번 포스팅은 동적 프로그래밍 방법론입니다. 방법론의 이름을 들으면 "??? 대체 무슨 방법론이야?" 라는 생각이 듭니다. 이름을 그대로 해석하면 이해를 할수가 없습니다. 동적 프로그래밍 방법론은 동적 계획법이라고 불리며 국소해를 저장하는 Table을 구축하고, 국소해를 저장/사용하는 알고리즘 방법론을 의미합니다. 아래 피보나치 수열을 구하는 방법을 보겠습니다. (너무 유명한 예제이지만, 이것만큼 숙련된 조교도 없습니다) #분할정복 방법을 사용한 피보나치수열을 구하는 함수 def fib_div(n): if n == 1: return 1 elif n == 0: return 0 result = fib_div(n-1) + fib_div(n-2) return result #동적 프로그래밍 방법을 사용한 피보나치..

이번 포스팅은 알고리즘을 설계하는 방법 중 분할정복 방법에 대한 포스팅입니다. 분할정복이란 글자 그 자체로 이해하면 편합니다. 1. 분할 : Data를 분할한다. 2. 정복 : 분할된 Data에 알고리즘을 적용한다. 3. 결합 : 정복단계의 알고리즘 결과를 취합한다. 위 3단계를 거쳐서 알고리즘이 수행되는 단계를 거치는 알고리즘 설계기법입니다. (단, 3단계 결합이 빠지는 경우도 분할정복 방법론으로 봅니다) 분할정복을 사용하는 알고리즘으로는 이진탐색, 퀵정렬, 합병정렬등을 예로 들 수 있습니다 이진 탐색을 예로 볼까요? 위 이진탐색의 내용을 다시 보겠습니다. 정복에서 알고리즘이 종료되지 않는다면 분할 단계에서 받은 부분배열에서 또다시 부분배열을 나누게 됩니다. 원하는 수준으로 작은 Data가 나오기 전까..

이번 포스팅은 가장 기초적이면서 원시적인 알고리즘 설계 방법론입니다. 이름하야 Brutal 방법론. 한국어로는 대충 단순방법론 이라고 할수있겠네요 ^_^;; 가장 쉬운 설게방법 이면서, 일반적으로 최고의 비효율을 보여줍니다. 탐색 알고리즘을 예로 들어보겠습니다. def find_value(list, value): for i in list: if i == value: return Ture find_value([9,4,8,7,5,3,1,2,1,64,9,7,6,2,6,3,4,8,99],99) 위 같은경우 Element가 n개 있을 경우 n개의 모든 원소에 대해서 처음부터 순차적으로 찾는 값과 동일한지 여부를 확인하는 알고리즘 입니다. 동일한 비교문을 n개의 Element에 적용하기 때문에 시간복잡도로 보면 O..

알고리즘의 경우 알고리즘에 들어가는 데이터의 수와 알고리즘의 구성 또는 해당 알고리즘을 실행하는 컴퓨터에 따라서 알고리즘 수행시간이 유동적으로 나타납니다. 이때, 동일한 동직을 수행하는 알고리즘 끼리 성능을 어떻게 비교할까요? 이번 포스팅은 알고리즘의 점근성능에 대한 내용입니다. 1. 점근성능 알고리즘의 점근 성능이란, 실제 수행시간은 아니지만 해당 알고리즘의 성능을 대변하는 수치를 의미합니다. 알고리즘의 점근성능을 이야기할 때 몇가지를 가정합니다. 1. 일반 사칙연산이나 비교문은 동일한 시간이 소요된다.(Data와 상관없이 상수시간이 소요된다) 2. 알고리즘의 수행시간은 최고차항의 영향이 지배적이다. 아래 예시 알고리즘을 살펴보겠습니다. #숫자를 입력받아, nxnxn 행렬을 만드는 알고리즘 입니다. d..