TIL 5일차

✏️오늘 배운 것

해시 테이블

키와 값을 받아 키를 해싱하여 나온 index에 값을 저장하는 선형 자료구조.

삽입은 O(1)이며 키를 알고 있다면 삭제, 탐색도 O(1)로 수행한다.

문제점 (해쉬 충돌) 해결법

• 선형 탐사법 : 충돌이 발생하면 옆으로 한 칸 이동
• 제곱 탐사법: 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동
• 이중 해싱: 충돌이 발생하면 다른 해시 함수를 이용한다
• 분리 연결법: 버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스크에 값을 추가
• 참고글 : https://j3sung.tistory.com/759

어디에 사용?

• 빠르게 값을 찾아야 하는 경우

트리, 이진트리

트리

• 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
• 정점이 N개인 트리는 반드시 N-1개의 간선을 가진다.
• 루트에서 특정 정점으로 가는 경로는 유일하다.

이진트리

• 탐색을 위한 알고리즘에 많이 쓰인다.
• 정점이 최대 2개의 자식을 가지는 트리.
• 정점이 N개인 이진 트리는 최악의 경우 높이가 N이 될 수 있다.
• 정점이 N개인 포화 또는 완전 이진 트리의 높이는 log N이다.
• 높이가 h인 포화 이진 트리는 2의 h제곱 - 1개의 정점을 가진다.
• 이진 탐색 트리, 힙, AVL 트리, 레드 블랙 트리에 사용된다.

이진 트리 구현 방법 규칙

• 0번 인덱스는 편의를 위해 비워 둔다
• left = index*2
• right = index*2+1
• Parent = floor(index/2)

힙

이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬되는 구조

특징

• 우선순위가 높은 요소가 먼저 나감.
• 루트가 가장 큰 값이 되는 최대 힙과 루트가 가장 작은 값이 되는 최소 힙이 있다.

힙의 요소 추가 알고리즘

• 요소가 추가될 때는 트리의 가장 마지막에 정점에 위치한다.
• 추가 후 부모 정점보다 우선순위가 높다면 부모 정점 순서를 바꾼다.
• 이 과정을 반복하면 결국 가장 우선순위가 높은 정점이 루트가 된다.
• 완전 이진 트리의 높이는 log N이기에 힙의 요소 추가 알고리즘은 O(logN) 시간 복잡도를 가진다.

힙 요소 제거 알고리즘

• 요소 제거는 루트 정점만 가능하다.
• 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치한다.
• 루트 정점의 두 자식 정점 중 더 우선순위가 높은 정점과 바꾼다.
• 두 자식 정점이 우선순위가 더 낮을 때까지 반복한다.
• 완전 이진 트리의 높이는 log N이기에 힙의 요소 제거 알고리즘은 O(logN) 시간복잡도를 가진다.

트라이

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조

특징

• 검색어 자동완성, 사전 찾기 등에 응용될 수 있다.
• 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있다.
• L이 문자열의 길이일 때 탐색, 삽입은 O(L)만큼 컬린다.
• 대신 각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용한다.

구조

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

정렬

• 비교식 정렬
  • 버블 정렬 : 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘 O(n^2)
  • 선택 정렬 : 선택한 요소와 가장 우선순위가 높은 요소를 교환하는 알고리즘 O(n^2)
  • 삽입 정렬 : 선택한 요소를 삽일 할 수 있는 위치를 찾아 삽입하는 방식의 알고리즘 O(n^2)
• 분산식 정렬
  • 분할 정복 : 문제를 작은 2개의 문제로 분리하고 더 이상 분리가 불가능 할 때 처리한 후 합치는 전략
  • 합병 정렬 : 분할 정복 알고리즘을 이용한 최선과 최악이 같은 안정적인 알고리즘 O(n logn)
  • 퀵 정렬 : 분할 정복 알고리즘을 이용한 매우 빠르지만 최악의 경우가 존재하는 불안정 정렬 O(n logn)

👦소감

정말 많은 자료구조와 알고리즘을 보았다.😅 과제로 트리의 전위, 중위, 후위 순회를 구현했는데 2시간 동안 고민 끝에 해결할 수 있었다. 다 구현하고 블로그를 찾아보니 아름다운 코드를 보게 되어 결국 그걸로 바꾸게 되었다. 배워야 할 게 너무 많고 부족하다고 느끼고 있지만 하나씩 만들어보면 나도 다 할 수 있을 거라 믿는다. 오후 8시 부터 선협님의 특강(부제: 코딩 테스트 준비 방법 & 알고리즘을 잘 공부하는 법)을 들으며 정말 많은 도움이 되었다. 마음가짐부터 꿀팁까지 나에게 필요한 모든 것을 알려준 명강의였다👍 시간을 내주신 선협님 너무 감사합니다 🙇‍♂️ 내일이면 거의 데브코스 첫 주가 끝나는데 시간이 정말 빨리가고 밀린 공부는 산더미지만 좋은 강의와 멘토님들의 케어로 능히 해낼 수 있을 것 같다!

👊세 줄 요약

• 많은 양의 자료구조와 알고리즘 공부 빡세다😓
• 2시간의 명강의(by. 이선협 강사님)👍
• 하면 된다🔥