정렬

분할 정복법 (Divide and Conquer)
탐욕 알고리즘 (Greedy)
동적 계획법 (Dynamic Programming)
알고리즘 응용

정렬 알고리즘
선택 정렬, 거품 정렬, 삽입 정렬

 

 

분할 정복법 (Divide and Conquer)

그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법

ex)퀵 정렬, 합병 정렬, 이진 탐색 

분할된 문제는 서로 독립적이다.

분할된 작은 문제는 원래 문제와 성격이 동일하다 => 입력 크기만 작아짐

 

1) divide : 원래 문제를 분할하여 더 작은 하위 문제로 분할이 가능할 때까지 나눈다.

2) conquer: 하위 문제를 재귀적으로 해결

3)combine: conquer한 문제들을 통합하여 원래 문제의 답을 얻ㅇ 해결

 

장점

 

top-down재귀방식으로 구현해서 코드가 직관적

문제를 나누어 해결한다는 특징상 병렬적으로 문제 해결

 

단점

재귀 함수 호출로 오버헤드 발생

스택에 다량의 데이터가 보관되는 경우 오버플로우 발생

 

 

탐욕 알고리즘(greedy)

그리디 알고리즘 : 현재 상황에서 최적이라고 생각하는 해를 선택

but  현재 상황만 고려하기 때문에 항상 최적해를 보장하지는 않는다.

 

동적 계획법 (Dynamic Programming)

모든 작은 문제들을 한번만 푼다. 정답을 구한 작은 문제를 메모해 놓는다. 큰 문제를 풀어나갈때 똑같은 작은 문제가 나타나면 앞에 메모한 작은 문제의 결과값을 이용

-> 같은 문제는 구할 떄마다 정답이 같다. =/.작은 문제의 결과 값이 항상 같다는 점을 이용해 큰문제를 해결

-> 작은 문제가 반복이 일어남

메모이제이션:

작은 문제들이 반복되고 작은 문제들의 결과값이 항상 같다. 작은 문제를 저장해놓고 다시 사용하는 것

한번 계산한 결과를 메모리 공간에 메모하는 기법

같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.

 

 

동적계획법과 분할정복의 차이점: 하위 문제의 중복

하위 문제가 독립적이지 ㅏㄶ고 중복이 되는 경우에는 dp의 방식이 분할 정복보다 더 나은 시간복잡도를 가진다. 

이유는 분할정복에서는 동일한 하위문제는 각각 독립적으로 구성되어 있기 때문에 반복적으로 계산이 되지 않기때문에

분할적ㅇ복은 작은문제에서 반복이 일어나는 부분이 없다. 

동적계획법은 작은 부분문제들이 반복되는 것을 이용

 

 

선택정렬

데이터 하나를 기준으로 다른 데이터와 비교하여 작거나 큰 데이터와 자리를 바꾸는 식으로 

데이터 개수 n개일 시 n-1회 회전

 

https://wakestand.tistory.com/596

 

버블정렬

 

삽입정렬

2번째 원소부터 n번째 원소까지 차례로 해당 원소가 위치할 인덱스에 원소를 삽입하는 방식

 

참고자료

https://galid1.tistory.com/507

https://loosie.tistory.com/150?category=972195