[BOOK] 복잡도, 선형 자료 구조, 비선형 자료 구조

 

• 자료 구조(data structure) : 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합
  
  
• 복잡도는 시간 복잡도와 공간 복잡도로 나뉜다.
  
• 시간 복잡도
  • 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계
  • 어떠한 알고리즘의 로직이 '얼마나 오랜 시간'이 걸리는지를 나타내는 데 쓰인다.
  • 빅오 표기법 : 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것.
    • 시간 복잡도를 보통 빅오 표기법으로 나타낸다.
    • 코드의 시간 복잡도를 빅오 표기법으로 나타내면 O(n²)이 된다.
      '가장 영향을 많이 끼치는'항의 상수 인자를 빼고 나머지 항을 없앤 것.
      • 다른 항들이 신경 쓰일 수도 있지만 증가 속도를 고려한다면 그렇지 않다.
        입력 크기가 커질수록 연산량이 가장 많이 커지는 항은 n의 제곱항이고,
        다른 것은 그에 비해 미미하기 때문에 이것만 신경 쓰면 된다는 이론.
• 시간 복잡도의 존재 이유
  • 효율적인 코드로 개선하는 데 쓰이는 척도가 된다.
    • ex) 버튼을 누르고 화면이 나타나는 로직이 O(n²)의 시간 복잡도를 가지고 9초가 걸린다고 할 때,
      이를 O(n)의 시간 복잡도를 가지는 알고리즘으로 개선한다면 3초가 걸리게 됨. 

• 시간 복잡도의 속도 비교
  • O(1)과 O(n)은 입력 크기가 커질수록 차이가 많이 나는 것을 볼 수 있다.
  • O(n²)보다는 O(n), O(n)보다는 O(1)을 지향해야 한다.

 

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

 

• 자료 구조에서의 시간 복잡도
  • 자료 구조를 사용할 때는 시간 복잡도를 잘 생각해야 한다.
  • 보통 시간 복잡도를 생각할 때 평균, 그리고 최악의 시간 복잡도를 고려하면서 쓴다.

---

 

• 선형 자료 구조
  • 요소가 일렬로 나열되어 있는 자료 구조
    
    
• 연결 리스트
  • 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조
  • 삽입과 삭제는 O(1)이 걸리며, 탐색은 O(n)이 걸린다.
  • prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨 것
  • 맨 앞에 있는 노드를 헤드(head)라고 한다.
  • 싱글 연결 리스트, 이중 연결 리스트, 원형 이중 연결 리스트가 있다.
    • 싱글 연결 리스트 : next 포인터만 가진다.
    • 이중 연결 리스트 : next포인터와 prev포인터를 가진다.
    • 원형 이중 연결 리스트 : 이중 연결 리스트와 같지만 마지막 노드의 next포인터가 헤드 노드를 가리킨다.

 

• 배열(array)
  • 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합
  • 중복을 허용하고 순서가 있다.
  • '정적 배열' 기반 탐색에 O(1)이 되어 랜덤 접근(random access)이 가능하며, 삽입과 삭제는 O(n)이 걸린다.
  • 인덱스에 해당하는 원소를 빠르게 접근해야 하거나 간단하게 데이터를 쌓고 싶을 때 사용.
    
• 랜덤 접근과 순차적 접근
  • 순차적 접근(Sequential access) : 데이터를 저장된 순서대로 검색해야 함.
  • 랜덤 접근 (= 직접 접근, Random access) : 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능
  • 즉, 랜덤 접근과 순차적 접근은 반대.

 

• 배열과 연결 리스트 비교
  • 배열 : 상자를 순서대로 나열한 데이터 구조, 몇 번째 상자인지만 알면 해당 상자의 요소를 끄집어낼 수 있다.
  • 연결 리스트 : 상자를 선으로 연결한 형태의 데이터 구조, 상자 안의 요소를 알기 위해서는 하나씩 상자 내부를 확인해봐야 한다.
  • 데이터를 탐색할 경우 : 배열이 빠르고 O(1) 연결 리스트는 느리다 O(n)
    • 배열은 상자 위에 있는 요소를 탐색하면 되는데, 연결 리스트는 주어진 선을 기반으로 순차적으로 상자를 열어야 한다.
  • 데이터를 추가 및 삭제할 경우 : 연결 리스트가 빠르고 O(1) 배열은 느리다 O(n)
    • 배열은 모든 상자를 앞으로 옮겨야 추가가 가능하지만, 연결 리스트는 선을 바꿔서 연결해주기만 하면 됨.
  • 요약 : 데이터 추가와 삭제를 많이 할 경우 연결리스트, 탐색을 많이 하는 것은 배열로 하는 것이 좋다.
    

배열

연결리스트

 

• 벡터(vector)
  • 동적으로 요소를 할당할 수 있는 동적 배열
  • 컴파일 시점에 개수를 모른다면 벡터를 써야 한다.
  • 중복을 허용하고 순서가 있고 랜덤 접근이 가능하다.
  • 탐색, 맨 뒤의 요소를 삭제하거나 삽입하는데 O(1)
    맨 뒤나 맨 앞이 아닌 요소를 삭제하고 삽입하는데 O(n)이 걸린다.

 

• 스택(stack)
  • 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO, Last In First Out)
  • 재귀적인 함수, 알고리즘, 웹 브라우저 방문 기록 등에 사용된다.
  • 삽입 및 삭제에 O(1), 탐색에 O(n)

 

