CS/면접 대비

[기술면접] 자료구조 면접 대비

미니모아 2022. 5. 4. 18:12

자료구조 면접 대비

자료구조란?
Array vs Linked List
Stack and Queue
Tree
- Binary Tree
- Full Binary Tree
- Complete Binary Tree
- BST (Binary Search Tree)
Binary Heap
Red-Black Tree
- 정의
- 특징
- 삽입
- 삭제
Hash Table
- Hash Function
- Resolve Collision
  - Open Addressing
  - Separate Chaining
- Resize
Graph
- Graph 용어 정리
- Graph 구현
- Graph 탐색
- Minimum Spanning Tree
  - Kruskal algorithm
  - Prim algorithm

자료구조란?

메모리를 효율적으로 사용하며 빠르고 안정적으로 데이터를 처리하는 것이궁극적인 목표로 상황에 따라 유용하게 사용될 수 있도록 특정 구조를 이루고 있는 것이다.

자료구조는 일차원인 컴퓨터 메모리를 현실에 대응되도록 구조를 만든 것!

데이터의 종류와 문맥에 따라 적절한 자료 구조를 사용하는 것은 전체 개발 시스템에 큰 영향을 끼친다. 그렇기 때문에 자료구조의 종류와 장점, 한계를 적절히 이해하고 상황에 맞게 올바른 자료구조를 사용하는 것이 중요하다.

선형 구조

한 원소 뒤에 하나의 원소만이 존재하는 형태로 자료들이 선형으로 나열되어 있는 구조를 가진다.

Array
Linked List
Stack
Queue

비선형 구조

원소 간 다대다 관계를 가지는 구조로 계층적 구조나 망형 구조를 표현하기에 적절하다.

그래프
트리

시간복잡도

프로그램의 성능을 정확히 파악하는 것은 불가능하기 때문에 대략적인 값을 비교하기 위한 상대적인 크기를 사용한다. 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 시간 복잡도라고 하며 일반적으로 빅오 표기법으로 나타낸다.

Array vs Linked List

Array

연관된 데이터를 연속적인 형태로 구성된 구조를 가진다.

배열에 포함된 원소는 순서대로 번호(index)가 붙는다.

특징

고정된 크기를 가지며 일반적으로는 동적으로 크기를 늘릴 수 없다.
원하는 원소의 index를 알고 있다면 O(1) 시간에 찾을 수 있다.

단점

특정 Index를 삭제할 경우 빈 공간이 생긴다. 따라서 연속적인 특징을 유지하기 위해서 그 뒤의 인덱스 원소들을 shift 해줘야 하는 비용이 발생하고 최악의 경우에 O(n)의 시간복잡도를 가질 수 있다.
첫번째 자리나 중간에 원소를 삽입할 경우에도 O(n)의 시간 복잡도를 가진다.

따라서 추가와 삭제가 반복되는 로직이라면 배열 사용을 권장하지 않는다. 배열은 탐색이 많은 경우에 더욱더 유리하다.

Linked List

추가, 삭제가 반복되는 로직에 비효율적인 배열을 문제점을 해결하기 위한 자료구조가 Linked List이다. 각 요소를 포인터로 연결하여 관리하는 선형 자료구조다. 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성된다.

특징

메모리가 허용하는 한 요소를 제한 없이 추가할 수 있다.
탐색은 O(n)이 소요된다.
요소를 추가하거나 제거할 때는 O(1)이 소요된다.
Singly Linked List, Doubly Linked List, Circulr Linked List가 존재한다.

단점

논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문에 어떠한 원소를 삭제 또는 추가하고자 했을 때, 그 원소를 찾기 위해 O(n)의 시간이 추가적으로 발생하게 된다.
결국 search에도 O(n), 삽입, 삭제에도 O(n)의 시간복잡도를 갖는다. Linked List는 Tree 구조의 기본이며 Tree에 사용되었을 때 그 유용성이 드러난다.

단일 연결 리스트

head에서 tail까지 단방향으로 이어지는 연결리스트로 가장 단순한 형태인 연결리스트이다.

이중 연결 리스트

다음과 이전을 가리킬 수 있어 양방향으로 이어지는 연결 리스트

환형 연결 리스트

마지막 tail이 header를 가리켜서 원형으로 연결된 연결 리스트

Stack and Queue

Stack

후입선출 (LIFO) 개념을 가진 선형 자료구조이다.

삽입(Push), 삭제(Pop)의 기능을 가지며 스택의 맨 위 원소를 TOP이라고 한다.

