자료구조 알고리즘 면접대비

준비

기본 자료구조

linked list vs array

노드 : 데이터와 다음 노드를 가르키는 포인터

배열은 같은 타입, 같은 크기, 인접한 메모리

랜덤접근 : 몇번째 자료인지만 알면 배열의 경우 O(1)에 접근 가능
리스트의 경우 순차적으로 Head부터 탐색해봐야 함 O(n)

대신 리스트는 중간 삽입 삭제에 매우 유리함
Front 삽입 삭제도 리스트가 훨씬 유리함
배열의 경우 Front에 삽입 or 삭제할 경우 당기거나 미뤄야 함
back의 경우는 삽입 삭제가 동일한 복잡도
허나 배열의 경우 전체 Capacity가 존재하기 때문에 삽입시 이 Capacity를 넘는다면 더 큰 용량의 array가 필요하고 이를 옮기는 작업이 필요하게 됨

스택 vs 큐

스택은 Last in First out (LIFO)
큐는 First in First out (FIFO)
deque는 양방향 출입이 자유로운 큐
원래 queue는 push back pop front만 가능한 것이 원칙
하지만 deque는 push front, back, pop front, back 모두 가능

트리 (tree)

https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html
이전까지는 선형 자료구조
지금 부터는 비선형 자료구조
트리는 그래프의 일종으로 acyclic graph이다
보통 우리가 생각하는 트리는 root를 가지고 있는 트리 형태이고
트리의 단위 또한 노드이다. (노드: 데이터 + 포인터)

일반적인 트리는 노드들이 임의의 개수의 자식수를 가질 수 있고
이진트리 (binary)트리는 노드들이 최대 2개의 자식수를 가진다

Binary Search Tree

모든 노드가 order가 지켜져서 search에 쓰일 수 있는 이진트리
예컨데
모든 왼쪽 자식들 < 현재 노드 < 모든 오른쪽 자식들
위와 같은 규칙을 갖고 있기 때문에 현재 노드가 자신이 찾는 데이터가 아닐 때
비교해보고 왼쪽으로 갈지 오른쪽으로 갈지 판단할 수 있다

Balanced Binary Search Tree

위에 탐색에 사용한다고 했는데 만약 기막힌 우연으로
한쪽으로만 길게 늘어진 BST일 경우 탐색의 복잡도가 O(n)이 된다
위의 경우를 방지하기 위해
root 노드와 각 노드의 좌, 우 subtree의 높이를 비슷하게 유지해주려는 tree이다
예시로 AVL 트리, RB트리가 있다
AVL 트리는 각 노드에서 rotation을 통해서 높이를 낮춘다
따라서 좌우 subtree에 대한 높이를 알고 있어야 한다

Heap이란?

우선순위 큐를 위해 만들어진 자료구조

우선순위가 높은 데이터가 가장 먼저 나간다
따라서 내부에서 새로운 데이터가 삽입되면 우선순위에 따라서
우선순위가 가장 높은 자료가 맨 앞에 오도록 해야한다

Complete binary tree의 일종인 Heap을 사용해 위의 성질을 유지한다
만약 새로운 데이터가 삽입되면
최하레벨 최우측에 삽입을 한다
그리고 상위 노드에서 우선순위를 파악해
부모 자식간의 데이터 중에 우선순위가 가장 높은 데이터가 부모로 올라오도록 한다

만약 삭제가 일어나면 root가 삭제된다 (PQ는 우선순위가 가장 높은 데이터부터 out)
그러면 마지막 노드를 root로 올린다음 규칙에 맞게 제자리를 찾도록 노드간의 데이터 교환을 진행한다

1. 최대 힙(Max Heap)

최대 트리(Max Tree)는 각 노드의 키(Key)값이 (자식 노드가 있다면) 그 자식의 키(Key)값보다 작지 않은(=크거나 같은) 트리이다.
최대 힙(Max Heap)은 최대 트리(Max Tree)이면서 완전 이진 트리(Complete Binary Tree)이다.
2. 최소 힙(Min Heap)

최소 트리(Min Tree)는 각 노드의 키(Key)값이 (자식 노드가 있다면) 그 자식의 키(Key)값보다 크지 않은(=작거나 같은) 트리이다.
최소 힙(Min Heap)은 최소 트리(Min Tree)이면서 완전 이진 트리(Complete Binary Tree)이다.

• 정리)

최대 힙(Max Heap) : 부모 노드는 자식 노드보다 작지만 않으면 된다. + 완전이진트리이다.

