Queue
FIFO, 선입선출.
맨 앞에 놈을 Front, 맨 뒤를 Back (혹은 rear).
맨 앞에 값을 제거하는 것을 DeQueue(), 맨 뒤에 값을 추가할땐 EnQueue().
큐를 연습해보기위해, 프로그래머스 Lv_2 문제인 프로세스 문제를 풀어보았습니다.
Linear Queue를 배열로 구현하여 풀어보았으며, Linked list로 구현하여 푸는 방법도 있었습니다.
Array의 경우, DeQueue()를 통한 삭제는 아래와 같은 < empty item >을 발생시킵니다.
Queue { queue: [ <1 empty item>, 2, 4 ], front: 1, rear: 3 }때문에, 이를 없애기 위해서는 원소들을 좌측으로 이동, 즉 O(n)의 시간이 발생합니다.
그에 반해 Linked List는 삽입/삭제에 O(1), 상수시간만 소요되기에 배열보다는 조금 더 시간이 적게 소요됩니다.
하지만 그만큼 구현이 조금 더 복잡한 점이 있습니다.
+) shift() 함수는 O(n)의 시간복잡도가 소요됩니다.
때문에 중첩 반복문에서는 사용을 지양하는 것이 좋을 것 같습니다.
해시 테이블
한정된 배열 공간에, 해시함수를 통해 key를 index로 변환하여 값들을 넣는 자료구조 입니다.
삽입은 O(1)이며 index를 알고있다면 삭제, 탐색도 O(1) 입니다.
해시 함수
해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다.
이렇게 변환된 데이터를 해시 값이라고 합니다.
하지만, 서로 다른 입력값에 같은 해시 값이 나올 수 있습니다.
이러한 현상을 해시 충돌이라 합니다.
이를 해결하기위한 여러 방법들이 있습니다.
-
선형 탐사법
해시 테이블에서 충돌이 발생했을 때, 충돌이 발생한 다음 빈 슬롯을 찾을 때까지 해시 테이블을 선형적으로 탐색하는 방법입니다. 즉, 충돌이 발생한 슬롯 다음부터 순차적으로 탐색하면서 빈 슬롯을 찾습니다.
하지만, 선형 탐사법은 균등한 분포를 가진 해시 함수에서는 잘 동작하지만, 해시 함수의 분포가 불균등할 경우 충돌이 더 자주 발생하게 되어 해시 테이블의 성능을 저하시킬 수 있습니다.
또한, 선형 탐사법은 클러스터링(Clustering) 현상이 발생할 가능성이 있어, 충돌이 발생한 슬롯 주변에 데이터가 밀집하게 저장되는 문제가 있습니다. -
제곱 탐사법
선형 탐사법이 충돌 후 빈 슬롯을 찾기 위해 옆으로 한칸씩 움직였다면, 제곱 탐사법은 이름처럼
충돌 발생 횟수의 제곱만큼 옆으로 이동합니다. -
이중 해싱
충돌이 발생하면 기존 해시 함수가 아닌, 다른 해시 함수를 사용하는 방법입니다. -
분리 연결법
출돌 지점에 Linked List를 만들어, 충돌이 일어난 index에 값을 저장하게 됩니다.
다만, 이 경우 버킷이 무한히 늘어날 수 있습니다.
그래프
비선형 자료구조로써, edge들과 node들로 이루어져 있습니다.
그래프의 특징으로는
- 정점은 여러개의 간선을 가질 수 있습니다.
- 간선은 가중치를 가질 수 있습니다.
ex ) 지하철에서
동대구역 - 동구청역은 1분이지만
동대구역 - 신천역은 2분으로, 가중치(소요 시간)가 서로 다릅니다.
- 사이클이 발생할 수 있습니다.
(사이클 == 탐색시 계속 루프가 가능한 구역을 뜻합니다.)
그래프 구현 방법
- 인접 행렬
- 인접 리스트
후기
오늘부터 약간 코딩테스트 준비를 위한 알고리즘 수업인 것 같다.
잘 들어서 나중에 코테 때문에 발목 잡히는 일 없게끔 해야지.