스택 자료구조를 이용하는 가장 대표적인 것은 스택 메모리이다. 스택 메모리는 함수가 호출되며 생성되는 지역 변수, 매개 변수가 저장되는 메모리 영역이다.

함수가 실행된다.
스택 메모리에 매개변수, 지역변수, 변환 주소 값이 푸시되어 기록된다.
함수가 종료되면 스택 메모리에서 pop이 수행되어 제거된다.

스택은 배열과 연결 리스트로 표현될 수 있다.

Queue

선입선출(FIFO)의 개념을 가진 선형자료구조이다.

큐의 맨 앞을 Front, 맨 뒤를 Rear라고 부르며 값을 추가하는 것을 enqueue, 값을 빼는 것을 Dequeue라고 부른다.

종류로는 선형큐와 환형큐가 있다.

배열과 연결리스트로 구현할 수 있지만 배열의 경우 인덱스를 shift할 때를 고려해야하기 때문에 연결리스트로 구현하는 것이 더 효율적이다.

Tree

방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조를 가지고 있다. 계층적 관계를 표현하는 자료구조이다.

구성요소

Node : 트리를 구성하고 있는 각각의 요소
Edge : 트리를 구성하기 위해 노드와 노드를 연결하는선
Root Node: 트리 구조에 최상위에 있는 노드
Terminal Node = Leaf Node = 단말 노드 : 하위에 다른 노드가 연결되어 있지 않은 노드
Internal Node (내부 노드, 비 단말 노드): 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.
level: 루트로부터 몇 번째 깊이인지
degree = 차수: 한 정점에서 뻗어나가는 간선 수
height: 트리의 최고 레벨

예) 조직도, 디렉토리 구조

특징

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

Binary Tree

각 정점이 최대 2개의 자식을 가지는 트리를 의미한다. 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다. 또한 나뉘어진 두 서브 트리도 모두 이진 트리어야 한다. 재귀적인 정의이기 때문에 공집합도 이진 트리로 포함 시켜야한다. 재귀적으로 조건을 확인했을 때 leaf node에 다다랐을 때, 정의가 만족되기 때문이다. 자연스럽게 노드가 하나인 것도 이진 트리 정의에 만족하게 된다.

i번째 노드에 대해 아래의 인덱스 값을 가진다.

parent(i) = i /2
Left_child(i) = i * 2
right_child(i) = i * 2 + 1

종류

완전 이진 트리: 마지막 레벨을 제외하고 모든 정점이 채워져 있는 트리
포화 이진 트리 : 마지막 레벨까지 모두 채워진 이진트리
편향 트리: 한 방향으로만 정점이 이어지는 것

특징

정점이 N개인 이진트리는 최악의 경우 높이가 N이 될 수 있다.
정점인 N개인 포화 또는 완전 이진트리의 높이는 logN이다.
높이가 h인 포화 이진트리는 2^h - 1개의 정점을 가진다.
다음 자료구조에 응용된다.
- 이진 탐색 트리
- 힙
- AVL 트리
- 레드 블랙 트리

BST (Binary Search Tree)

효율적인 탐색을 위해서 데이터를 저장하는 규칙을 가지며 해당 규칙은 특정 데이터의 위치를 찾는데 사용될 수 있다.

이진 탐색 트리의 노드에 저장된 키는 유일하다.
부모의 키가 왼쪽 자식 노드의 키보다 크다.
부모의 키가 오른쪽 자식 노드의 키보다 작다
왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

이진 트리의 탐색 연산은 O(logN)이지만 높이에 따라 O(h)의 시간 복잡도를 갖는다. 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두 배씩 증가하기 때문이다. 따라서 편향 트리가 될 경우 (저장 순서에 따라 노드가 한 쪽으로만 추가될 경우) 성능에 영향을 미치게 되며, 탐색의 worst case가 되어 O(n)의 시간 복잡도를 가지게 된다.

배열보다 많은 메모리를 사용하며 데이터를 저장했지만 탐색에 필요한 시간복잡도가 같게 되어 비효율적이다. 이를 해결하기 위해 rebalancing 기법이 등장했다. 트리의 균형을 잡아서 편향 트리가 되지 않게 하는 것이다.

이 기법을 구현 트리에는 여러 종류가 존재한다.

Red-Black tree
AVL Tree

Red Black Tree

BST를 기반으로 하는 트리 형식의 자료구조이다.

