CS 자료구조

복잡도

시간 복잡도

문제를 해결하는 데 걸리는 시간과 입력의 함수 관계 → 얼마나 오랜 시간이 걸리는지

빅오표기법

10n^2 + n 시간이 걸리는 알고리즘이 있다면 O(n^2) 으로 표기된다.

가장 영향을 많이 끼치는 항의 상수를 제외하고 작성한다.

O(n^2)으로 9초의 시간이 걸리는 로직을 O(n)으로 개선하면 3초가 걸리게 된다.

그렇기 때문에 O(n^2) → O(n) → O(1) 을 지향해야된다.

공간복잡도

프로그램을 실행시켰을 때 필요한 자원 공간의 양

int a[1004] 라고 하였을 때 a는 1004 * 4 바이트의 크기를 가지고 있는다.

자료구조에 따른 시간복잡도

선형 자료 구조

요소가 일렬로 나열되어 있는 자료 구조

• 싱글 연결 리스트 - 데이터를 감싼 노드를 포인터로 연결 맨앞이 HEAD로 표시되고, 노드는 다음노드의 주소를 가르키고 있다.

• 이중 연결 리스트 - 노드에 이전 노드의 주소, 데이터, 다음 노드의 주소를 가지고 있다.
• 원형 이중 연결 리스트 - 마지막 노드가 HEAD의 포인트를 가르킴

배열 **

데이터의 탐색을 중점으로한 자료구조, 탐색 O(1)

• 직접 접근(랜덤 접근) - 배열
• 순차적 접근 - 연결리스트

순서대로 나열되어 있는 데이터 구조이기 때문에, 상자의 위치만 알면 쉽게 데이터를 찾을 수 있다. 링크드 리스트가 상자를 찾기위해 일일히 요소를 둘러보는 것과는 다르다.

벡터

동적으로 요소를 할당할 수 있는 배열

중복 o, 순서 o, 랜덤 접근 o

탐색, 맨 앞/뒤의 요소를 삭제하는데는 O(1)의 시간 복잡도를 가지지만, 중간의 요소를 삭제 삽입하는데는 O(n)의 시간 복잡도를 가진다.

O(1)의 복잡도를 가지는 이유는 백터는 요소가 삽입될 때마다 커지는 것이 아닌, 1, 2, 4, 8, 16, 32… 순으로 커지기 때문에

벡터가 확장된다면, 확장된 배열에 기존의 값을 복사하고 뒤에 추가하려는 값을 붙이면 되기에, 확장하는 작업자체는 자주 일어나지 않고, 확장한다하여도 무시할만큼 작기때문에 상수로 간주된다.

스택

가장 마지막에 들어간 값이 먼저나오는 후입선출을 따르고 있음

ex ) 재귀 함수, 알고리즘, 웹 브라우저 방문 기록

삽입, 삭제 - O(1) / 탐색 - O(n)

탐색에 시간이 오래걸리는 이유는, 처음 값부터 순회해가면서 찾아봐야되기 때문에

큐

먼저 집어넣은 값이 먼저나오는 선입선출을 가짐

ex ) 프로세스, 스레드 행렬, 네트워크 접속을 기다리는 행렬, 캐시…

삽입, 삭제 - O(1) / 탐색 - O(n)

비선형 자료 구조

일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조 (트리, 그래프…)

그래프

정점과 간선으로 이뤄진 자료 구조

가중치 - 간선과 정점사이 드는 비용, A → B 이동하는데 드는 비용

트리

그래프 중 하나로, 계층적(부모 - 자식) 데이터의 집합

그래프는 딱히 데이터 간의 계층이 없지만, 트리는 상위에 있는게 더 많은 자식 노드를 가지고 있다.

노드 사이의 경로는 무조건적으로 존재한다.

왼쪽 : 작은 값 / 오른쪽 : 큰값

AVL 트리

최악의 선형트리가 되는 것을 방지하고자 스스로 균형을 잡는 트리, 서브트리의 높이는 항상 1을 넘어가지 않음

탐색, 삽입, 삭제 - O(logn) 의 시간 복잡도를 가짐

레드 블랙 트리

삽입, 탐색, 삭제 모두 시간 복잡도 O(logn)

색상은 추가 비트를 저장해 균형잡히도록 설계 → 조건을 만족하면 색이 나타나도록 함

• 리프 노드는 항상 블랙
• 어떤 노드가 레드이면 그 자식노드는 무조건 블랙

힙

완전 이진 트리 기반의 자료 구조

• 최소힙 : 루트 노드에 있는 값은 모든 노드 중 최솟값
• 최대힙 : 루트 노드에 있는 값은 모든 노드 중 최댓값

삽입 → 노드 들과 비교하여 힙의 성질을 만족할 때 까지 내려간다.

삭제 → 삭제하고 그 빈자리를 다른 노드와 비교하며 자리를 재 정렬함

우선순위 큐

최대 / 최소힙을 기반으로 우선순위가 높은/낮은 요소를 상단에 배치한다.

맵

특정 순서에 키 - 값 으로 구성된 자료 구조

“이승철” : 1, “박동영” : 2 와 같은 방식으로 구현한다.

• unordered_map : 정렬을 보장하지 않는 맵
• map : 정렬을 보장하는 맵

셋

특정 순서에 따라 고유한 요소를 저장함, 중복되는 요소는 없고 고유한 요소만 저장함

해시 테이블

무한에 가까운 데이터를 유한한 개수의 해시 값으로 매핑, O(1) 의 시간복잡도를 가진다.

unordered_map으로 구현한다.