최소 힙(Min Heap) : 부모 노드는 자식 노드보다 크지만 않으면 된다. + 완전이진트리이다.

즉 priority가 큰값인지, 작은값인지에 따라 max or min이 정해진다
우선순위가 무엇이냐 차이지 우선순위가 가장 높은 데이터가 pop 되는 것은 변치 않는다

그래프(Graph)의 개념

단순히 노드와 연결하는 간선(edge)를 하나로 모아 놓은 자료구조

오일러 경로

• 그래프에 존재하는 모든 간선(edge)을 한 번만 통과하면서 처음 정점(vertex)로 되돌아오는 경로
• 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재한다

그래프의 특징

• 그래프는 네트워크 모델 이다.
• 2개 이상의 경로가 가능하다.
• 즉, 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
• self-loop 뿐 아니라 loop/circuit 모두 가능하다.
• 루트 노드라는 개념이 없다.
• 부모-자식 관계라는 개념이 없다.
• 순회는 DFS나 BFS로 이루어진다.
• 그래프는 순환(Cyclic) 혹은 비순환(Acyclic)이다.
• 그래프는 크게 방향 그래프와 무방향 그래프가 있다.
• 간선의 유무는 그래프에 따라 다르다.

그래프의 탐색
일반적으로 두가지 방법이 존재한다
깊이 우선 탐색(Depth-First Search) 과 너비 우선 탐색(Breadth-First Search)
1. 깊이 우선 탐색 (DFS, Depth-First Search)
루트 노드 (혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

• 즉, 넓게(wide)탐색하기 전에 깊게(deep)탐색하는 것이다
• 사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다

2. 너비 우선 탐색 (BFS, Breadth-First Search)
   루트노드 (혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

• 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
  Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
  깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
  너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색

Sort

Insertion Sort

새로운 카드를 기존의 정렬된 데이터 묶음 사이에서 올바른 위치를 찾아 삽입하는 정렬법
생각해보면 올바른 위치 찾는데 평균적으로 n/2가 걸릴 것임
이를 n번 반복해야 하므로 평균적으로 복잡도는 n^2가 될것
예외적으로 매번 올바른 위치를 찾는데 바로바로 찾아진다 가정
그러면 위치를 찾는데 소요하는 시간복잡도가 O(1)이므로
best case에서는 O(n)

• in-place sorting으로 구현 가능

Selection Sort

selection sort는 다음과 같은 방식으로 동작한다
1. 주어진 배열 중에서 최솟값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
4. 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.

즉 1번 과정에서 우리는 모든 data를 살펴봐야 하므로 O(n)의 시간복잡도를 소요함
이를 n번 반복해아 하므로 O(n^2)의 시간복잡도 소요

Bubble sort

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

• 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다

구체적인 개념

• 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.
• 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

즉 거품이 올라오는 것처럼 제일 큰 데이터가 맨 끝으로 하나씩 올라오는 것이다
완전 정렬을 보장하기 위해 항상 모든 원소에 대해서 교환 여부를 확인한다 (매 회시마다 확인하는 원소의 개수는 하나씩 줄어들기는 한다)

in-placing sorting

bubble sort가 제일 느린 이유는 불필요한 switching이 많기 때문 아닐까?

Shell sort

‘Donald L. Shell’이라는 사람이 제안한 방법으로, 삽입정렬을 보완한 알고리즘이다.
삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안

• 삽입 정렬의 최대 문제점: 요소들이 삽입될 때, 이웃한 위치로만 이동
• 즉, 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있다.
• 삽입 정렬과 다르게 셸 정렬은 전체의 리스트를 한 번에 정렬하지 않는다.

과정 설명
1. 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류
2. 연속적이지 않은 여러 개의 부분 리스트를 생성
3. 각 부분 리스트를 삽입 정렬을 이용하여 정렬
4. 모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 반복
5. 위의 과정을 부분 리스트의 개수가 1이 될 때까지 반복

부분적으로 미리미리 조금씩 정렬을 시켜서 최악의 상황을 방지하는 그런느낌?
그래서 전체적으로 AVG값을 삽입정렬보다 낮출 수 있었다

Quick Sort

분할 정복(Divide & Conquer) 알고리즘의 하나로 평균적으로 매우 빠른 수행속도를 가짐

과정
1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)
3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.

• 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
• 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.

4. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.

• 리스트의 크기가 0이나 1이 될 때까지 반복한다.

퀵정렬은 다음의 단계들로 이루어진다.

• 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
• 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
• 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
  순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

best케이스를 생각해보면 첫 시행해서 n, 그다음 시행에서 n/2, n/2 로 나뉘고 그다 n/4 4개
즉 매 시행에서 n번의 시간복잡도를 사용함
그런데 매번 2로 분할해서 문제를 쪼개기 때문에 총 높이는 log2n이 됨
따라서 O(n log2n)의 시간복잡도를 가지게 됨

장점
1. 속도가 빠르다 : 시간복잡도가 O(nlog2n)을 가지는 다른 알고리즘과 비교했을 때도 빠르다
2. 추가 메모리 공간 필요x

단점
1. 정렬된 리스트에 대해서는 피벗을 선택하면 나머지 데이터가 모두 피벗의 왼쪽 혹은 오른쪽으로 이동하게 된다
그러면 O(n^2)이 걸리게 된다

개선법
리스트 내에서 임의로 몇개의 데이터를 추출해 이 중에 medium값을 사용해 피벗으로 사용한다

quick sort의 관건은 좋은 피벗을 고르는 것이다

Merge sort

폰노이만이 제안한 방법
분할 정복 알고리즘의 하나이다
과정
1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

합병 정렬알고리즘의 구체적인 개념

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가ㅏ 정렬된 리스트가 되게 하는 방법이다.

추가적인 리스트가 필요하다 (추가적인 메모리 필요)

합병의 과정

merge sort의 특징
단점
in-place sorting이 아니다, 추가적인 메모리가 필요하다
레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다

장점
안정적인 정렬 방법
데이터 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다
(quick sort의 경우 분포에 따라 n^2 가 걸릴 수도 있었음)
만약 linked list로 구현한다면 inplace sorting을 구현할 수 있음

따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 졍렬 방법보다 효율적이다.

Heap Sort

heap에 하나의 요소를 삽입하거나 삭제할 때 log2n 만큼 소요
전체 데이터는 n개이므로 대략 O(n log2n)이 시간복잡도
힙의 경우는 Best, avg, worst 모두 nlogn

생각해보자
1. 정해진 데이터를 이용해 heap을 만든다
nlogn
2. 데이터를 꺼낸다
매번 logn 따라서 전체 시행 nlogn

O(nlogn) + O(nlogn)이므로 전체적으로 O(nlogn) 이다.

DFS, BFS

그래프를 탐색하는 방법에는 크게 깊이 우선 탐색(Depth first search), 너비 우선 탐색 (Breadth first search)이 있씁니다.

여기서 그래프란, 정점(node)와 간선(edge)로 이루어진 자료구조의 일종을 말하며
그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말합니다.

(그래프와 트리의 차이는, 그래프는 방향성이 있는 비순환 그래프이다)

깊이 우선 탐색의 개념
루트노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식

1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
2. 깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단함
3. 검색 속도 자체는 너비 우선 탐색에 비해서 느림

너비 우선탐색의 개념
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로
시작 정점으로부터 가까운 노드를 먼저 방문하고 멀리 떨어져 있는 노드를 나중에 방문하는 방법

주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다

DFS와 BFS를 활용한 문제 유형/응용
1) 그래프의 모든 정점을 방문하는 것이 주요한 문제
둘다 사용 가능

