오늘 할일

• 알고리즘 문제풀이

• 포트폴리오 수정

• 프로젝트 준비

• 채용공고 읽기

오늘 한 것 & 배운 내용

알고리즘 문제 풀이

K번째 수

• 문제 해석
  • 첫째줄에 K와 N이 주어지고 둘째줄에 N개 만큼의 숫자가 주어진다
  • 이 숫자들을 정렬했을 때 K번째 위치에 있는 수를 출력한다
• 풀이 계획
  • 숫자를 모두 입력받은 뒤 정렬한다
    • 연습삼아 정렬을 하나 직접 구현해보는게 좋을 것 같다
  • 인덱스가 k인 숫자를 출력한다
• 병합정렬 공부
  • 참고 : https://www.youtube.com/watch?v=QAyl79dCO_k&t=8s
  • 병합정렬은 원래의 배열을 반씩 나누는걸 반복하여 1개의 단위로 쪼갠뒤 앞에 배열과 뒤에 배열의 값을 정렬하여 2개의 배열로만들고 다시 2칸짜리 배열을 만들고 다시 2개씩정렬하여 4칸짜리 배열을 만드는식으로 정렬하는 방식이다
  • n개 배열을 반씩 나누어서 연산함으로 n * logn이 되어 시간복잡도가 o(NlogN) 이 확정적으로 나온다고 한다
    • 퀵정렬은 최악의 경우 O(n2)이 나오는데 반해 시간복잡도가 안정적이라는 장점이 있지만 배열을 생성해야해서 공간복잡도에서 단점이 있다
• 나의풀이
  • 병합 정렬을 직접 구현해서 정렬한뒤 arra[k-1]을 통해 k번재 수를 출력하였다
    • 강의를 한번보고 한번 따로 구현해보고 다시 구현한 것이라 거의 외우듯이 구현한 것이라 복습이 필요한 것 같다
    • for문에 범위를 몇번 틀리게 구현해서 디버깅하는데 시간이 걸렸다
      • 이해를 충분히 하지 못하고 구현했기 때문에 발생한 문제인 것 같다
• 다른사람 풀이
  • 참고 : https://fbtmdwhd33.tistory.com/86
  • 퀵정렬을 응용한 퀵 셀렉션 알고리즘을 이용해 병합 정렬보다 빠르게 해답을 구할 수 있었다
    • 퀵 셀렉션은 k번째 pivot까지만 구하면 되기 때문에 시간복잡도가 O(n)으로 줄어든다고 한다
  • 퀵정렬을 이용해 정렬을 하면 pivot에 위치는 이미 몇번째로 큰수인지에 관한 정보를 가지고 있다
    • pivot을 기준으로 왼쪽에는 pivot보다 작은수가 분류되어 있고 오른쪽에는 pivot보다 큰 숫자가 분류되어 있기 때문에 pivot은 확실히 pivot 번째로 큰수라는 정보를 담고 있기 때문이다
  • 즉 퀵정렬을 구현하여 실행하되 pivot이 k번째로 나온다면 바로 return한뒤 출력하면 되는 것이다
    • k번째가 아니라면 pivot이 k보다 크면 왼쪽에 배열을 돌리고 작으면 오른쪽에 배열을 돌려 pivot이 k가 될때까지만 반복하면 된다..
  • 퀵 정렬 구현 자체가 익숙하지 않아 사실 예제를 찾아보면서도 이해하는데 시간이 오래걸렸는데 반드시 이해하고 넘어가야 될 구현이라 계속 이해하기 위해서 노력했다
    • 이해가 잘 안될때 Intellij에 디버깅을 활용해서 실제 어떻게 동작하는지 보는것은 많이 도움이 되었다

포트폴리오 수정

• 포트폴리오 작성에 거의 마지막 단게로 교육과 커리어에 대해서 정리하는 작업을 하였다

  • 사실 며칠 전부터 진행해오던 과제인데 이렇게 과거를 글로써 정리해본 경험이 거의 없어서 굉장히 어렵게 느껴져서 진행이 굉장히 더디고 어려웠다

• 현재는 어떤상황에서 이런일을 하게 됬고 이런 경험을 얻었다는 식으로 정리하였는데 너무 감상적이지 않은가 싶어서 어떻게 좀더 업무적인 경험들을 강조할 수 있을가 고민이 된다

내일 할일

• Qucik Sort & Selection 복습

• 포트폴리오 수정

• 알고리즘 문제 풀이

• 프로젝트 준비

• 채용공고 읽기