Search, Insert, Delete에 O(logN)의 시간 복잡도가 소요된다. 동일한 노드의 개수일 때, depth를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어이다.

각 노드는 red, black이라는 색깔을 갖는다.
root node는 black이다.
각 leaf node는 black이다.
어떤 노드의 색깔이 red라면 두 개의 children의 색깔은 모두 black이다.
모든 leaf node는 같은 black depth를 가진다.
black-height를 가진다. 노드 x로부터 노드 x를 포함하지 않은 leaf node까지의 simple path상에 있는 black node들의 개수가 같다.

black depth : root에서 current node까지의 black edge의 수

black edge: black인 자식에서 parent로 가는 edge

특징

BST의 특징을 모두 갖는다.
루트부터 leaf까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2보다 크지 않다. 이러한 상태를 balanced라고 한다.
노드의 child가 없을 경우 child를 가리키는 포인터는 nil 값을 저장한다. 이러한 nil들을 leaf node로 간주한다.

삽입

BST의 특성을 유지하면서 노드를 삽입한다. 삽입된 노드의 색깔은 RED로 지정한다. 만약 Red의 자식은 black이어야한다는 규칙을 위배하는 double red가 발생한다면 두가지 해결 방법을 통해 해결한다.

restructuring : uncle node가 black일 때 일렬 묶음에서 중간 값을 root로 재배치 후 색깔을 black이었던 노드와 바꿔준다.
Recoloring: uncle node가 red일 때 grand parent를 red (root라면 black), parent, uncle은 black으로 바꿔준다. 다시 double red가 발생할 수 있다.

따라서 수행은 아래와 같다

insertion 된 z 찾기
추가하고 red 칠하기

While doubleRed(z):
	if isBlack(sibling(parent(z))) => restructuring
    else => recoloring

삭제

삽입과 마찬가지로 BST의 특성을 유지하면서 해당 노드를 삭제한다. 삭제될 노드의 child 개수에 따라 rotation 방법이 달라지게 된다. 만약 지워진 노드의 색깔이 black이라면 black-height가 1 감소한 경로에 black node가 1개 추가되도록 rotation하고 노드의 색깔을 조정한다. 지워진 노드의 색깔이 red라면 Violation이 발생하지 않으므로 RBT가 그대로 유지된다.

Binary Heap

우선 순위 큐

우선 순위가 높은 요소가 먼저 나가는 큐. 우선 순위 큐는 자료구조가 아닌 개념이다. 우선순위큐 != 힙

힙은 우선 순위큐를 구현하기 위한 가장 적절한 자료구조이다.

힙

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

특징

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

추가

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

제거

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

B Tree, B+ Tree

B Tree

데이터베이스에서 널리 사용되는 트리 자료구조의 일종이다. 이진트리를 확장해서, 더 많은 수의 자식을 가질 수 있게 일반화 시킨 것이 B-Tree이다. (다차원 트리)

자식 수에 대한 일반화를 진행하면서, 하나의 레벨에 더 저장되는 것 뿐만 아니라 트리의 균형을 자동적으로 맞춰주는 로직까지 갖추었다.

단순하고 효율적이며, 레벨로만 따지면 완전히 균형을 맞춘 트리이다.

규칙

노드의 자료수가 N이면, 자식 수는 N + 1이어야함
각 노드의 자료는 정렬된 상태여야 한다.
루트 노드는 적어도 2개 이상의 자식을 가져야한다.
루트 노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야한다.
외부 노드로 가는 경로의 길이는 모두 같다.
입력 자료는 중복 될 수 없다.

B+ Tree

데이터의 빠른 접근을 위한 인덱스 역할만 하는 비단말 노드가 추가로 있다.

B-Tree의 변형 구조로, index 부분과 leaf 노드로 구성된 순차 데이터 부분으로 이루어진다. 인덱스 부분의 key 값은 leaf에 있는 key 값을 직접 찾아가는데 사용한다.

장점

블럭 사이즈를 더 많이 사용할 수 있다. key 값에 대한 하드디스크 액세스 주소가 없다.
leaf 노드끼리 연결 리스트로 연결되어 있어서 범위 탐색에 매우 유리하다.

단점

B-tree의 경우 최상 케이스에서 루트에서 끝날 수 있지만 B+tree는 무조건 leaf 노드까지 내려가 봐야한다.

차이점

	B-Tree	B+ Tree
데이터 저장	각 노드	index노드와 leaf 노드로 분리되어 저장됨
각 노드 저장	key, data 모두 저장 data는 disk block으로 포인터가 될 수 있다.	key만 들어간다. data는 모두 leaf 노드에만 존재한다.
		add, delete가 모두 leaf 노드에서만 이루어진다.