2) 경로의 특징을 저장해둬야 하는 문제
예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)

3) 최단거리 구해야 하는 문제
미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.
왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,
너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.

구현

DFS는 재귀함수나 스택으로 구현
https://better-tomorrow.tistory.com/entry/DFS-BFS-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0

1. 탐색 시작 노드를 스택에 삽입하고 방문처리

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리

   방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 2번의 과정을 수행할 수 없을 때까지 반복

노드 방문 시 방문 여부를 반드시 검사해야 한다.
그렇지 않으면 방문 했음에도 불구하고 재방문 하면서 무한루프에 빠질 수 있음

장점

• 단지 현 경로상의 노드만을 기억하면 되므로 저장공간의 수요가 비교적 적다 (그래서 그래프가 너무 크면 BFS보다 DFS를 쓰라는 것인가)
  (생각해보면 그래프의 최대 가능 깊이만의 스택 메모리만 존재하면 된다)
• 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

단점

• 해가 없는 경로에 깊이 빠질 가능성이 있따. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수도 있다.
• 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 DFS가 찾아낸 해는 최적해가 아닐 가능성이 있다. 반면에 BFS는 처음 발견된 해가 최단경로이다.

BFS는 큐를 사용해 구현한다

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리

2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 큐에 삽입 후 방문 처리

