인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 보고 작성한 문서입니다.

분할정복법

• 분할 배열을 다음과 같은 조건이 만족되도록 두 부분으로 나눈다.

  elements in lower parts <= elements in upper parts

• 정복: 각 부분을 순환적으로 정렬한다.

• 합병: nothing to do

수도코드

quickSort(A[], p, r){
  if(p<r) then {
    q = partition(A, p, r); //분할
    quickSort(A, p, q-1);   //왼쪽 부분배열 정렬
    quickSort(A, q+1, r);   //오른쪽 부분배열 정렬
  }
}

partition(A[], p, r){
  배열 A[p...r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고
  A[r]이 자리한 위치를 return 한다;
}

partition 메소드

• x = pivot 값

• pivot의 위치는 고정 하고 i를 기준으로 작은 값, 큰 값을 분류한다.

수도코드

Partition(A, p, r){
  x <- A[r];
  i <- p-1;
  for j<- p to r-1
  if A[j] <= x then
    i <- i+1;
    exchange A[i] and A[j];
  exchange A[i+1] and A[r];
  return i+1;
}

최악의 경우

• 항상 한 쪽은 0개, 다른 쪽은 n-1개로 분할되는 경우

  

• 이미 정렬된 입력 데이터 (마지막 원소를 피봇으로 선택하는 경우)

최선의 경우

• 항상 절반으로 분할되는 경우

  

퀵소트가 대체적으로 더 빠른 이유

• 일반적으로 최악과 최선의 경우처럼 극단적인 상황은 많지 않다.

• 극단적인 경우만 아니면 “nlogn”의 복잡도로 수렴한다.(위와 같이 1/9만 돼도)

평균시간복잡도

• “평균” 혹은 “기대값”이란?

  

빠른정렬(quicksort) 평균시간복잡도

Pivot의 선택

• 첫번째 값이나 마지막 값을 피봇으로 선택

  • 이미 정렬된 데이터 혹은 거꾸로 정렬된 데이터가 최악의 경우

  • 현실의 데이터는 랜덤하지 않으므로 (거꾸로) 정렬된 데이터가 입력으로 들어올 가능성은 매우 높음

  • 따라서 좋은 방법이라고 할 수 없음

• “Median of Three”

  • 첫번째 값과 마지막 값, 그리고 가운데 값 중에서 중간값(median)을 피봇으로 선택

  • 최악의 경우 시간복잡도가 달리지지는 암ㅎ음

• Randomized Quicksort

  • 피봇을 랜덤하게 선택

  • no worst case instance, but worst case execution (누가 pivot이 될지 정해져있지 않아서 최악의 case가 미리 존재할 수 없다. 하지만 랜덤 선택의 운이 안좋으면 최악의 경우를 실행 시킬 수 있다.)

  • 평균 시간복잡도 O(NlogN)

오늘 한일

• 화이트 코스때 스프링부트로 구현 했던 작업물을 JSP, Servlet을 이용하여 구현.

  • Hibernate Validator를 사용한 유효성 체크 테스트 코드 작성.

  • 중복 되는 코드들을 SessionUtils 클래스로 만들어 중복 제거.

• 알고리즘 강의의 빠른정렬(quick sort)에 대해 공부했다. (포스팅)

내일 할일

• JSP, Servlet으로 웹애플리케이션 구현하기

• 알고리즘 강의 듣기

인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 보고 작성한 문서입니다.

분할정복법

• 분할

  해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할

• 정복

  각각의 작은 문제를 순환적으로 해결

• 합병

  작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함

합병정렬(merge sort)

1. 데이터가 저장된 배열을 절반으로 나눔

2. 각각을 순환적으로 정렬

3. 정렬된 두 개의 배열을 합쳐 전체를 정렬

수도코드

mergeSort(A[], p, r){
  if(p < r) then {
    //p, r의 중간 지점 계산
    q <- (p+r)/2;
    //전반부 정렬
    mergeSort(A, p, q);
    //후반부 정렬
    mergeSort(A, q+1, r);
    //합병
    merge(A, p, q, r);
  }
}

merge(A[], p, q, r){
  정렬되어 있는 두 배열 A[p...q]와 A[q+1..r]을 합하여
  정렬된 하나의 배열 A[p...r]을 만든다.
}

java코드

void merge(int data[], int p, int q, int r){
  int i =p, j=q+1, k=p;
  int[] tmp = new int[data.length];
  while(i <= q && j <= r){
    if(data[i] <= data[j]){
      tmp[k++] = data[i++];
    } else{
      tmp[k++] = data[j++];
    }
  }
  while(i <= q){
    tmp[k++] = data[i++];
  }
  while(j <=r){
    tmp[k++]=data[j++];
  }
  for(int i = p; i <= r; i++){
    data[i] = tmp[i];
  }
}

시간 복잡도

오늘 한일

• 화이트 코스때 스프링부트로 구현 했던 작업물을 JSP, Servlet을 이용하여 구현.

  • junit을 통한 test 코드를 작성하며 crud 기능 추가

  • 개인정보 수정 기능 구현

• 알고리즘 강의의 합병정렬(merge sort)에 대해 공부했다. (포스팅)

내일 할일

• JSP, Servlet으로 웹애플리케이션 구현하기

• 알고리즘 강의 듣기

인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 보고 작성한 문서입니다.

정렬

비교적 간단하지만 느린 정렬들

• Bubble sort

• Insertion sort

• Selection sort

복잡하지만 조금더 빠른 정렬

• Quicksort

• Merge sort

• Heap sort

근본적으로 다른 정렬

• Radix sort

Selection sort(선택 정렬)

• 순서

  1. 가장 큰 값을 찾는다.

  2. 마지막 자리와 자리를 바꾼다.

  3. 다음 큰 값을 찾는다.

  4. 마지막 이전 자리와 자리를 바꾼다.

  5. 마지막 하나가 남을때 까지 반복…

  6. 끝

수도코드

selectionSrot(A[], n){
  //1
  for last <- n downto 2{
    //2
    A[1...last] 중 가장 큰 수 A[k]를 찾는다;
    //3
    A[k] <-> A[last];
  }
}

• 실행시간:

  1. for 루프틑 n-1번 반복

  2. 가장 큰 수를 찾기 위한 비교 횟수: n-1, n-2,…,2,1

  3. 교환은 상수시간 작업

• 시간복잡도

  T(n) = (n-1) + (n-2) + … + 2 + 1 = O(n*n)

최악, 최선, 평균의 복잡도가 동일

Bubble sort(버블정렬)

기본 아이디어는 선택정렬이랑 유사하다.

• 순서

  1. 첫번째와 두번째 값과 비교한다.

  2. 첫번째 값이 더 크면 자리를 바꾼다.

  3. 두번째 값과 세번째 값을 비교한다.

  4. 두번째 값이 더 크면 자리를 바꾼다.

  5. 반복

  6. n-1번째 값과 n번째 자리를 비교한다.

  7. n-1번째 값이 더 크면 자리를 바꾼다.

  8. n번째를 빼고, n-1번째 까지 1~7번 작업을 반복한다.

수도코드

bubbleSort(A[], n){
  //1
  for last <- n downto 2{
    //2
    for i <- 1 to last-1{
      //3
      if(A[i] > A[i+1]) then A[i] <-> A[i+1];
    }
  }
}

• 수행시간:

  1. for 루프는 n-1번 반복

  2. for 루프는 각각 n-1, n-2,…,2,1번 반복

  3. 교환은 상수시간 작업

• 시간복잡도

  T(n) = (n-1) + (n-2) + … + 2 + 1 = O(n*n)

최악, 최선, 평균의 복잡도가 동일

Insertion Sort(삽입정렬)

• 순서

  1. 두번째와 첫번째를 비교하여 정렬한다.

  2. 세번째와 앞의 정렬이 된 배열과 비교하여 정렬한다.

  3. 네번째와 앞의 정렬이 된 배열과 비교하여 정렬한다.

  4. n번째와 앞의 정렬이 된 배열과 비교하여 정렬한다.

• n번째의 데이터를 배열과 비교할때 앞에서부터 비교하는 것보단 뒤에서부터 비교하는게 더 효율 적이다.

  • 앞에서부터 비교하면 아래와 같이 작업 한다.

    1. 앞에서부터 비교

    2. 뒤의 데이터들을 이동

  • 뒤에서부터 비교하면 아래와 같다.

    1. 뒤에서부터 비교하며 더 큰 값은 뒤로 이동시키며 자신의 자리를 찾는다.

  • 차이점은 앞에 있는 데이터들을 비교하지 않아도 되서 더 효율적이다.

수도코드

insertionSort(A[], n){
  //1
  for i <- 2 to n{
    //2
    A[1...i]의 적당한 자리에 A[i]를 삽입한다.
  }

}

• 수행시간:
  1. for 루프는 n-1번 반복
  2. 삽입은 최악의 경우 i-1번 비교
• 최악의 경우:
  T(n) = (n-1) + (n-2) + … + 2 + 1 = O(n*n)

최악의 경우는 선택,버블 정렬이랑 동일하지만 최선의 경우는 n-1 이다.