TIL Algorithm

broccoli·2023년 4월 22일
Algorithms
0

algorithm

목록 보기
1/1

공부한 알고리즘 정리 공간
https://codesandbox.io/dashboard/recent

TIL check 공간
https://docs.google.com/spreadsheets/d/1raBt1WNYgw_ae3CHy3PDeyCKfoQN8Q9aUqfE_nIN62E/edit#gid=0

😎 용어
피봇이란 개념을 알고리즘에서 사용하는 것을 종종 볼 수 있는데, 정확한 개념을 찾았다기보다는 컨텍스트적으로 받아들인 개념은 기준선이긴 한데, 움직이는 기준선을 pivot으로 생각하면 될 거같다.

🥳 알고리즘 유형 정리

[]브루트 포스(Brute Force)
[]그리디(Greedy)
[]구현(Implementation)
[x]DFS와 BFS
[]정렬(Sorting)
[]이분 탐색(Binary Search)
[]분할 정복(Divide and Conquer)
[]동적 계획법(Dynamic Programming)
[]백트래킹(Backtracking)
[]그래프 이론(Graph Theory)
[]문자열(String)
[]수학(Mathematics)
[x]스택(Stack)
[x]큐(Queue)
[]덱(Deque)
[]우선순위 큐(Priority Queue)
[]힙(Heap)
[]세그먼트 트리(Segment Tree)
[x]이진 검색 트리(Binary Search Tree)
[]트리(Tree)
[]유니온 파인드(Union Find)
[]최단 경로(Shortest Path)
[]최소 스패닝 트리(Minimum Spanning Tree)

🥳 자료구조 유형 정리 목록
[]배열(Array)
[x]연결 리스트(Linked List)
[x]스택(Stack)
[x]큐(Queue)
[x]우선순위 큐(Priority Queue)
[x]힙(Heap)
[]덱(Deque)
[]해시 테이블(Hash Table)
[]트라이(Trie)
[x]그래프(Graph)
[x]트리(Tree)
[x]셋(Set)
[]맵(Map)
[]비트마스크(Bitmask)
[]세그먼트 트리(Segment Tree)
[]펜윅 트리(Fenwick Tree)
[]스파스 테이블(Sparse Table)
[]디스조인트 세트(Disjoint Set)
[]문자열(String)

1. 트리

😎 개념:

  1. 노드:
    1. root: 부모가 없는 노드
    2. leaf: 자식이 없는 노드
  2. Edge: 가지 branch라고도 함.
  3. 차수: 자식노드의 수

😎 이진트리: 이진트리: 자식노드가 최대 두개인 노드들로 구성된 트리

  1. 포화이진트리: 모든노드가 두개의 자식 노드를 가진다. 모든 잎노드가 동일한 깊이 를 갖는다.
  2. 완전이진트리: 마지막레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며 마지막 레벨에서는 왼쪽부터 노드가 순서대로 채워진 트리
  3. 이진트리의 순회
    1. 전위순회: 뿌리 → 왼쪽 → 오른쪽
    2. 중위순회: 왼쪽 → 뿌리 → 오른쪽
    3. 후위순회: 왼쪽 → 오른쪽 → 뿌리
  4. 값이 루트보다 작거나 큰값만 들어올 경우 불균형한 이진탐색트리가 만들어지고 검색효율을 저하시킨다. ⇒ 보완해주는 것은 레드블랙트리???(모임)
    1. 트리의 모든 노드는 검정 아니면 레드이다.
    2. 루트노드는 무조건 검정이다
    3. 모든잎노는는 검정이다
    4. 레드노드자식들은 모두 검정이지만 검정노드 자식들은 어떤색이든 상관없다.
    5. 루트노드에서 모든 잎노드 사이에 있는 검정노드의 수는 모두 동일하다.

2. 그래프

그래프는 순환할 수 있다는 차이점이 트리와 다르다. 네비게이션 개념
그래프는 vertices 와 edge의 셋으로 구성되어있음

  • 단방향과 양방향 그래프가 있음
  • 트리와 달리 circular 구조가 있음.
  • 함수
    • addVertex
    • addEdge
    • bfs
    • dfs
    • printGraph

😎 DFS : 깊이우선탐색

한방향으로만 먼저 탐색한다. 막히면 다시 edge로 올라가서 다음 노드 방문

⇒ stack 활용 : First In Last Out

stack 과 current 활용한 로직

stack 이 비워지면 순회가 종료됨.

😎 BFS: 너비우선탐색

형제 노드 부터 방문한다.

⇒ Queue 활용: First In First Out

Queue와 current 활용한 로직

queue가 비워지면 순회가 종료됨

