오늘 한일

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

  • DAO 리팩토링 작업

• 알고리즘 강의의 힙의 응용으로 우선순위 큐(priority queue)에 대해 공부했다. (포스팅)

내일 할일

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

• 알고리즘 강의 듣기

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

Heapsort

• 주어진 데이터로 힙을 만든다.

  수도코드

  

• 힙에서 최대값(루트)을 가장 마지막 값과 바꾼다.

• 힙의 크기가 1 줄어든 것으로 간주한다. 즉, 가장 마지막 값은 힙의 일부가 아닌 것으로 간주한다.

• 루트노드에 대해서 HEAPIFY(1)한다.

• 2~4번을 반복한다.

가장 큰 수부터 배열의 뒷자리를 차지하며 정렬이 된다.

수도코드

오늘 한일

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

  • 기존의 일반적인 이클립스 프로젝트를 maven 프로젝트로 변경 하였다.

  • 그 과정에서 경로 등의 문제들로 생각 보다 오래 걸렸다.

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

내일 할일

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

• 알고리즘 강의 듣기

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

Heap과 Heapsort

• 최악의 경우 시간복잡도 O(nlogn)

• Sorts in place - 추가 배열 불필요

• 이진 힙(binary heap) 자료구조를 사용

Heap은

• compleate binary tree이면서

• heap property를 만족해야한다.

Full v.s Complete Binary Trees

• Level

  부모로부터 몇칸 떨어져 있는가

힙은 일차원 배열로도 표현 가능하다

complete binary 트리이기때문에 인덱스를 통해 누구의 자식인지 알수 있다.

---

MAX-HEAPIFY

• 힙이라는 자료구조를 다루기 위한 필요한 기본연산.

• 전체가 heap을 만족하도록 각 노드들의 위치를 조정하는 과정.

• 자식의 값보다 부모의 값이 더 작으면 더 큰 자식과 부모를 바꿔가며 heap을 만족해 나간다.

수도코드

• recursive version

  MAX-HEAPIFY(A, i){
    if there is no child of A[i]{
      return;
    }
    k <- index of the biggest child of i;
    if A[i] >= A[k]{
      return;
    }
    exchange A[i] and A[k];
    MAX-HEAPIFY(A, k);
  }
  

  (root 노드에 대한 heapify는 MAX-HEAPIFY(1)을 호출하면 된다.)

• iterative version

  MAX=HEAPIFY(A, i){
    while A[i] has a child do{
      k <- index of the biggest child of i;
      if A[i] >= A[k]{
        return;
      }
      exchange A[i] and A[k];
      i = k;
    }
    end.
  }
  

오늘 한일

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

  • Hibernate Validator를 사용한 회원 가입 및 개인정보 수정시 유효성 체크 구현

  • maven의 구조에 대해 일부 학습

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

---

오늘 느낀점

• 요즘 공부내용이 크게 바뀌고 있진 않다. 그래서 지치는 부분도 있지만, 새로운걸 접하는 즐거움 못지 않게 꾸준하게 한가지를 공부하는 것도 중요하고 보람도 느껴서 큰 문제 없이 해나가고 있다. 계속 힘내자!

• 명절때도 공부하러 카페를 가고 있다. 주변에서 몇몇은 무리하지 말고 힘들텐데 쉴땐 쉬라고 하는데…반복되는 일상에 무료함을 느껴 지칠때는 있지만, 공부하는 것 자체가 힘들게 느껴지는 것은 없다. 몇번의 선택을 통해 지금의 공부를 하고 있다. 내가 하고 싶은 것을 찾고, 하기 위한 선택들이였다. 즉, 하고 싶은 공부를 하고 있다. 공부자체가 힘들진 않다. 가능하다면 공부를 더 긴 기간 하고 싶은게 문제다.

• 나중은 어떻게 변할지 모르겠지만, 그래서 지금은 내가 하고 싶은 공부 시간도 가질 수 있는 직장에 취업 하는게 목표다. 지속적으로 먹고 살기 위해 공부를 해 나가지 않고, 내가 알고 싶기 때문에 공부를 해 나가고 싶다.

---

내일 할일

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

• 알고리즘 강의 듣기