Hash Table

해시 테이블은 키와 값을 받아 해싱하여 나온 Index에 값을 저장하는 선형 자료구조로 삽입은 O(1)이며 키를 알고 있다면 삭제, 탐색도 O(1)로 수행한다. 해시테이블은 한정된 배열 공간에 key를 index로 변환하여 값들을 넣게 된다.

해시함수

입력 받은 값을 특정 범위 내 숫자로 바꾸는 함수

문제점

만약 해시 함수의 결과가 동일하여 겹친다면 ? 이를 해시 충돌이라고 한다.

해시 충돌 해결

기본적으로는 두 가지 방식이 있다.

Open Addressing (개방 주소법) : 다른 해시 버킷에 해당 자료를 삽입하는 방식이다.
Separate Chaining (분리 연결법) : 다른 해시 버킷이 아니라 해당 해시 버킷에 여러 개의 데이터를 연결하는 방식으로 트리를 이용한 방식과 linked list를 이용한 방식이 있다.

open addressing vs seperate chaining

개방주소법은 연속된 공간에 데이터를 저장하기 때문에 캐시 효율이 더 좋다. 따라서 데이터의 개수가 충분히 적다면 개방주소법이 분리 연결법보다 성능이 좋다.

분리 연결법은 테이블의 확장을 보다 늦출 수 있다.

Open addressing

선형 탐사법

충돌이 발생하면 옆으로 한 칸 이동한다.

단순하지만 특정 영역에 데이터가 몰릴 수 있다는 단점이 있으며 이동한 버캣에서 또 충돌이 발생한다면 충돌이 발생하지 않을 때까지 이동한다. 그래서 이름 그대로 최악의 경우 탐색에 선형 시간이 걸릴 수 있다.

제곱 탐사법

충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동한다.

충돌이 발생할 수록 범위가 커지기 때문에 데이터가 몰리는 것이 선형 탐사법보다 덜하다.

이중 해싱

충돌이 발생하면 다른 해시 함수를 이용한다.

충돌이 또 발생하면 충돌이 발생하지 않을 때 까지 두 번째 해시 함수를 이용해 해싱한다.

Seperate chaining

Linked List 사용

버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가한다.

충돌이 발생할 경우 다른 인덱스로 이동하지 않고 해시 테이블의 요소를 연결 리스트로 만들어 충돌이 발생한 버캣에 그대로 요소를 추가한다. 최악의 경우 하나의 버켓이 무한정 늘어날 수 있다는 단점이 있다.

사용 사례

값을 빠르게 찾아야하는 경우 해시 테이블을 사용하는 것이 좋다.

예) 학생 정보 관리

Graph

정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조

정점 집합과 간선 집합으로 표현할 수 있다.

트리 또한 그래프이며 단 사이클을 허용하지 않는다.

예) 지하철 노선도, 페이지 랭크: 하나의 페이지가 정점, 페이지에서 파생된 링크가 간선

특징

정점은 여러 개의 간선을 가질 수 있다.
크게 방향 그래프와 무방향 그래프로 나눌 수 있다.
간선은 가중치를 가질 수 있다.
사이클이 발생할 수 있다.

무방향 그래프 (Undirected graph)

간선으로 이어진 정점끼리 양방향으로 이동이 가능하다. 표현하기에 (A, B), (B, A)는 같은 간선으로 취급된다.

Degree : 각 정점에서 연결된 edge의 개수를 degree라고 한다. 각 정점으로 나가는 간선의 개수를 outdegree라고 하고 들어오는 간선의 개수를 Indegree라 한다.

ex) 양방향 도로

방향 그래프 (Directed graph)

간선에 방향성이 존재하는 그래프

양방향으로 갈 수 있더라도 <A, B>와 <B, A>는 다른 간선으로 취급된다.

ex) 일방 통행

연결 그래프

모든 정점이 서로 이동 가능한 상태인 그래프

비연결 그래프

특정 정점쌍 사이에 간선이 존재하지 않는 그래프

완전 그래프

모든 정점끼리 연결된 상태인 그래프

사이클

그래프의 정점과 간선의 부분 집합에서 순환되는 부분

가중치 그래프와 부분 그래프

가중치 그래프란 간선에 가중치 정보를 두어서 구성한 그래프를 말한다.

부분 그래프란 본래 그래프의 일부 정점 및 간선으로 이루어진 그래프를 말한다.

