[면접을 위한 CS 전공지식 노트] 자료구조

자료구조는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합

1. 복잡도

복잡도는 시간 복잡도와 공간복잡도로 나뉜다

 

빅오 표기법

• 시간복잡도란 '입력 크기에 대해 어떠한 알고리즘이 실행되는 데 걸리는 시간' 입니다
• 주요 로직의 반복 횟수를 중점으로 측정되며, 보통 빅오 표기법으로 나타냅니다
• 빅오 표기법이린 입력 범위 n을 기준으로 해서 로직이 몇번 반복되는지 나타내는 것인데, 앞서 말한 코드의 시간 복잡도를 빅오 표기법으로 나타내면 O(n^2)이 됩니다

 

시간 복잡도의 존재 이유

• 효율적인 코드로 개선하는 데 쓰이는 척도가 된다
• O(n^2) 보다는 O(n) < O(1)을 지향해야 한다

 

공간 복잡도

• 공간 복잡도는 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말한다 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함

 

자료 구조에서의 시간 복잡도

• 보통 시간 복잡도를 생각할 때 평균, 그리고 최악의 시간 복잡도를 고려하면서 쓴다

2. 선형 자료 구조

• 선형 자료 구조란 요소가 일렬로 나열되어 있는 자료 구조를 말한다
• 연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조
• 삽입과 삭제가 O(1)이 걸리며 탐색에는 O(n)이 걸린다

• prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결 시킨 것이 연결 리스트이며, 연결 리스트는 싱글 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있습니다
• 맨앞에 있는 노드를 head라고 합니다
• 싱글 연결 리스트 : next 포인터만 가진다
• 이중 연결 리스트 : next, prev 포인터를 가진다
• 원형 이중 연결 리스트 :
• 이중 연결 리스트와 같지만 마지막 next 포인터가 헤드 노드를 가리키는 것을 말한다
• 앞에서부터 요소를 넣는 push_front()
• 뒤에서부터 요소를 넣는 push_back()
• 중간에서 요소를 넣는 Insert() 

 

배열

• 배열은 같은 타입의 변수들
• 크기가 정해져 있고 인접한 메모리 위치에 있는 데이터를 모아놓은 집합 중복을 허용하고 순서가 있다
• '정적 배열' 은 접근에 O(1)의 시간 복잡도를 가지며 랜덤 접근이 가능하다
• 삽입과 삭제는 O(n)이 걸린다
• 데이터 추가와 삭제를 많이 하는것은 연결리스트, 접근을 많이 하는 것은 배열로 하는게 좋다

 

랜덤 접근과 순차적 접근

• 랜덤 접근은 동일한 시간에 배열과 같은 순차적인 데이터가 있을때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능
• 순차적 접근은 데이터를 저장된 순서대로 검색해야 한다 랜덤접근의 반대

배열과 연결 리스트 비교

• 배열은 상자를 순서대로 나열한 데이터 구조이며 몇번째 상자인지만 알면 해당 상자의 요소를 끄집어낼 수 있다
• 연결 리스트는 상자를 선으로 연결한 형태의 데이터 구조이며, 상자 안의 요소를 알기위해서는 하나씩 상자 내부를 확인해봐야 한다는 점이 다르다
• n 번째 요소의 접근은 배열은 빠르고 연결 리스트는 느리다
• 배열은 O(1)의 시간 복잡도를 가지고
• 연결 리스트는 접근의 경우 O(n)의 시간 복잡도를 가진다
• 즉 참조가 많이 일어나는 작업의 경우 배열이 빨고 연결리스트는 느리다

백터

• 동적으로 요소를 할당할 수 있는 동적 배열
• 컴파일 시점에 개수를 모른다면 벡터를 써야 한다
• 중복을 허용하고 순서가 있고 랜덤 접근이 가능
• 탐색과 맨뒤의 요소를 삭제하거나 삽입하는데 O(1)이 걸리며 맨 뒤나 맨 앞이 아닌 요소를 삭제하고 삽입하는 데 O(n)의 시간이 걸린다
• 뒤에서부터 삽입하는 push_back()의 경우 O(1)의 시간이 걸리고 벡터의 크기가 증가되는 시간 복잡도가 amortized 복잡도

=> 상수시간 복잡도와 유사한 시간 복잡도를 가지기 때문

• 뒤부터 요소를 더하는 push_back(), 맨뒤부터 지우는 pop_back(), 지우는 erase(), 요소를 찾는 find(), 배열을 초기화하는 clear() 함수가 있다

 

스택

• 스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO, Last in first out)을 가지는 자료구조
• 재귀적인 함수, 알고리즘에 사용되면 웹 브라우저 방문 기록에 쓰인다
• 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸린다

 

큐

• 먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO, First in first out)을 지닌 자료구로
• 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸린다
• CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용됩니다

 

3. 비선형 자료 구조

비선형 자료구조란 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말한다

일반적으로 트리나 그래프를 말한다

 

그래프

그래프 : 정점과 간선으로 이루어진 자료 구조

정점과 간성 

• 어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 했을 때 '어떤 곳은'은 정점이 되고 '무언가'는 간선이 된다
• 짝사랑은 단방향 간선
• 사랑은 양방향 간선

 

• 정점으로 나가는 간선을 해당 정점의 outdegree라고 하며, 들어오는 간선을 해당 정점의 indegree라고 한다
• 정점은 약자로 V 또는 U
• 보통 어던 정점으로부터 시작해서 어떤 정점까지 간다를 " U에서 V로 간다"라고 표현
• 설명한 정점과 간선으로 이루어진 집합을 '그래프'라고 한다.

 

