프로그래머스 데브코스 TIL - 1주차 보충

✅ 학습 목차

- [Day 5] JavaScript 주요 문법 (5) 

 

✅ 새롭게 학습한 부분

- 트라이

- 정렬

- 이진탐색

 

---

트라이(Trie) 

- 문서를 저장하고 효율적으로 탐색하기 위한 트리형태의 자료구조
- L이 문자열의 길이일 때 탐색, 삽입은 O(L)만큼 걸린다.
- 대신 각 정점이 자식에 대한 링크를 전부 가지고 있기 때문에 저장공간을 더 많이 사용한다.

- 검색어의 자동완성 기능에 활용할 수 있다는 것을 알게 되었다.💡

 

트라이의 구조

- 루트는 비어있다.
- 각 간선은 추가될 문자를 키로 가진다.
- 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다.
- 해시 테이블과 연결 리스트를 이용하여 구현할 수 있다.

 

---

비교식 정렬

버블정렬

- 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘 o(n2)의 시간복잡도를 가진다.
- 뒤에서부터 정렬이 된다.

 

선택정렬

- 선택한 요소와 가장 우선순위가 높은 요소를 교환하는 정렬 알고리즘 o(n2)시간복잡도를 가진다
- 앞에서부터 정렬이 된다

 

삽입정렬

- 선택한 요소를 삽입 할 수 있는 위치를 찾아 삽입하는 방식의 정렬 알고리즘

- O(n2)시간복잡도를 가진다.

 

분산식 정렬

분할정복

- 문제를 작은 2개의 문제로 분리하고 더 이상 분리가 불가능 할 때 처리한 후 합치는 전략

 

합병정렬

- 분할 정복 알고리즘의 하나로, 최선과 최악이 같은 안정적인 정렬 알고리즘

- O(n log n) 시간복잡도를 가진다.

 

퀵정렬

- 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 알고리즘

- 최악의 경우가 존재하는 불안정 정렬으로 O(n log n) 시간복잡도를 가진다.

 

정렬 실습 : 가장 큰 수 구하기

 

✍ 처음 작성한 코드(실패)

function solution(numbers) {
  let answer = numbers.sort((a, b) => String(b) + a - (String(a) + b)).join("");

  return answer;
}

실패 케이스가 하나가 계속 나와서 왜 안되나 생각을 해봤는데

제공되는 숫자 배열이 [0,0,0] 나오는 케이스를 생각을 하지 못했다.

 

✅ 수정한 코드

function solution(numbers) {
  let answer = numbers.sort((a, b) => String(b) + a - (String(a) + b)).join("");

  return answer == 0 ? "0" : answer;
}

---

 

이진 탐색

- 정렬되어있는 요소들을 반 씩 제외하며 찾는 알고리즘

- O(log n)시간복잡도를 가진다.

- 반드시 정렬이 되어있어야 할 수 있다.

- 배열 혹은 이진트리를 이용하여 구현할 수 있다.

 

이진 탐색 트리

- 이진 탐색을 위한 이진 트리로 왼쪽 서브 트리는 루트보다 작은 값이 모여있고

  오른 쪽 서브 트리는 루트보다 큰 값이 모여있다.

- 루트를 기준으로 왼쪽은 작은 값 오른쪽은 더 큰 값이다.

- 최악의 경우 한쪽으로 편향된 트리가 될 수 있다.

- 그런 경우 순차 탐색과 동일한 시간복잡도를 가진다

- AVL트리, 레드-블랙 트리로 해결 할 수 있다.

 

---

 

✍ 느낀점

 

한 주가 너무 빨리 지나갔다.. !!!

강의를 듣는 것은 어렵진 않지만 이해를 하고 넘어가야 했어서 조금 더뎠던 것 같다.

어떻게 다 이해를 해야 하지.. 하고 약간 좌절할 뻔 했던 적도 있었다.

하지만 결국 계속 보고 직접 해보면서 머리 속을 두드리니 비집고 들어가지기는 하는걸 보니

결론 = 계속 하면 된다. ㅋㅋㅋ 포기만 안하면 될 듯!!!

1주차의 과제를 먼저 하기 위해서 금요일의 강의는 토요일과 나누어서 마무리를 했다.

주말이 있어 이렇게 다행일수가!!

자료구조와 알고리즘에 대한 개념이 부족하다 보니 실습 부분도 시간이 꽤 걸렸다.

짧은 시간 안에 여러가지를 머릿 속에 넣느라 어질어질 했지만😱

과제도 전부 마무리 하고 1주 전의 나 보다는 많은 것을 알게 된 것 같다!!