[알고리즘] Hello Coding 알고리즘 (재귀, 퀵 정렬)

[ 3장 재귀]

• 재귀를 쓴다고 성능이 더 나아지지는 않는다. 사실 반복문이 더 성능이 좋은 경우가 많다.
• 프로그램에 반복문을 사용하면 프로그램의 성능을 향상시킬 수 있지만, 재귀를 사용하면 프로그래머의 능력을 향상시킬 수 있다. 상황에 따라 적절한 방법을 골라 사용해야 한다.
• 대부분의 중요한 알고리즘들이 재귀를 사용하므로 개념을 잘 이해해야 한다.

 

[ 3장 요약 ]

• 재귀는 함수가 스스로를 호출하는 것이다.
• 모든 재귀 함수는 기본 단계와 재귀 단계라는 두 부분으로 나누어져 있다.
• 스택에는 push와 pop이라는 두 가지 연산이 있다.
• 모든 함수 호출은 호출 스택을 사용한다.
• 호출 스택은 너무 커져서 메모리를 엄청나게 소비할 수도 있다.​

---

[4장 퀵 정렬]

분할 정복

• 문제 해결 방법 중에서 가장 유명한 재귀적 기술.

1. 가장 간단한 경우로 기본 단계를 찾는다.
2. 주어진 문제를 작게 줄여서 기본 단계가 되도록 만드는 법을 찾아낸다.

• • 배열을 포함하는 재귀 함수를 만들 때, 기본 단계는 보통 빈 배열이나 원소가 하나뿐인 배열이 된다.
  • 반복문으로 풀 수 있는데도 굳이 재귀적으로 푸는 이유 : 하스켈과 같은 함수형 프로그래밍 언어에는 반복문이란 것이 없다. 그러니 무조건 재귀 함수를 사용해야만 함.

 

퀵 정렬 

• 퀵 정렬은 분할 정복 전략을 사용한다.
• 가장 빠른 정렬 방법 중의 하나이고, 분할 정복의 좋은 예. 선택 정렬보다 훨씬 빠르고 실제로도 자주 사용된다.
• 기본 단계는 정렬할 필요도 없는 정렬로, 비어 있는 배열이나 원소가 하나인 배열이다.
  배열을 있는 그대로 반환하면 됨.
  
  • 분할
    1. 기존 원소보다 작은 숫자들로 이루어진 하위 배열
    2. 기준 원소
    3. 기준 원소보다 큰 숫자들로 이루어진 하위 배열
  • 정렬
    • 하위 배열들이 정렬되어 있으면 왼쪽 배열 + 기준 원소 + 오른쪽 배열과 같이 배열들을 합친다.
    • 하위 배열들을 정렬하는 방법
      1. 기준 원소를 고른다.
      2. 배열을 기준 원소보다 작은 원소의 배열과 기준 원소보다 큰 원소의 배열, 이렇게 두 개의 하위 배열로 분할한다.
      3. 하위 배열에 대해 재귀적으로 퀵 정렬을 호출한다.
      4. 이러한 식으로 정렬한다면, 5개의 원소, 6개, 7개, 그 이상의 배열도 정렬할 수 있음.

 

[ 4장 요약 ]

• 분할 정복은 문제를 더 작은 조각을 나누어 푼다.
  만약 리스트에 분할 정복을 적용한다면 기본 단계는 원소가 없는 빈 배열이거나 하나의 원소만 가진 배열이 된다.
• 퀵 정렬을 구현하려면 기준 원소를 무작위로 선택한다. 퀵 정렬의 평균적인 실행 시간은 O(n log n)이다.
• 빅오 표기법에서 가끔씩 상수가 중요해질 때도 있다. 퀵 정렬이 병합 정렬보다 빠른 이유도 상수 때문.
• 단순 탐색과 이진 탐색을 비교할 때는 상수항이 전혀 문제가 되지 않는다.
  왜냐하면 리스트가 길어지면 O(log n)이 O(n)보다 훨씬 빨라지기 때문이다.

---

[ 출처, 참고 : Hello Coding 알고리즘 ]