Algorithms

1. Introduction- 알고리즘은 다양하게 선택가능하다. - 예를들어 Insertion Sort는 Incremental method(증분 방법)을 사용한다.- 이번 챕터에선 분할 정복(divide and conquer) 이라는 설계 방법을 간단하게 다루게 된다. - 자세한 방법은 챕터 4때 알아보도록 하자. 2. Divide and Conquer(분할 정복)- 많은 유용한 알고리즘들은 재귀적(recursive) 구조를 가지고 있음.- 주어진 문제를 해결하기 위해, 이들은 스스로 한번 이상 호출하여 하위문제들을 해결함- 일반적으로 분할 정복(Divide & Conquer)을 따름- 문제를 원래 문제와 유사하지만 더 작은 크기의 여러 하위 문제로 나누고, - 하위 문제를 재귀적으로 해결한 뒤 이러한 ..

1. Introduction- 앞서 1-1 에 설명했던 Sorting Problem을 풀기위해 삽입 정렬(Insertion Sort)를 알아보자. 2. Insertion Sort- 적은 수의 요소를 정렬하는 데 효율적인 알고리즘- 카드를 한손에 들고 정렬하는 방식과 유사- 각 숫자를 적절한 위치에 삽입하는 방법을 의미함- 파이썬으로 해당 알고리즘을 구현한 걸 함께 살펴보자.(parameter는 2개 / 배열, 배열길이)def insertion_sort(A,n): for i in range(1,n): key = A[i] j = i-1 while j >=0 and A[j] > key: A[j+1] = A[j] j -=1 ..

1. Introduction- 컴퓨터가 무한히 빠르고 메모리 비용이 들지 않는다고 가정하자.- 컴퓨터가 무한히 빠르면 어떤 문제를 해결하는 알고리즘들은 전부 무한히 빠를 것이다.- 따라서, 어떤 기법이든 가장 쉽게 구현할 수 있는 것을 자주 사용하게 된다.- 하지만 컴퓨터는 엄청 빠를 순 있지만, 무한히 빠를 수 없다. 마찬가지로, 메모리도 매우 저렴하 순 있지만, 비용이 전혀 들지 않을 수 없다. - 결국 우리는 가장 효율적인 알고리즘과 자료구조를 찾아야만 한다.  2. 효율성- 동일한 문제를 해결하기 위한 알고리즘이 효율성 면에서 극적으로 다를 수 있다.- 잘 설계된 알고리즘은 효율성이 낮은 알고리즘보다 계산/시간적인 차원에서 문제의 크기가 커질수록 그 상대적인 장점도 커진다 - 알고리즘에 대한 지식..