컴퓨터과학 개론 06 - 알고리즘 (2)

해당 포스트는 강의를 수강 후 개인적으로 이해한 부분을 글로 기록하고 해석하기 위한 목적으로 이해한 부분이 틀릴수도 있습니다. 잘못 이해하고 있거나 틀린 부분에 대해서는 편하게 지적해 주시면 수정하겠습니다.

1. 정렬 알고리즘

1. 퀵 정렬

• 특정 데이터(피벗)를 기준으로 입력 배열을 두 부분배열로 분할하여 각 부분배열에 대해 퀵 정렬을 순환적으로 적용

  피벗, Pivot

  • 두 개의 부분배열을 분할할때 기준이 되는 데이터
  • 보통 주어진 배열의 첫 번째 원소로 지정

  1. 퀵 정렬의 특징

     1. 분할
        • 정렬할 n개의 데이터를 피벗을 중심으로 두 개의 부분배열로 분할
     2. 정복
        • 두 부분배열 각각에 대해 퀵 정렬을 순환적으로 적용하여 두 부분배열을 정렬
     3. 결합
        • 필요 없음

  2. 퀵 정렬의 성능

     • 분할 과정의 수행 시간 -> $O(n)$
     • 평균 수행 시간 -> $O(nlogn)$
     • 최선 수행 시간 -> $O(nlogn)$

  퀵 정렬은 피벗을 중심으로 항상 동일한 크기의 두 개의 부분배열로 분할되는 경우에 최선 수행 시간을 가진다.
  반대로 피벗의 값이 배열에서 항상 최댓값 또는 최솟값인 경우 최악의 수행 시간 $O(n^2)$을 가진다. 이미 정렬된 배열의 피벗을 첫 번째 원소로 지정하는 경우를 예로 들 수 있다.
  피벗 선택의 임의성만 보장되면 평균 수행 시간을 보일 가능성이 높다.

2. 합병 정렬

   • 동일한 크기로 두 개의 부분배열로 분할하고(분할), 각 부분배열을 순환적으로 정렬한 후 (정복), 정렬된 두 부분배열을 합병(결합)해서 하나의 정렬된 배열을 만드는 방식
   
   
   1. 과정
      • 배열을 더 이상 나눌 수 없는 지점까지 분할한 후 분할된 배열의 가장 첫번째 값들을 비교해가며 작은 값부터 순서대로 배열에 입력
   
   
   2. 특징
      1. 분할
         • 정렬할 n개의 데이터를 $n/2$개의 데이터를 갖는 두 부분배열로 분할
      2. 정복
         • 두 부분배열에 대해 합병 정렬을 각각 순환적으로 적용하여 정렬
      3. 합병
         • 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만든다.
   3. 성능
      • 합병 정렬의 성능은 최선, 최악, 평균 수행 시간 모두 $O(nlogn)$이다.

3. 탐색

   1. 순차 탐색, Sequential search

      • 리스트 형태로 주어진 데이터를 처음부터 하나씩 순서대로 비교하여 원하는 데이터를 찾는 방법
      
      
      1. 성능
         • $O(n)$
         • 실패하는 경우의 비교 횟수 -> n번
         • 성공하는 경우의 비교 횟수 -> 1 ~ n번 -> 평균 $\frac{n+1}{2}$번
      2. 특징
         • 데이터가 키값과 관련해서 아무런 순서 없이 단순하게 연속적으로 저장
         • 정렬되지 않은 데이터에 적합

   2. 이진 탐색, Binary search

      • 정렬된 입력 배열에 대해서 주어진 데이터를 절반씩 줄여가면서 원하는 데이터를 찾는 방법, 분할 정복 방법을 적용한 알고리즘
        
        
      1. 방법
         • 입력 배열의 가운데 값 A[mid]와 탐색키 key를 비교
      2. 성능
         • 한 번 탐색할 때마다 탐색 대상이 되는 데이터의 개수가 $1/2$씩 감소하여 $O(logn)$
      3. 특징
         • 데이터가 이미 정렬된 경우에만 적용 가능
         • 삽입/삭제 연산 시 정렬 상태의 유지를 위해 데이터 이동이 발생하여 동적 연산이 많은 응용에는 부적합

   3. 이진 탐색 트리, Binary search tree

      • 각 노드의 왼쪽 서브트리에 있는 모든 키 값은 그 노드의 키 값보다 작다.
      • 각 노드의 오른쪽 서브트리에 있는 모든 키 값은 그 노드의 키 값보다 크다.
      
      

      1. 탐색 연산

         • 루트 노드에서부터 키 값의 비교를 통해 왼쪽 또는 오른쪽 서브트리를 따라 이동하면서 데이터를 찾는다.
         
         

         1. 삽입 연산

            • 삽입할 데이터를 탐색한 후, 탐색이 실패한 위치에 새로운 노드를 자식 노드로 추가

         2. 삭제 연산

            • 후속자 노드, Successor, 계승자 노드
              : 어떤 노드의 키 값의 바로 다음 키 값을 갖는 노드

            • 삭제 되는 노드의 자식 노드의 개수에 따라 구분해서 처리
              1. 자식 노드가 없는 경우(리프 노드)
              2. 자식 노드가 1개인 경우
              3. 자식 노드가 2개인 경우

         3. 성능

            • 키 값의 비교 횟수에 비례
            • 트리의 높이가 최소 높이를 가지는 경우 평균 수행 시간 $O(logn)$이 되고 경사 이진 트리와 같은 최대 높이를 가지는 경우 최악 수행 시간 $O(n)$이 된다.