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

선형시간 정렬 알고리즘

선형시간: O(n)

Counting Sort

• n개의 정수를 정렬하라. 단 모든 정수는 0에서 k사이의 정수이다.(사전지식)

• 예: n명의 학생들의 시험점수를 정렬하라. 단 모든 점수는 100이하의 양의 정수이다.

int A[n];
int C[k] = {0,};
for(int i = 1; i <= n; i++){
  C[A[i]]++;
}
for(int s = 1, i = 0; i <= k; i++){
  for(int j = 0; j < C[i]; j++){
    A[s++] = i;
  }
}

그러나 대부분의 경우 정렬할 key 값들은 레코드의 일부분이기 때문에 위와 같이 정렬할 데이터를 정수 값으로 보는 방식은 실제로 유용한 방식은 아니다.

수도코드

Counting-Sort(A,B,k)
  for i <- 0 to k
    do C[i] <- 0
  for j <- 1 to length[A]
    do C[A[j]] <- C[A[j]] + 1
  > C[i] now contains the number of elements equal to i.
  for i <- 1 to k
    do C[i] <- C[i] + C[i - 1]
  > C[i] now contains the number of elements less than or equal to i.
  for j <- length[A] downto 1
    do B[C[A[j]]] <- A[j]
      C[A[j]] M- C[A[j]] - 1

• Θ(n+k), 또는 Θ(n) if k =O(n).

• k가 클 경우 비실용적

• Stable 정렬 알고리즘

  • “입력에 동일한 값이 있을때 입력에 먼저 나오는 값이 출력에서도 먼저 나온다.”
  • Counting정렬은 stable하다.

오늘 한일

• 알고리즘 강의의 선형시간 정렬에 대해 공부했다. (포스팅)

• 인프런을 통해 생활코딩의 “웹브라우저 Javascript (자바스크립트)” 공부를 했다.

오늘 느낀점

• 알고리즘 공부 외에 무엇을 추가로 할지에 대한 여러가지 선택 중에 프로젝트를 진행 할려다가, 아무래도 프론트단을 모르다보니 지나치게 많은 시간을 쏟았던 경험들이 떠올라 빠르게 자바스크립트의 기본을 보기로 결정하였다.

• html과 css는 제대로 공부해 본적이 없고, 생활코딩의 웹애플리케이션 만들기 강의를 본게 다여서 자신이 없었는데 최근 기간동안 여러번 접하다보니 어느정도 구조가 눈에 보인다. 특히나 최근에 호눅스의 추천으로 읽었던 “데이타베이스론”에 나온 xml의 dom구조 덕에 html의 구조가 더 쉽게 파악된다. (애초에 html 자체는 어려울게 없는거지만…)

내일 할일

• 알고리즘 강의 듣기

• 자바스크립트 공부(총 열시간의 강의인데 오늘 포함 이틀 혹은 삼일 안에 끝내자)

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

Comparison Sort

• 데이터들간의 상대적 크기관계만을 이용해서 정렬하는 알고리즘

• 따라서 데이터들간의 크기 관계가 정의되어 있으면 어떤 데이터에든 적용 가능(문자열, 알파벳, 사용자 정의 객체 등)

• 버블소트, 삽입정렬ㄹ, 합병정렬, 퀵소트, 힙정렬 등

Non-comparison sort

• 정렬한 데이터에 대한 사전지식을 이용 - 적용에 제한

• Bucket sort

• Radix sort

하한(Lower bound)

• 입력된 데이터를 한번씩 다 보기위해서 최소 Θ(n)의 시간복잡도 필요

• 합병정렬과 힙정렬 알고리즘들의 시간복잡도는 Θ(nlogn)

• 어떤 comparison sort알고리즘도 Θ(nlogn)보다 나을수 없다.

decision_tree

(1,2,3의 의미는 숫자 값이 아니라 정렬할 데이터들의 첫번째, 두번째 값을 의미)

• Leaf노드의 개수는 n!개
  왜냐하면 모든 순열(permutation)에 해당하므로

• 최악의 경우 시간복잡도는 트리의 높이

• 트리의 높이는

  • height >= logn! = Θ(nlogn)

오늘 한일

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

  • 리팩토링

  • 유저 목록을 보여주는 페이지 제작

• 알고리즘 강의의 정렬의 lower bound에 대해 공부했다. (포스팅)

오늘 느낀점

• JSP, Servlet 복습이 일단 마무리 됐다.

  • 복습을 시작하면서 JSP & Servlet에 대한 포비의 영상이 있어 해당 영상을 참조해가면서 복습을 했었는데, 해당 영상엔 없던 유저 목록을 보여주는 페이지도 제작 해봄으로 어느정도 복습이 마무리 됐다.

  • JSP, Servlet 자체는 어느정도 익숙해진 감이 있는데 JDBC 쪽, DB와 연동하는 부분들이 아직은 수월하지 않다.

  • 좀더 정확히 표현하면 한가지 기술에 종속적이다. 기능 추가가 필요하면 가능 하지만, 현재 구축한 방식의 기술 말고 다른 기술로 바꿀 필요가 있으면 어떻게 바꿔야 할지 감이 덜 잡힌다.

• 내일부터는 무엇을 공부 할지 고민을 해보자(아래는 선택지)

  1. 프론트엔드쪽 공부로 자바스크립트를 본다.

  2. 파이썬, 장고 강의를 본다.

  3. 이전 부터 사용하던 서비스라 프로젝트로 만들어 보고 싶었던 샌드애니웨어같은 형태의 웹앱을 만들어본다.

  4. 혹은 다른 무언가 할것이 없나 생각해보자.

내일 할일

• 알고리즘 강의 듣기

• 자바스크립트 공부 혹은 생각하고 있던 프로젝트 시작(아니면 다른 무언가..)

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

힙의 응용: 우선순위 큐

• 최대 우선순위 큐(maximum priority queue)는 다음의 두 가지 연산을 지원하는 자료 구조

  • INSERT(x): 새로운 원소 x를 삽입

  • EXTRACT_MAX(): 최대값을 삭제하고 반환

• 최소 우선순위 큐 (minimum priority queue)는 EXTRACT-MAX 대신 EXTRACT-MIN을 지원하는 자료구조

• MAX HEAP을 이용하여 최대 우선순위 큐를 구현

FIFO: 먼저 들어온 값이 우선순위가 높은 큐

이번 예제에서는 값 자체를 우선순위라고 본다.(큰 값이 더 우선순위가 높다고)

INSERT

INSERT(x): 새로운 원소 x를 삽입

수도코드

HEAP-INSERT(A, key){
  heap_size = heap_size+1;
  A[heap_size] = key;
  i = heap_size;
  while( i > 1 and A[PARENT(i)] < A[i]){
    exchange A[i] and A[Parent(i)];
    i = PARENT(i);
  }
}

시간복잡도 : O(logn)

시간복잡도는 트리의 높이(LEVEL)에 비례한다.

EXTRACT_MAX()

EXTRACT_MAX(): 최대값을 삭제하고 반환

1. 가장 큰 값인 root의 값을 반환.

2. 가장 마지막 노드를 root로 옮긴다.

3. HEAPIFY를 한다.(현재는 MAX-HEAPIFY)

수도코드

HEAP-EXTRACT-MAX(A)
  if heap-size[A] < 1
    then error "heap underflow"
  max <- A[1]
  A[1] <- A[heap-size[A]]
  heap-size[A] <- heap-size[A] - 1
  MAX-HEAPIFY(A,1)
  return max

시간복잡도 : O(logn)