일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- 프로그래머스 프론트엔드 데브코스
- 프로그래머스 K_Digital Training
- SCSS import
- 쌓임맥락
- 다른컴퓨터에서 git사용
- vue 이벤트 수신
- 리스트 렌더링
- KDT 프로그래머스
- 고양이 사진 검색기
- 프로그래머스 데브코스
- SCSS forward
- SCSS extend
- 프로그래머스 데브코스 프론트엔드
- postcss
- nextjs사용법
- Spacer
- KDT 프로그래머스 데브코스 프론트엔드
- 리액트
- intersection opserver
- vue 지역 컴포넌트
- Vue
- SCSS use
- git 같은계정 다른 컴퓨터
- flex
- netlify redirect
- 이벤트 수식어
- react next
- vue mixin
- 폼 입력 바인딩
- vuex map
- Today
- Total
혼자 적어보는 노트
프로그래머스 데브코스 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주 전의 나 보다는 많은 것을 알게 된 것 같다!!
'스터디' 카테고리의 다른 글
프로그래머스 데브코스 TIL - Day 7 (0) | 2022.03.29 |
---|---|
프로그래머스 데브코스 TIL - Day 6 (0) | 2022.03.28 |
프로그래머스 데브코스 TIL - Day 5 (0) | 2022.03.25 |
프로그래머스 데브코스 TIL - Day 4 (0) | 2022.03.24 |
프로그래머스 데브코스 TIL - Day 3 (0) | 2022.03.23 |