3. 스택

First In Last Out

  • push: 가장 윗데이터로 데이터 삽입
  • pop: 가장 윗데이터 삭제
  • top: 가장 윗 데이터 반환
  • empty: 스택이 비워져있는지 여부 boolean 값 리턴

4. 큐

First In First Out

5. 링크드리스트

다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식의 자료구조

😎싱글링크드리스트

다음노드의 대한 참조만을 가진 가장 단순한 형태의 연결리스트 마지막 원소를 찾으려면 얄짤없이 리스트 끝까지 찾아가야 하기 때문에 On

😎더블링크드리스트

다음노드 참조뿐 아니라 이전 노드의 참조도 같이 가리키게 하는 자료구조

😎순환연결리스트

단순연결리스트에서 마지막 원소가 처음 원소를 가리키게 하는 자료구조

😎 청크리스트

리스트의 멤버가 배열인 자료구조

6. SET

셋은 es6에서 도입된 개념. set은 유니크한 아이템들의 집합이다. 그래서 어떤 요소도 중복이 될 수 없다.
그리고 set은 iterated되고 순서보장이 된다. 원시값이나 obj나 아무것이나 item이 될 수 있다.

참고링크 : https://www.geeksforgeeks.org/sets-in-javascript/

  • size {number} : 요소의 수
  • add(item:any){func} : boolean 마지막에 요소를 추가한다.
  • delete(item:any){func} : boolean 요소를 제거
  • clear{func} : set : 요소 모두 제거
  • entries{func} : iteration 함수 요소의 값을 next().value를 통해 get한다. 이때 키값이 없으므로 배열의 요소는 모두 value가 된다. [value, value]
  • has(item){func} : boolean
  • values{func}
  • keys{func}
  • forEach{func}
// it contains
// ["sumit","amit","anil","anish"]
var set1 = new Set(["sumit","sumit","amit","anil","anish"]);
  
// it contains 'f', 'o', 'd'
var set2 = new Set("fooooooood");
  
// it contains [10, 20, 30, 40]
var set3 = new Set([10, 20, 30, 30, 40, 40]);
  
 // it is an  empty set
var set4 = new Set();

7. Max Heap, 우선순위 큐

우선순위 큐는 우선순위 정보가 먼저 처리되는 알고리즘이고, Max Heap을 이용한 완전이진트리의 자료구조로 되어있다.

참고로 Heap은 최소 최대 값을 O(1)의 시간복잡도로 얻어내기 위해서 사용한다.

1. Max Heap의 구조는 부모노드가 자식노드보다 큰 수이고 왼쪽, 오른쪽의 자식노드의 순서는 중요하지 않다.
2. 루트노드는 arr[0]에 있다.
3. i번째 노드에 대해서 보면, 
부모노드는 arr[Math.floor((i - 1)/2)]에 있다.
왼쪽자식노드는 arr[(2*i) + 1]에 있다.
오른쪽자식노드는 arr[(2*1) + 2]에 있다.

사용되는 예시

  • 운영체제에서 우선순위 기반의 일들을 스케쥴링 하기 위해서 힙을 사용한다.
  • 다익스트라 알고리즘(최단 거리 구하기알고리즘)에서 최소 비용을 기반으로 그래프를 탐색할 때 사용된다.

Min Heap은 반대의 구조이다.

참고링크: geeksforgeeks.org/max-heap-in-javascript/
참고링크: https://jun-choi-4928.medium.com/javascript%EB%A1%9C-heap-priority-queue-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-8bc13bf095d9

최대 힙은 각 내부 노드의 값이 해당 노드의 자식 값보다 크거나 같은 완전한 이진 트리입니다. 힙의 요소를 배열로 매핑하는 것은 간단합니다. 노드가 인덱스 k에 저장되면 왼쪽 자식은 인덱스 2k + 1에 저장되고 오른쪽 자식은 인덱스 2k + 2에 저장됩니다.

8. Heap

힙은 완전이진트리의 형태로서 조금 특별한 형태의 자료구조이다.

예로는 Min Heap, Max Heap 이 있다.

  • 용어정리
    heapify: heap 트리구조를 생성하는 과정
    insert: 기존 heap에 새로운 요소를 추가하는 과정 기본적으로 가장 마지막에 add해서 heapifyUp을 해준다.
    delete: 기존 heap에 가장 우선순위의 요소를 제거하는 과정. 기본적으로 0번째 요소를 삭제하고 heapifyDown을 해준다.
    peek: 가장 우선순위의 요소를 찾는다. 보통 0번째 인덱스
profile
broccoli
🌃브로콜리한 개발자🌟

0개의 댓글