알고리즘의 설계

루프 불변성

• 점진적인 방법에서 활용 가능하다.
• For 나 While 등 루프를 돌아도 변하지 않는 조건
• 알고리즘이 타당한 이유를 쉽게 이해할 수 있게 사용된다.
• 세가지 특징이 있다.
  1. 초기조건 : 첫번째 반복을 시작하기 전에 루프 불변성이 참이여아한다.
  2. 유지조건: 다음 반복이 시작되기 전까지도 계속 참이여야 한다.
  3. 종료조건: 루프가 종료될 때 그 불변성이 알고리즘의 타당성을 보이는데 도움이 될 유용한 특성을 가져야 한다.
• 귀납법과 비슷하다.
  1. 베이스가 참임을 보임
  2. 귀납적 과정을 증명함
  +. 마지막으로 알고리즘의 타당성을 보이는 것이 중요
• 정렬 알고리즘을 풀기로 했으면 루프 불변성이 마지막에 정렬된 수열을 나타내야 하는 것.

분할 정복

• 재귀적 구조를 가진 알고리즘 중 하나
• 세단계
  1. 분할: 현재 문제를 같은 문제를 다루는 다수의 부분 문제로 분할한다.
  2. 정복: 부분 문제를 재귀적으로 풀어서 정복한다. 크기가 충분히 작으면(베이스) 직접적인 방법으로 푼다.
  3. 결합: 부분 문제의 해를 결합하여 원래 문제의 해가 되도록 만든다.
• 예시(Merge sort)
  1. 분할: 정렬할 n개 원소의 배열을 n/2개씩 부분 수열 두개로 분할한다.
  2. 정복: 병합 정렬을 이용해 두 부분 배열을 재귀적으로 정렬한다.
  3. 결합: 정렬된 두 개의 부분 배열을 병합해 정렬된 배열 하나로 만든다.
  • 의사코드

  Merge-sort(A,p,r) # 정복
  if p <r
  	q = int(p+r)/2
  	Merge-sort(A,p,q)  # 분할 1
  	Merge-sort(A,q+1,r) # 분할 2
  	Merge(A,p,q,r) # 결합
  

• 분할 정복의 시간 복잡도 분석도 분할, 정복, 결합 별로 복잡도를 분석하여 최대 차수에 의해 결정된다.

---

출처

Introduction to algorithm 3rd edition