구현 방식

인접 행렬 : 2차원 행렬 이용, 해당하는 위치의 value 값을 통해서 vertex 간의 연결 관계를 O(1)로 파악할 수 있다. Dense graph를 표현할 때 적절할 방법이다.
인접 리스트: 연결 리스트 사용, sparse graph를 표현하는데 적당한 방법이다.

그래프 탐색

깊이 우선 탐색 (DFS)

그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘이다.

Stack을 이용하여 구현할 수 있다.
시작 정점에서 깊은 것부터 찾는다.
V가 정점의 수, E가 간선의 수일 때 O(V+E)의 시간 복잡도를 갖는다.

시작지점을 스택에 넣는다.
스택의 탑을 참고해서 이동할 수 있는 정점 중 방문하지 않은 정점을 추가한다.
더 이상 갈 수 있는 정점이 없을 때까지 반복한다.
더 이상 갈 수 있는 정점이 없다면 꺼내고 2번으로 돌아간다.
모든 노드를 방문하면 종료한다.

너비 우선 탐색 (BFS)

그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘이다.

Queue를 사용하여 구현할 수 있다.
시작 지점에서 가까운 정점부터 탐색한다.
V가 정점의 수, E가 간선의 수일 때 BFS의 시간복잡도는 O(V+E)이다.

시작지점를 큐에 넣는다
큐에서 정점을 꺼내서 해당 정점에서 갈 수 있는 모든 정점 중 아직 방문하지 않은 정점을 큐에 넣는다.
큐가 빌 때까지 반복한다.

최소 신장 트리

최소한의 비용으로 모든 정점을 연결한 것을 최소 신장 트리라고 한다.

신장 트리란 그래프 내에 모든 정점을 포함하는 최소 연결 부분 그래프이다.

최소 신장 트리의 조건

최소한의 간선으로 모든 정점이 연결되어야 한다.
모든 신장 트리 중 가중치의 값이 최소여야 한다.
Cycle이 발생해서는 안된다.

최소 신장 트리 알고리즘

프림 (Prim)
크루스칼 (Kruskal)

Union-Find 알고리즘

서로소 집합을 구하기 위한 알고리즘
- 공통 원소가 없는 두 집합을 표현하기 위한 자료구조
서로 다른 집합을 병합하는 연산 Union과 집합의 원소가 어떤 집합에 속해 있는지 판단하는 연산 Find를 나타낸다.
보통 트리 구조로 구성한다.
편의상 재귀로 구현하는 경우가 많다.

union 구현

자기 자신을 부모 정점으로 설정한다.
간선 정보에 따라 union연산을 반복하며 집합의 최상위 원소를 부모로 설정한다.

결과만으로는 각 원소가 어떤 집합에 속하는지 알 수 없다.

find 구현

어떤 노드의 최상위 원소를 재귀하며 확인한다. 만약 편향트리일 경우 O(n)의 시간복잡도가 소요된다. 이를 경로 압축을 이용해 최적화할 수 있다.

경로 압축

어차피 타고 올라가다 보면 최종 공통 부모를 알 수 있기 때문에 재귀로 구현했다면 돌아오면서 최상위 값으로 부모 값을 변경해준다.

크루스칼 알고리즘

그리디 개념을 이용하여 구현할 수 있다.
먼저 모든 그래프를 부분 집합으로 분리한다.
가장 가중치가 낮은 간선을 선택하고 부분 집합을 연결한다.
이 때 Cycle이 발생하지 않도록 주의한다.
- 공통 최상위 부모를 찾는 것으로 막을 수 있다.
- Union-Find 알고리즘을 이용한다.

구현

간선들을 정렬한다.
가중치가 가장 낮은 간선을 선택하고 두 정점의 최상위 원소가 같지 않다면 한 집합으로 만들어 연결해준다. 최상위 원소가 같다면 사이클이 발생하기 때문이다.
모든 정점이 연결될 때까지 반복한다.

프림 알고리즘

초기화 과정에서 한 개의 vertex로 이루어진 초기 그래프 A를 구성한다. 이후 그래프 A 내부에 있는 vertex로부터 외부에 있는 vertex 사이의 edge를 연결하는데 그 중 가장 작은 weight의 edge를 통해 연결된느 vertex를 추가한다. 이렇게 연결된 vertex는 그래프 A에 포함된다. 위 과정을 반복하고 모든 vertex들이 연결되면 종료한다.

저작자표시 비영리 변경금지