3. 2번 반복

특정 조건의 최단 경로 알고리즘을 계산할 때 사용

장점

• 출발 노드에서 목표노드까지의 최단 길이 경로를 보장

단점

• 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 많은 메모리가 필요할 수 있음
• 해가 존재하지 않는다면 유한 그래프의 경우, 모든 그래프를 탐색한 후에 실패로 끝난다
• 무한 그래프의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

그래프 표현 방식

1. 인접행렬 : 2차원 배열로 그래프 표현
2. 인접 리스트 : 리스트로 그래프 표현

동적 계획법 (Dynamic Programming)

어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다

ex) 다익스트라 알고리즘

다익스트라 알고리즘

다익스트라 알고리즘은, 알고리즘의 제안자 다익스트라씨가 차 마시다가 노트에 끄적거린거 몇번으로 나올 수 있을만큼 나름 심플한 알고리즘임을 알았다. 진짜 멀리 갈 필요 없다. BFS를 구현 하되, BFS에서는 큐를 쓰지만, 간선의 가중치에 따라서 우선 탐색을 해야하니, 우선순위 큐를 쓰면 되는 것이었다. 진짜 그게 끝이다. 그래서 BFS와 함께 다익스트라 알고리즘을 한 글에다 담아 본 것이다.

다익스트라 알고리즘은 음의 간선이 존재하지 않는 경우 사용할 수 있다.
현실 세계에서는 음의 간선이 존재하지 않는 경우가 많기 때문에 현실에 적용하기 적합한 알고리즘 중 하나라고 할 수 있다.

다익스트라 알고리즘이 다이내믹 프로그래밍 문제인 이유는 '최단 거리는 여러개의 최단거리로 이루어져있기 때문이다' 작은 문제가 큰 문제의 부분 집합에 속해있다고 볼 수 있다.

다익스트라 알고리즘을 구현하기 위해서는 다음과 같은 과정을 반복하면 된다

1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. (처음엔 시작 노드)
2. 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록한 값보다 작다면 그 거리를 갱신한다.

우선순위 큐로 구현할 수 있다
노드의 인근 노드와의 비용을 큐에 넣는다
우선순위에 따라 최소 비용 노드를 꺼내고 방문하지 않은 노드를 갱신해서 더 작으면 집어 넣는다
그중 또 최소 비용 노드를 꺼내서 방문하지 않은 노드와의 비용을 갱신해서 더 작으면 집어 넣는다
이를 모든 노드를 방문할 때까지 반복한다.

https://mattlee.tistory.com/50

BFS vs 다익스트라 알고리즘

BFS 탐색 : 시작점으로부터 어떤 지점까지 너비 우선적으로 탐색한다. 만약 edge의 가중치가 모두 동일한 단위 길이인 경우 최단 경로를 구할 수도 있따.
다익스트라 : 시작점으로부터 나머지 node까지의 최단경로를 구할 때 사용한다
다익스트라의 경우 edge의 가중치가 존재하는 경우에도 최단경로를 구할 때 사용할 수 있다.
그러나 BFS는 node 너비 우선 탐색이므로 edge의 최소 갯수만 판별 가능하지 edge에 weight가 존재하는 경우 첫번째로 찾은해가 최단거리라는 보장이 없다

Map과 HashMap의 차이

둘의 가장 큰 차이는 특정 키에 대한 값을 찾는 과정에서, Hash_Map 은 이름 그대로 Hash Table 을 이용해서 키-값 관계를 유지하며, Map 은 red-black tree 알고리즘을 이용한다.

Hash란 무엇인가?

해시(hash)란 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑(mapping)한 값이다. 이를 이용해 특정한 배열의 인덱스나 위치나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다.

데이터를 검색할 때 사용할 키와 실제 데이터 값이 한쌍으로 존재하고 이를 통해서
O(1)의 복잡도로 데이터가 저장된 곳을 찾아낼 수 있다.

다만 이러한 해시값을 만드는 해시 함수가 언제나 완벽하게 1대1 대응의 key값을 만들어낼 수 있지 않다
이러한 경우 충돌이 발생했다고 하는데
이러한 충돌을 해결하기 위해 array에 Linked list를 만들어 해당 데이터와 일치하는 경우를 찾아갈 수 있다. 만약 이러한 linked list가 너무 편향되어 몰려있다면 설계를 다시 고려해봐야 한다

STL
각 STL 사용된 자료구조
array
Vector
list
set
map
priority queue
등등
그냥 자료구조 그래프

면접 예상질문