• 큐(queue)
  • 먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO, First In First Out)
  • 스택과는 반대 개념
  • CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용된다.
  • 삽입 및 삭제에 O(1), 탐색에 O(n)

---

 

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

 

• 그래프(graph)
  • 정점과 간선으로 이루어진 집합 또는 자료 구조
  • 정점과 간선
    • 어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 했을 때
      '어떠한 곳'은 정점(vertex), '무언가'는 간선(edge)
    • ex) 짝사랑은 단방향 간선, 둘 다 좋아하면 양방향 간선
  • 가중치
    • 간선과 정점 사이에 드는 비용
    • ex) 1번 노드와 2번 노드까지 가는 비용이 한 칸이라면, 1번 노드에서 2번 노드까지의 가중치도 한 칸

 

• 트리
  • 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있다.
  • 트리 구조로 배열된 일종의 계층적 데이터의 집합
  • 트리로 이루어진 집합을 숲이라고 한다.
  • 트리의 특징
    • 부모, 자식 계층 구조를 가진다.
    • 같은 경로상에서 어떤 노드보다 위에 있으면 부모, 아래에 있으면 자식 노드가 된다.
  • 트리의 구성
    • 루트 노드, 내부 노드, 리프 노드 등으로 구성된다.
      • 루트 노드 : 가장 위에 있는 노드
        트리를 탐색할 때 루트 노드를 중심으로 탐색하면 문제가 쉽게 풀리는 경우가 많다.
      • 내부 노드 : 루트 노드와 리프 노드 사이에 있는 노드
      • 리프 노드 : 자식 노드가 없는 노드
  • 트리의 높이와 레벨
    • 깊이, 레벨 : 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리
    • 높이 : 루트 노드부터 리프 노드까지 거리 중 가장 긴 거리
    • 서브트리 : 트리 내의 하위 집합, 트리 내에 있는 부분집합

 

• 이진트리 : 자식의 노드 수가 두 개 이하인 트리
  • 정이진트리(full binary tree) : 자식 노드가 0 또는 두 개인 이진트리
  • 완전 이진트리(complete binary tree) : 왼쪽에서부터 채워져 있는 이진트리
  • 변질 이진트리(degenerate binary tree) : 자식 노드가 하나밖에 없는 이진트리
  • 포화 이진트리(perfect binary tree) : 모든 노드가 꽉 차 있는 이진트리
  • 균형 이진트리(balanced binary tree) : 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진트리
    • ex) map, set을 구성하는 레드 블랙 트리
      

 

• 이진 탐색 트리(BST)
  • 노드의 오른쪽 하위 트리에는 '노드 값보다 큰 값'이 있는 노드만 포함되고,
    왼쪽 하위 트리에는 '노드 값보다 작은 값'이 들어 있는 트리
  • '검색'을 하기 용이하다
  • 보통 요소를 찾을 때 O(logn)이 걸리며, 최악의 경우 O(n)이 걸린다.
    그 이유는 삽입 순서에 따라 선형적일 수 있기 때문.

 

• AVL 트리(Adelson-Velsky and Landis tree)
  • 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리
  • 두 자식 서브트리의 높이는 항상 최대 1만큼 차이 난다.
  • 탐색, 삽입, 삭제 모두 O(logn)이며,
    삽입, 삭제를 할 때마다 균형이 안 맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전시키며 균형을 잡는다.

 

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

 

• 힙(heap)
  • 완전 이진트리 기반의 자료 구조
  • 최대힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 한다.
  • 최소힙 : 최소힙에서 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 한다.
  • 최대힙의 삽입
    • 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
    • 새로운 노드를 부모 노드들과의 크기를 비교하며 교환해서 힙의 성질을 만족시킨다.
  • 최대힙의 삭제
    • 최대힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제되고,
      그 이후 마지막 노드와 루트 노드를 스왑 하여 또다시 스왑 등의 과정을 거쳐 재구성된다.

최대힙의 삽입

 

• 우선순위 큐(= 우선순위 대기열)
  • 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료 구조
  • 힙을 기반으로 구현된다

우선순위 큐와 힙

 

• 맵(map)
  • 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조
  • 레드 블랙 트리 자료 구조를 기반으로 형성되고, 삽입하면 자동으로 정렬된다.

 

• 셋(set)
  • 특정 순서에 따라 고유한 요소를 저장하는 컨테이너
  • 중복되는 요소는 없고 오로지 희소한(unique) 값만 저장하는 자료 구조

 

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

---

자료 구조는 매번 배워도 계속 잊어버리는 개념들 중 하나이다.. 완벽하게 이해를 하고 있지 않아서 그런 걸까?ㅠ

용어들과 익숙해지고 친해지려면 최대한 자주 보면서 계속 눈에 익히는 수밖에 없는 것 같다.
벡터, 이진트리의 종류, AVL 트리, 레드 블랙 트리는 처음 보는 개념들이니 한 번씩 더 눈에 담아보자.

아직 완강 못한 Udemy 자료 구조 강의와 Hello Coding 책을 참고해서
각 자료구조들의 특징을 제대로 파악하고, 다른 자료구조들과 비교하면서 차이점을 분석해 보자.
콤팩트하게 정리하는 부분에서는 블로그보단 노션이 확실히 편한 것 같기도~~

---

출처 : 면접을 위한 CS 전공지식 노트