📌 트리 Tree
비선형 계층적 자료구조.
방향그래프의 일종으로 정점을 가리키는 간선이 하나밖에 없는 구조
ex) 디렉토리 구조, 조직도 등
트리 자료구조의 특징
- 루트 정점을 제외한 모든 정점은 반드시 하나의 부모정점 가짐
- 정점이 N개인 트리는 N-1 개의 간선을 가짐
- 루트에서 특정 정점으로 가는 경로는 유일함.
이진트리
각 정점이 최대 2개의 자식을 가지는 트리
이진트리의 특징
- 정점이 N개인 이진트리는 최악의 경우 높이가 N이 될 수 있음. (편향트리)
- 정점이 N개인 포화/완전이진트리의 높이는 log N
-높이가 h인 포화이진트리는 2^h-1개의 정점 가짐 - 이진트리는 이진탐색트리, 힙, AVL트리, 레드-블랙 트리 구현에 사용됨
트리 구현 방법
그래프와 동일하게 인접행렬, 인접리스트로 구현 가능하고, 배열 혹은 요소에 링크가 두 개 존재하는 연결리스트로 구현이 가능하다.
(1) 배열로 구현하는 법
(2) 연결리스트로 구현하는 법
과제
트리를 이용하여 전위 순회, 중위 순회, 후위 순회를 검색하여 직접 구현해 보세요. (힌트 : 스택, 재귀 호출)
//트리 노드를 순회하는 방법은 루트 노드를 언제 거치냐에 따라 세 가지로 나뉜다.
//트리를 순회할 때는 항상 왼쪽이 우선이다.
//레벨순회: 맨위 레벨에서 왼쪽->오른쪽으로 탐색
//전위순회: 루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽
//노드를 탐색하는 방식.
//중위순회: 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면
//루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색하는 방식
//후위순회: 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤,
//제일 마지막에 루트를 방문하는 방식📌 힙 Heap
힙도 트리로 된 자료구조이다. 우선순위가 높은 요소가 먼저 나가는 큐인 '우선순위 큐'를 구현할 때 많이 쓰임.
이진트리 형태를 가지며, 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입/삭제될 때 바로 정렬되는 특징이 있다.
(우선순위 큐!=힙)
힙의 특징
- 우선순위가 높은 요소가 먼저 나감.
- 루트가 가장 큰 값이 되는 최대 힙과 루트가 가장 작은 값이 되는 최소힙이 있다.
- JS에서는 직접 구현해서 사용해야 함.
힙 요소 추가 알고리즘
(1) 요소가 추가될 때는 트리의 가장 마지막 정점에 위치한다.
(2) 추가 후 부모정점보다 우선순위가 높다면 부모정점과 순서를 바꾼다.
(3) 반복하면 가장 우선순위가 높은 정점이 루트가 된다.
(4) 완전이진트리의 높이는 log N이므로 힙의 요소추가알고리즘은 O(log N) 시간복잡도를 가진다.
힙 요소 제거 알고리즘
(1) 요소제거는 루트정점만 가능하다.
(2) 루트정점이 제거된 후 가장 마지막 정점이 루트에 위치하게 된다.
(3) 루트정점의 두 자식 정점 중 더 우선순위가 높은 정점과 바꾼다.
(4) 두 자식 정점이 우선순위가 더 낮을 때까지 반복한다. O(log N) 시간복잡도
과제
이전 코드를 참고하여 최소힙을 구현해보세요. 아주 조금만 수정하면 됩니다.
추후 추가
📌 트라이 Trie
문자열을 저장하고 효율적으로 탐색하기 위한 트리형태의 자료구조
ex. 검색어 자동완성
트라이 자료구조의 특징
- 검색어 자동완성, 사전찾기에 응용된다.
- 문자열 탐색 시 단순하게 비교하는 것보다 효율적으로 찾을 수 있음.
- 문자열 길이가 L일때 탐색/삽입은 O(L)만큼 걸린다.
- 대신 각 정점이 자식에 대한 링크를 전부 가지고 있어야 해서 저장공간 많이 필요함.
트라이 생성하기
구조 : 루트는 비어있고, 각 간선(링크)은 추가될 문자를 키로 가진다. 각 정점은 이전 정점의 값+간선의 키를 값으로 가진다.
- 해시테이블과 연결리스트를 이용해 구현 가능
과제
: 트라이를 사용하여 자동 완성 코드를 구현하세요. (힌트 : 이전에 트리 파트에 사용된 레벨 순회를 응용하여 구현하시오!)
해보자고
📌 정렬 Sort
요소들을 일정한 순서대로 열거하는 알고리즘
특징
- 정렬 기준은 사용자가 정할 수 있다.
- 크게 비교식과 분산식 정렬로 나눌 수 있다
- 대부분 언어가 빌트인으로 제공해줌 👍
- 삽입/선택/버블/머지/힙/퀵 정렬 등 다양한 정렬 방식 존재
(1) 비교식 정렬
1. 버블정렬
서로인접한 두 요소를 검사하여 정렬하는 알고리즘. O(n^2) 시간 복잡도 가짐
2. 선택정렬
선택한 요소와 가장 우선순위가 높은 요소를 교환하는 정렬 알고리즘. O(n^2) 시간 복잡도 가짐
3. 삽입정렬
선택한 요소를 삽입할 수 있는 위치를 찾아 삽입하는 방식의 정렬 알고리즘. O(n^2) 시간 복잡도 가짐. 두 번째 요소부터 시작 된다.
삽입정렬 예제 그림을 볼 수 있는 블로그!
(2) 분산식 정렬
1. 분할정복
문제를 작은 2개의 문제로 분리 후 더 이상 분리가 불가능할 때 처리한 후 합치는 전략. 다양한 알고리즘에 응용됨.
1-1. 합병정렬
분할정복 알고리즘 이용한 알고리즘으로, 최선과 최악의 경우가 같은 안정적인 정렬 알고리즘. O(nlog n) 시간복잡도
1-2. 퀵정렬
매우 빠르나 최악의 경우엔 O(n^2) 시간 복잡도. 불안정 정렬 알고리즘. O(nlog n) 시간복잡도
pivot을 기준으로 좌우를 나누고 정렬한다.
자바스크립트에서는 sort 함수를 사용한다. 이때, 그냥 정렬하게 되면 아스키 문자를 기준으로 정렬되므로, 오름차/내림차 순 정렬을 설정해 주어야 함.
정렬 실습하기
프로그래머스 lv2. 가장 큰 수:
https://school.programmers.co.kr/tryouts/85583/challengesfunction solution(numbers) { let ans=numbers.map(e=>e+"") .sort((a,b)=>(b+a)-(a+b)) .join(""); return ans[0]==='0' ? '0' : ans; }comment
: 분명 sort로 풀 수 있으니까 정렬일 텐데... 왜 안 될까 싶었다. 구상에만 30분 걸렸음.
처음에는 제일 앞 자리 수가 큰 대로 정렬을 하기 위해 문자열을 split해서 일일이 비교해줘야 하나 싶어서 이 방법을 구현하는 데에 시간을 너무 많이 썼고...
결국 다른 사람 풀이를 보았다.
sort를 이용하는 많은 문제를 풀면서 sort((a,b)=>(b+a)-(a+b))는 처음 봤다. 표면적으로 sort함수 내부가 어떤 식으로 진행되는지는 이해하겠는데, 원론적으로는 정말 모르겠다. 나중에 찾아봐야지...
📌 이진탐색 Binary Search
선형탐색
순서대로 하나씩 찾는 탐색 알고리즘. O(n) 시간 복잡도
이진탐색
a.k.a 업다운 게임
정렬되어 있는 요소들을 반씩 제외하며 찾는 알고리즘. O(log n) 시간복잡도
이진탐색의 특징
- 반드시 정렬 되어 있어야 함
- 배열/이진트리 이용하여 구현 가능
- 상당히 빠름
(1) 이진탐색을 배열로 구현하는 방법
(2) 이진탐색을 이진탐색트리로 구현하는 방법
이진탐색트리
: 이진탐색을 위한 이진트리. 왼쪽 서브트리는 루트보다 작은 값, 오른쪽 섭트리는 루트보다 큰 값.
이진탐색트리 요소 추가
루트와 비교하여 루트보다 작은 경우 왼쪽 서브트리로, 큰 경우 오른쪽 서브트리로 추가한다. 루트와 동일한 경우 아무데나 추가하삼.
이진탐색트리 요소 삭제
(1) 단말정점을 삭제하는 경우 별다른 처리 없이 부모정점과 연결을 끊으면 됨.
(2) 하나의 서브트리 가지는 경우 제거되는 정점의 부모간선을 자식정점을 가르키게 바꾸면 됨.
(3) 두 개 서브트리 가지는 경우 왼쪽 서브트리의 가장 큰 값 혹은 오른쪽 서브 트리의 가장 작은 값과 교체하면 됨. 이 경우 교체된 정점의 좌우 자식이 없다면 제거되는 정점의 링크로 대체됨. (what?)
이진탐색트리 문제점:
최악의 경우 한쪽으로 편향된 트리가 될 수 있음. 이런 경우 순차탐색과 같은 시간복잡도를 갖는다. 이를 해결하기 위해 AVL트리/레드-블랙트리를 이용한다.
과제
이진탐색트리구조에서 요소제거를 구현해보시오.
이진탐색 실습하기
프로그래머스 lv3. 입국심사 https://school.programmers.co.kr/learn/courses/30/lessons/43238
function solution(n, times) { //최소로 걸리는 시간과 최대로 걸리는 시간 //그 중간시간에 몇 명을 처리할 수 있는지 세어 보고 //처리할 수 있는 사람 수가 n보다 크면 //중간시간이 넘 넉넉하니까 중간시간 줄임 //n보다 작으면 넘 타이트하니까 중간시간 늘림 //n과 같으면 정답 구함 let low=1; let high=Math.max(...times)*n; while(low<=high){ let mid=Math.floor((low+high)/2); let done=times.reduce((a, t)=> a+Math.floor(mid/t), 0); if(done>=n) { high=mid-1; } else if(done<n) { low=mid+1; } } return low; }
