2. 자료구조

[자료구조와 알고리즘]

자료구조는 데이터를 원하는 규칙 또는 목적에 맞게 저장하기 위한 구조이고, 알고리즘이란 자료구조에 쌓인 데이터를 활용해 어떠한 문제를 해결하기 위한 여러 동작들의 모임이다.

[스택, 큐, 트리, 힙 구조 설명]

• 스택: 세로로 된 바구니와 같은 구조로 먼저 넣게되는 자료가 마지막으로 나오게되는 First-In Last-Out(FILO) 구조이다.
• 큐: 가로로 된 통과 같은 구조로 먼저 넣게되는 자료가 가장 먼저 나오는 First-In First-Out(FIFO) 구조이다.
• 트리: 정점과 간선을 이용해 사이클을 이루지 않도록 구성한 Graph의 특수한 형태로, 계층이 있는 데이터를 표현하기에 적합하다.
• 힙: 최댓값 또는 최솟값을 찾아내는 연산을 쉽게하기위해 고안된 구조로, 각 노드의 키값이 자식의 키값보다 작지 않거나(최대힙) 그 자식의 키값보다 크지 않은(최소힙) 완전이진트리이다.

[우선순위 큐와 내부 구조 및 시간복잡도]

우선순위큐는 가장 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조이다. 우선순위 큐를 구현하기 위해서 일반적으로 힙을 사용한다. 힙은 완전이진트리를 통해서 구현되었기 때문에 우선순위 큐의 시간복잡도는 O(log n)이다.

[해시 테이블과 해시 테이블의 시간 복잡도]

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용하다. 해시 테이블은 Key값에 해시함수를 적용해 고유한 Index를 생성하여 그 Index에 저장된 값을 꺼내오는 구조이다.

해시 테이블은 고유한 Index로 값을 조회하기 때문에 평균적으로 O(1)의 시간복잡도를 갖는다. 하지만 해시의 Index값이 충돌이 발생한 경우 충돌된 Index값에 대해 연결된 데이터들을 조회하여 원하는 값을 조회하기 때문에 O(N)까지 증가할 수 있다.