[스터디3] 자료구조 - 07. 복잡도 및 선형 자료 구조

목차

 

 

5.2 섹션인 선형 자료 구조 위주로 정리하려고 합니다. 자료 구조를 정확히 이해하면 좋다는 것을 알지만, 자주 헷갈리는 것 같습니다.

5장 자료 구조

5.1 복잡도

5.1.1 시간 복잡도

• 시간 복잡도: 입력 크기에 대해 어떠한 알고리즘이 실행되는 데 걸리는 시간
• 빅오 표기법: 입력 범위 n을 기준으로 해서 로직이 몇 번이나 반복되는지 나타내는 것
• 시간 복잡도는 효율적인 코드로 개선하는 데 쓰이는 척도가 됨.

5.1.2 공간 복잡도

• 공간 복잡도: 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
• 정적 변수로 선언된 것 외 동적으로 재귀적인 함수로 공간을 계속 필요로 하는 경우도 포함됨.

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

• 시간 복잡도를 생각할 때 평균, 최악의 시간 복잡도를 고려해야 함.

자료 구조	접근	탐색	삽입	삭제
배열(array)	O(1)	O(n)	O(n)	O(n)
스택(stack)	O(n)	O(n)	O(1)	O(1)
큐(queue)	O(n)	O(n)	O(1)	O(1)
이중 연결 리스트(doubly linked list)	O(n)	O(n)	O(1)	O(1)
해시 테이블(hash table)	O(1)	O(1)	O(1)	O(1)
이진 탐색 트리(BST)	O(log n)	O(log n)	O(log n)	O(log n)
AVL 트리	O(log n)	O(log n)	O(log n)	O(log n)
레드 블랙 트리	O(log n)	O(log n)	O(log n)	O(log n)

▲ 자료 구조의 평균 시간 복잡도

자료 구조	접근	탐색	삽입	삭제
배열(array)	O(1)	O(n)	O(n)	O(n)
스택(stack)	O(n)	O(n)	O(1)	O(1)
큐(queue)	O(n)	O(n)	O(1)	O(1)
이중 연결 리스트(doubly linked list)	O(n)	O(n)	O(1)	O(1)
해시 테이블(hash table)	O(1)	O(n)	O(n)	O(n)
이진 탐색 트리(BST)	O(n)	O(n)	O(n)	O(n)
AVL 트리	O(log n)	O(log n)	O(log n)	O(log n)
레드 블랙 트리	O(log n)	O(log n)	O(log n)	O(log n)

▲ 자료 구조의 최악의 시간 복잡도

5.2 선형 자료 구조

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

5.2.1 연결 리스트

• 연결 리스트: 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조
  • prev 포인터와 next 포인터로 앞뒤 노드를 연결시킨 것
  • 시간 복잡도 - 삽입, 삭제: O(1) / 탐색: O(n)
  • 싱글 연결 리스트: next 포인터만 가짐.
  • 이중 연결 리스트: next 포인터와 prev 포인터 가짐.
    • push_front(): 앞에서부터 요소 넣음.
    • push_back(): 뒤에서부터 요소 넣음.
    • insert(): 중간에 요소 넣음.
  • 원형 이중 연결 리스트: 이중 연결 리스트와 같지만, 마지막 노드의 next 포인터가 헤드 노드를 가리킴. 

▲ 연결 리스트 종류

5.2.2 배열

• 배열(array): 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합
• 중복, 순서가 있음. 랜덤 접근이 가능함.
• 시간 복잡도 - 접근(참조): O(1) / 삽입 삭제: O(n)
• 배열과 연결 리스트 비교
  • 배열은 순서대로 나열한 데이터 구조로, 인덱스를 알고 있다면 해당 요소를 즉시 가져올 수 있음.
  • 연결 리스트는 선(포인터)를 사용하여 다음 요소와 연결된 형태의 데이터 구조로, 요소를 찾기 위해서 순차적으로 탐색해야 함.
  • 이러한 이유로 n번째 요소의 접근(참조)는 배열이 연결 리스트 보다 빠름. 데이터 추가 및 삭제는 연결 리스트가 배열 보다 빠름.

5.2.3 벡터

• 벡터(vector): 동적으로 요소를 할당할 수 있는 동적 배열
• 컴파일 시점에 개수를 모른다면 벡터를 사용해야 함.
• 중복, 순서가 있음. 랜덤 접근이 가능함.
• 시간 복잡도 - 탐색과 맨 뒤 삭제 후 삽입: O(1) / 맨 뒤나 맨 앞이 아닌 요소 삭제 후 삽입: O(n)
• 벡터 함수 
  • push_back(): 뒤에서부터 요소를 더함.
  • pop_back(): 맨 뒤부터 지움.
  • erase(): 지움.
  • clear(): 배열을 초기화함.

5.2.4 스택

• 스택(stack): 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO: Last In First Out)을 가진 자료 구조
• 재귀 함수, 알고리즘, 웹 브라우저 방문 기록 등에 사용됨.
• 시간 복잡도 - 삽입 삭제: O(1) / 탐색: O(n)

▲ 스택

5.2.5 큐

• 큐(queue): 먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO: First In First Out)을 가진 자료 구조
• CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용됨.
• 시간 복잡도 - 삽입 삭제: O(1) / 탐색: O(n)

▲ 큐

이 글은 『 면접을 위한 CS 전공지식 노트 』 책을 학습한 내용을 정리한 것입니다.