아이효 6. 알고리즘 수업

<알고리즘 설계법>

• 입력 --> 알고리즘 --> 출력.
• 알고리즘은 길인데, 어떻게 입력에서 출력으로 길을 찾을까?

유명한 알고리즘 설계법

1. 완전탐색(naive, brute force): 모든 경우의 수를 다 해보는 방법. (Ex. 자물쇠 비밀번호 찾기.)

2. 분할정복(Divide & conquer): 나누고, 정복하고, 합치는 방법.

   문제에 입력과 출력을 정의해줄 때 문제 파악이 어렵다면, 
   문제를 작은 조각으로 나눠보고(Ex. merge sort),
   그 작아진 문제를 정복(solve)하고,
   푼 문제들을 합쳐서(combine) 원래 문제를 해결한다.
   --> O(n log n)으로 일반적인 O(n^2)보다 빠름. ```

3. DP(Dynamic Programming): 문제가 어려우면 우선 세부적으로 나누는 것이 주 아이디어. 분할정복과의 차이점은 memorization(저장해두고 나중에 참조)을 함.
   ..--> 중복된 문제를 풀지 않게 도와줌.

   Ex. 피보나치 수열에서의 문제

   • 이전의 두개의 항의 합이 다음 항.
   • 종료조건 필수(아니면 메모리 터짐;;)
   • 시간복잡도는 O(2^n): 계속되는 서브 트리 반복 = 같은 계산 반복.
     ..--> 이 문제 방지를 위해 DP.
   • DP 방법을 사용하면 O(n)이 됨.

4. Greedy method(탐욕법):

• 최적화 문제(가장 좋은 답을 찾는 것.)
• 현재 상태에서 가장 좋은 것을 고르면 끝.

  Ex. 동전 문제

  • 거스름돈을 줄 때, 가장 적은 동전의 개수는 어떤 것인가?
  • 현재 상태에서 가장 큰 것만 선택하고 이전의 것들은 생각하지 않음.
  • 단, 체계에 따라 답이 달라질 수 있음.
  • '현재 최적해가 최종 최적해'라는 가정이 들어가고 반드시 이를 증명해야 함.

• 반복(iteration)과 재귀(self)는 호환됨. 다만 재귀 코드짜기가 쉬움. 성능은 반복이 더 좋음.
• 반복은 상향식 방식, 재귀는 하향식 방식.