가중치

가중치는 간선과 정점사이에 드는 비용

 

트리

• 트리는 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터의 집합.
• 루트 노드, 내부 노드, 리프 노드 등으로 구성
• 트리로 이루어진 집합을 숲이라고 한다

트리의 특징

트리는 그래프의 일종이며

1 . 부모, 자식 계층 구조를 가진다

2 . V - 1 = E라는 특징이 있다

3 . 임의의 두 노드 사이의 경로는 '유일무이'하게 '존재'한다 즉 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있다

 

트리의 구성

루트노드, 내부노드, 리프노드

 

루트노드 : 가장 위에 있는 노드를 뜻한다. 트리를 탐색할 때 루트 노드를 중심으로 탐색하면 문제가 쉽게 풀리는 경우가 많다

내부노드 : 루트노드와 내부 노드 사이에 있는 노드를 뜻함

리프노드 : 리프노드는 자식노드가 없는 노드를 뜻한다

 

트리의 높이와 레벨

깊이 : 트리에서의 깊이는 각 노드마다 다르며, 루트노드부터 특정 노드까지 최단 거리로 갔을때의 거리

높이 : 트리의 높이는 루트 노드부터 리프 노드까지 거리 중 가장 긴 거리를 의미

레벨 : 트리의 레벨은 주어지는 문제마다 조금씩 다르지만 보통 깊이와 같은 의미

서브트리 : 트리 내의 하위집합 서브트리라고 한다 트리 내에 있는 부분 집합

이진 트리

이진트리는 자식 노드 수가 두개 이하인 트리를 의미 이를 다음과 같이 분류

 

1. 정이진 트리 : 자식 노드가 0 또는 두 개인 이진 트리를 의미
2. 완전 이진 트리 : 왼쪽에서부터 채워져 있는 이진 트리를 의미 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 경우 왼쪽부터 채워져 있습니다
3. 변질 이진 트리 : 자식 노드가 하나밖에 없는 이진 트리
4. 포화 이진 트리 : 모든 노드가 꽉 차 있는 이진 트리
5. 균형 이진 트리 : 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리를 의미 map,set을 구성하는 레드 블랙 트리는 균형 이진 트리 중 하나

이진 탐색 트리(BST)

노드의 오른쪽 하위 트리에는 노드 값보다 큰 값이 있는 노드만 포함되고, 왼쪽 하위 트리에는 노드 값보다 작은 값이 들어 있는 트리를 말한다

이진 탐색 트리는 삽입 순서에 따라 선형적일 수 있다 => 그럼 검색이 느려짐

 

AVL 트리

• 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리
• 두 자식 서브트리 높이는 항상 최대 1만큼 차이 난다는 특징이 있다.
• 최악의 경우를 배제하고 항상 균형잡인 트리로 만들자의 개념을 가진 트리가 AVL 트리이다

레드 블랙 트리

• 균형 이진 탐색 트리로 탐색, 삽입, 삭제 모두 시간 복잡도가 O(logn)이다
• 각 노드는 빨간색 또는 검은색의 색상을 추가하는 추가 비트를 저장하며 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는 데 사용
• 모든 리프 노드와 루트 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다 등의 규칙을 기반으로 균형을 잡는 트리

 

• 힙
• 완전 이진 트리 기반의 자료구조이며 최소힙과 최대힙 두가지가 있고 해당 힙에 따라 특정한 특징을 지킨 트리를 말한다
• 최대힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 한다 또한 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다
• 최소힙 : 최소힙에서 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 한다 또한 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다
• 힙에는 어떠한 값이 들어와도 특정 힙의 규칙을 지키게 만들어져 있다

 

최대 힙의 삽입

힙에 새로운 요소가 들어오면 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입

이 새로운 노드를 부모 노드들과의 크기를 비교하며 교환해서 힙의 성질을 만족

 

최대힙의 삭제

최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제되고, 그 이후 마지막 노드와 루트 노드를 스왑하여 또다시 스왑 등의 과정을 거쳐 재구성

 

우선순위 큐

우선순위 큐는 우선순위 대기열이라고도 하며, 대기열에서 우선 순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료 구조

 

 

우선순위 큐는 힙을 기반으로 구현

greater를 써서 오름차순, less를 써서 내림차순 

 

맵

• 맵은 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료구조
• 레드 블랙 트리 자료 구조를 기반으로 형성되고 삽입하면 자동으로 정렬
• 맵을 쓸때는 map<strint,int> 형태로 구현
• 배열과 비슷하게 clear()함수로 맵에 있는 모든 요소를 삭제 할 수 있으며, size()로 map 크기를 구할 수 잇다
• erase()로 해당 키와 키에 매핑 된 값을 지울 수 있다
• 해시 테이블을 구현할 때 쓰며 정렬을 보장하지 않는 unordered_map과 정렬을 보장하는 map 두가지가 있다
• map을 순회할 때는 키에 해당하는 값을 first, 키에 매핑된 값에 해당하는 값을 second로 탐색 가능

셋

• set은 특정 순서에 따라 고유한 요소를 저장하는 컨테이너이며, 중복되는 요소는 없고 오로지 희소한 값만 저장하는 자료구조
• pair는 두가지 형을 담을 수 있는 구조이며 first, second로 그 인자에 접근이 가능

 

해시테이블

• 무한에 가까운 데이터들을 유한한 개수의 해시값으로 매핑한 테이블 삽입, 삭제 , 탐색 시 평균적으로 O(1)의 시간 복잡도를 가지며 unordered_map으로 구현