[TIL] 코드스테이츠 SEB BE Day 24
💡 Today I Will Learn
- DFS / BFS
✏️ Summary
BFS (Breadth-First Search)
그래프 탐색의 한 방법으로 한 정점에 인접한 정점들을 우선적으로 탐색한다. 주로 두 정점의 최단경로를 찾을 때 사용한다.
DFS (Depth-First Search)
그래프 탐색의 또 다른 한 방법으로 한 정점에서의 한 경로를 완벽하게 탐색한 후에 다른 경로를 탐색하는 방법이다.
Deque
1. Stack + Queue
Deque는 Stack과 Queue와 달리 삽입과 삭제의 방향이 정해져 있지 않다. 그러므로 자유롭게 변형하여 사용할 수 있다.
2. 양방향으로 삽입, 삭제 용이
양방향으로 데이터 삽입, 삭제는 용이하나 중간으로 삽입, 삭제는 불가능하다.
Linked List
데이터와 다음 데이터의 주소를 담고있는 노드가 선형으로 이루어져있는 자료구조이다.
구조
배열은 연속된 주소에 담기는 반면, Linked List는 흩어진 공간에 노드의 연결로 이루어져있다.
특징
1. 노드의 추가, 삭제가 빠르고 쉽다.
배열과 달리 추가된 노드로의 주소로 변경하면 되기에 O(1)의 빠른 시간복잡도를 가진다.
2. 데이터 검색을 하려면 전체를 찾아야 한다.
또한 배열과 달리 중간 데이터의 접근이 불가능하므로 탐색에 O(n)의 느린 시간복잡도를 가진다.
Hash Table
Hash Function을 이용하여 index를 생성하여 key-value로 데이터를 저장한다.
즉, key를 해시 함수로 index로 만든 후 데이터를 저장하는 자료구조이다.
Hash Table 특징
삽입, 삭제, 탐색 모두 O(1)의 시간복잡도를 가진다.
Hash Collision(다른 키가 같은 hash값을 가지는 충돌)이 발생할 수 있으며, 저장공간이 미리 확보되어야 하기때문에 공간의 효율성이 떨어진다.
1. 저장, 삭제, 검색
O(1) 의 시간복잡도를 가지며 Hash Collision이 발생할 경우에는 모든 index를 찾아야 하므로 O(n)이다.
2. 해시 알고리즘
key를 기반으로 index를 만드는 Division Method, Digit Folding, Multiplication Method, Universal Hashing 알고리즘 등이 있다.
충돌 해결
1. 개방 연결법 (Open Addressing)
2. 분리 연결법 (Seperate Chaining)
3. 저장소 확장 (Resize)
Heap Tree
Priority로 빠르게 자료를 찾을 수 있는 구조이다.
느슨한 정렬구조로 이루어져 있다. 즉 큰값 혹은 작은값이 부모노드에 존재하지만, 자식노드의 좌우는 결정되지 않는다.
Heap Tree 특징
1. 완전 이진 트리
삽입/삭제 성능을 위해 꽉 찬 완전 이진 트리로 구현한다.
2. 중복 저장
BST와 다르게 중복 저장이 가능하다.
3. 최대 힙과 최소 힙
Heap Tree 데이터 처리방식
최대, 최소값은 루트의 노드이며 (O(1)) 삽입 및 삭제시 특정한 루틴에 따라 데이터를 재배치한다.
또한 완전 이진 트리는 배열로 구현할 수 있다.
현재 노드의 왼쪽 자식노드 2i
현재 노드의 오른쪽 자식노드 2i + 1
현재 노드의 부모노드 i/2
📌 정리
알고리즘 문제에서 빈번히 사용되는 그래프 탐색 알고리즘(DFS, BFS)에 대해 학습하였다. 익숙하지만 DFS의 깊이가 깊어질 수록 return이 어떻게 이루어지는 지 헷갈려서 조금 더 심화해서 공부해야겠다.
👿 Problem
1. Array에 final 제어자는 의미가 없다?
2. BFS 길찾기에서 도착확인?
👼 Solution
1. Array의 참조변수명은 주소값을 가르키므로 final 선언은 참조변수의 주소를 변경할 수 없다는 의미가 된다. 따라서 요소들의 값은 변경할 수 있다.
2. 도착확인은 노드를 add()할 때 많이 했지만, 자기자신에서 자기자신으로 도착하는 입력이 있을 경우에는 poll() 하고난 후 도착확인해야 해결된다.
🎯 Tomorrow
- Time Complexity
- Greedy Algorithm
Back to [TIL] 코드스테이츠 SEB BE Day 23
