clrs

1.Introduction- Chapter4 부터는 분할 정복(Divide & Conquer) 응용을 살펴보고, - 분할 정복 알고리즘을 분삭할 때 생기는 점화식을 딥하게 알아보고자 한다. 1.1. 분할 정복(Divide & Conquer)- 주어진 문제를 재귀적으로 해결한다.- Base case(Bottoms Out) 같은 경우 재귀 없이 직접 해결 하고- Recursive case같은 경우 다음과 같이 세가지 단계로 나누어 문제를 해결한다 1) Divide(분할) : 문제를 더 작은 동일 문제의 하위 문제로 나눔2) Conquer(정복) : 하위 문제를 재귀적으로 해결함3) Combine(결합) : 하위 문제의 해결책을 결합하여 원래 문제의 해결책을 만듬  1.2. Recurrences(점화식)- 재..

1. Introduction- 효율적인 알고리즘을 구현하기 위해 이 "효율"을 계산하기 위한 "시간 복잡도"에 대해서 알아보자 2. Big-O Notation - Big-O Notation은 함수의 상한을 나타낸다. - 즉 상한을 걸어두고, 그 함수는 상한에 걸어둔 Big-O Notation보다 특정 순간부터 증가하지 않음을 의미한다.(이 때 최고차항을 기준으로 나타낸다.)- 예를들어 다음과 같은 함수가 있다고 생각해보자.- f(x) = n^3 + 2n+1 --> O(n^3)이라고 나타낼 수 있다. - 하지만 O(n^4),O(n^5)로도 나타낼 수 있다. 그 이유는 f(x)는 n^4 , n^5보다 느리게 증가하기 때문이다.- 따라서 c>=3 을 만족할 때 O(n^c)로 Big-O Notation으로 표현..

1. Bubble Sort? - 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘--> 인접한 2개의 노드를 비교하여 크기순으로 서로 교환을 해준다. 2. 더 자세히!- 버블 정렬은 인접된 두 노드, 즉 (첫 번째, 두번째),(두 번째, 세 번째),(세 번째,네 번째)... 이런 식으로마지막 노드를 비교하여 교환하면서 데이터를 정렬한다.- 그림을 보면 더 쉽게 이해가능하다.- 반대로 마지막 부터 시작으로 역순으로 버블이 움직여도 괜찮다.(CLRS에선 역순으로 움직인다.) 3. Code(Python)def bubble_sort(arr,n): for i in range(n): for j in range(n,i,-1): if arr[j]  4. Bubble Sort의 시간..

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