자료구조 정리

• 자료구조 - 데이터를 효율적으로 저장하고 관리하기 위한 방법
• 알고리즘 - 어떤 목적을 이루기 위한 효율적인 연산 방법

시간복잡도

배열

• 일정한 메모리 공간을 차지하는 여러 요소들이 순차적으로 나열된 자료구조
• 각 요소는 0부터 시작하는 고유한 순서 번호인 index가 매겨짐, 인덱스로 배열의 요소 식별
• 배열과 유사한 컴퓨터 부품 - RAM
  • RAM은 어떤 주소에 접근하든 접근 시간이 일정(Random Access Memory), 배열도 마찬가지
  • 인덱스를 통해 요소에 접근하는 시간은 요소의 개수와 무관하게 일정 -> O(1)
  • 앞부터 차례대로 특정 요소가 있는지를 찾는 연산 -> O(n)
  • 특정 요소 추가/삭제 
    • 삽입 혹은 삭제 연산 이후에 모든 요소들의 재정렬 가정했을때 -> O(n)

연결 리스트 (linked list) 

• 노드의 모음으로 구성된 자료구조
• 노드
  • 저장하고자 하는 데이터(들)
  • 다음 노드의 위치(메모리 상의 주소) 정보
• 연결 리스트는 기본적으로 모든 노드들이 한 쪽 방향으로 꼬리에 꼬리를 무는 형태로 구성
• 연결리스트의 첫 번째 노드는 헤드(head), 마지막 노드는 꼬리(tail)라고 부름

• 연결 리스트를 구성하는 모든 노드는 반드시 메모리 내에 순차적으로 저장되어 있을 필요가 없음
• 즉, 연속적으로 구성되어 있는 데이터를 불연속적으로 저장할 때 유용
• 배열의 경우 인덱스가 주어지면 요소에 접근하는 시간이 일정하나, 연결 리스트에서 특정 요소에 접근할 때는 앞에서부터 순차적으로 접근할 수밖에 없기 때문에 O(n) 소요
• 요소 추가 / 삭제
  • 연결 리스트는 중간에 요소를 추가하거나 삭제하는 연산에서 재정렬 불필요
  • 삽입/삭제할 노드 위치가 주어지면 위치를 막론하고 노드에 접근하는 시간이 동일하므로 O(1) 소요

연결 리스트에서 요소 추가 및 삭제

• 싱글 연결 리스트
  • 한 쪽 방향으로 꼬리에 꼬리를 무는 형태를 띠는 기본적인 연결 리스트
  • 단방향 탐색만 가능 -> 특정 노드를 통해 다음 노드의 위치만 알 수 있고, 이전 노드의 위치는 알기 어려움
• 이중 연결 리스트
  • 노드 내에 다음 노드의 위치 정보뿐만 아니라 이전 노드의 위치 정보도 포함 - 양방향 탐색 가능
  • 저장 공간 필요 -> 한 노드에 2개의 위치 정보(메모리 주소)를 저장함
• 환형 연결 리스트 (원형 연결 리스트)
  • 꼬리 노드가 헤드 노드를 가리켜 노드들이 원형으로 구성된 연결 리스트
• 이중 연결 리스트로 구현된 환형 연결 리스트
  • 헤드 노드의 이전 노드가 꼬리 노드를 가리키고, 헤드 노드의 다음 노드가 헤드 노드를 가리키도록 구성
  • 모든 노드 데이터를 여러 차례 여러 방향으로 순회해야 할 때 유용하게 활용

스택

• 한 쪽에서만 데이터의 삽입 및 삭제가 가능한 자료구조
  • 후입선출(LIFO) 자료구조
  • push - 스택에 데이터를 저장하는 연산
  • pop - 스택에서 데이터를 빼내는 연산
  • 스택이 유용하게 사용되는 상황
    • 최근에 임시 저장한 데이터를 가장 먼저 활용해야 할 때
    • 뒤로가기 기능을 만들고 싶을 때

큐

• 한 쪽으로 데이터를 삽입하고, 다른 한 쪽으로 데이터를 삭제할 수 있는 자료구조
• 선입선출(FIFO, First In First Out) 자료구조
  • enqueue - 큐의 한 쪽 끝에 데이터를 삽입하는 연산
  • dequeue - 다른 한 쪽 끝으로 데이터를 빼내는(삭제하는) 연산
• 큐는 임시 저장된 데이터를 차례 차례 내보내거나 꺼내와야 하는 각종 버퍼(buffer)로도 활용
  • 줄 세우기에 자주 사용
  • 큐 또한 배열이나 스택처럼 다른 자료구조나 알고리즘 구현에 재료로 자주 사용
• 원형 큐 (circular queue)
  • 데이터를 삽입하는 쪽과 삭제하는 쪽, 양쪽을 하나로 연결해 원형으로 사용하는 자료구조
• 덱(deque) - 양방향 큐(double-ended queue)
  • 양쪽으로 데이터를 삽입/삭제할 수 있는 큐
• 우선순위 큐(priority queue)
  • 정해진 우선순위가 높은 순으로 처리되는 큐
  • 우선순위 큐는 힙(heap) 자료구조를 기반으로 구현

해시 테이블

• 해시 테이블 - 키와 값의 대응으로 이루어진 표(테이블)와 같은 자료구조
  • 키: 해시 테이블에 대한 입력
  • 값: 키를 통해 얻고자 하는 데이터
• 해시 테이블의 구조와 동작
  • 키를 통해 얻고자 하는 데이터는 버킷(bucket)에 저장 
    • 버킷은 여러 개가 존재하며, 버킷들은 배열을 형성함
  • 해시 함수는 키를 인자로 버킷에 접근할 인덱스 반환
    • 키를 해시 함수에 통과시켜 원하는 버킷에 접근

• 로드 팩터(load factor) - 해시 테이블에 저장된 데이터 수를 버킷의 수로 나눈 값
  • 해시 테이블이 현재 얼마나 가득 차있는지에 대한 지표
  • 로드 팩터가 클수록 해시 테이블의 성능이 떨어짐
• 빠른 검색속도 -> 검색, 삽입, 삭제 연산의 시간 복잡도는 O(1), 입력과 무관하게 항상 일정한 속도 보장
  • 속도가 빠른 만큼 상대적으로 많은 메모리 공간 소모
  • 해시 충돌 문제 -> 서로 다른 키에 대해 같은 해시 값이 대응되는 상황, 보안 상의 위험 발생 가능
    • 체이닝(chaining) - 충돌이 발생한 데이터를 연결 리스트로 추가
      • 하나의 테이블 인덱스에 여러 데이터가 연결 리스트의 노드로서 존재할 수 있음
      • 서로 다른 키가 같은 위치로 해시되어도 단순히 연결 리스트 노드만 추가
      • 충돌이 발생할 때마다 연결 리스트의 노드가 추가된다면 해시 테이블의 성능 저하 우려
    • 개방 주소법(open addressing)
      • 충돌이 발생했을 때, 충돌이 발생한 버킷의 인덱스가 아닌 다른 인덱스에 데이터를 저장하는 방법
      • 조사(probe) - 충돌이 발생했을 때 비어 있는 다른 버킷의 인덱스를 찾는 과정
      • 선형 조사법(linear probing)
        • 충돌이 발생한 인덱스의 다음 인덱스부터 순차적으로 가용한 인덱스 탐색
        • 데이터의 군집화 
          • 선형 조사법의 문제
          • 해시 충돌이 발생하는 인덱스 인근에 충돌이 발생한 여러 데이터가 몰려 저장될 수 있음
          • 군집화되면 오랜 순차 탐색이 필요 -> 성능 악화
    • 이중 해싱(double hashing)
      • 2개의 해시 함수를 사용
      • 충돌이 발생 시 다른 해시 함수(보조 해시 함수) 해시 값만큼 떨어진 거리에 위치한 인덱스를 찾는 방법
      • 해시 함수를 통해 무작위로 인덱스가 생성될 수 있다면 선형 조사법의 군집화 문제를 상당 부분 피할 수 있음

좌: 체이닝, 우: 개방 주소법

• 해시 함수(hash function)
  • 임의의 길이를 지닌 데이터를 고정된 길이의 데이터로 변환하는 단방향 함수
  • 단방향 함수이기 때문에 입력 데이터를 고정된 해시 값으로 변환할 수는 있어도 역으로 해시값을 토대로 입력 데이터를 유추하기는 어려움
  • 해시 값은 비밀번호 저장할 때도 사용
  • 무작위 값을 만들거나 단방향 암호를 만들 때, 데이터의 무결성을 검증하기 위해 사용
    1. 데이터 전송 전에 송신자가 데이터에 대한 해시값을 먼저 계산한 뒤, 이를 데이터와 함께 전송
    2. 수신자는 데이터로 해시 값을 계산한 뒤, 계산된 해시 값과 전달받은 해시 값 비교
    3. 두 값이 일치하면 바르게 전송

• 해시 알고리즘
  • 해시 함수의 연산 방법
  • 대표적인 해시 알고리즘 - MD5, SHA-1, SHA-256, SHA-512, SHA3, HMAC 등
  • 같은 데이터라도 적용된 해시 알고리즘이 다르면 해시 값의 길이나 값이 달라짐

트리

• 계층적 구조를 표현하기 위한 자료구조
• 데이터가 저장되어 있는 노드, 노드와 노드를 연결하는 간선(edge) 또는 링크(link)로 구성
• 노드는 상하 관계 형성
• 루트 노드(root node): 부모 노드가 없는 최상단 노드
• 리프 노드(leaf node): 더 이상의 자식 노드가 없는 최하단 노드
• 차수(degree): 각 노드가 갖는 자식 노드의 수
• 레벨(level): 루트 노드에서 시작해 특정 노드에 이르기까지 거치는 간선 수 
  • 트리의 깊이와 같은 개념
  • 가장 높은 레벨 = 트리의 높이
• 서브트리(subtree): 트리 안에 포함되어 있는 트리
• 하나의 노드를 데이터 저장 공간 + 자식 노드의 위치 정보(메모리 상의 주소) 저장동간의 모음으로 간주

 

트리의 순회

• 트리의 모든 노드를 한 번씩 방문하는 것
• 전위 순회
  • 루트 노드부터 시작, 왼쪽 서브트리 전위 순회, 오른쪽 서브트리 전위 순회
  • a -> b -> d -> h -> i -> e -> j -> k -> c -> f -> l -> g

• 중위 순회
  
  • 왼쪽 서브트리 중위 순회 -> 루트 노드 -> 오른쪽 서브트리 중위 순회
  • h -> d -> i -> b -> j -> e -> k -> a -> l -> f -> c -> g
• 후위 순회
  • 왼쪽 서브트리 후위 순회 -> 오른쪽 서브트리 후위 순회 -> 루트 노드
  • h -> i -> d -> j -> k -> e -> b -> l -> f -> g -> c ->a

이진 트리 (binary tree)

• 자식 노드의 개수가 2개 이하인 트리
• 편향 이진 트리
  • 노드 방향이 편향됨, 트리의 모든 노드가 일렬로 구성
• 정 이진 트리 
  • 자식 노드의 개수가 1개가 아닌 이진 트리 (즉, 자식 노드의 개수가 0 또는 2개인 이진 트리)

• 포화 이진 트리
  • 리프 노드를 제외한 모든 노드들이 자식 노드를 2개씩 가지고 있고, 모든 리프 노드의 레벨이 동일한 이진 트리
• 완전 이진 트리
  • 마지막 레벨을 제외한 모든 레벨이 2개의 자식 노드를 가지며, 마지막 레벨의 노드들이 왼쪽부터 존재하는 이진트리

• 이진 탐색 트리 (BST, Binary Search Tree)
  • 특정 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값을 지닌 노드들이 있고, 오른쪽 서브트리에는 해당 노드보다 큰 값을 지닌 노드들이 있는 구조의 이진 트리
  • 이진 탐색 트리를 활용하면 O(log n)으로 원하는 값을 탐색 가능
  • 예외 - 편향 이진 트리의 경우 탐색 속도 O(n), 이진 탐색 트리를 이용하는 경우 최악의 상황

• 힙(heap)
  • 탐색에 특화된 또 다른 완전 이진 트리의 일종
  • 주로 최댓값과 최솟값을 빠르게 찾기 위해 사용
  • 이진 탐색 트리와 유사하게 일반적으로 탐색에 O(log n)의 시간 복잡도가 소요
  • 최대힙 - 부모 노드가 자식 노드의 값보다 큰 값으로 이루어진 이진 트리
  • 최소힙 - 부모 노드가 자식 노드의 값보다 작은 값으로 이루어진 이진 트리
  • 우선순위 큐는 최대 힙으로 구현
    • 최대 힙을 구현 -> 최상단 루트 노드는 언제나 우선순위가 가장 높은 값을 가지게 됨
    • 우선순위 큐 저장 순서와 무관하게, 우선순위 큐에서 데이터를 빼낼 때는 우선순위가 높은 데이터 순으로 걷어낼 수 있음

 

균형을 맞추는 트리: RB 트리

• 이진 탐색 트리의 문제점
  • 삽입, 삭제 연산을 반복하는 과정에서 트리가 한 쪽으로만 자라나는 편향된 트리가 될 수 있음
  • 같은 노드의 집합으로 트리를 만들어도, 트리를 만드는 순서에 따라 편향된 트리가 될 수 있음
    • 이 경우 편향 트리의 탐색 속도 = O(n)
    • 연결 리스트와 다를 바 없게 되고, 사실상 트리 자료구조의 사용 이유가 없어짐

• 자가 균형 이진 탐색 트리
  • 왼쪽 서브트리와 오른쪽 서브트리 높이의 균형을 맞추는 특별한 이진 탐색 트리
  • AVL 트리 (Adelson-Velsky and Landis Tree)
  • RB 트리 (Red Black Tree)
    • RB 트리는 컴퓨터 과학 전반에 녹아 있는 근원적인 자료구조 중 하나
    • 리눅스의 CFS 스케줄러에도 RB 트리가 사용되며, 프로그래밍 언어 내부 구현에서도 RB 트리가 사용
    • 모든 노드를 빨간색 혹은 검은색으로 칠해서 균형을 유지하는 트리
    • 노드에 색상을 칠하는 규칙
      • 루트 노드는 블랙 노드
      • 리프 노드는 블랙 노드
      • 레드 노드의 자식 노드는 블랙 노드
      • 어떤 노드에서 리프 노드에 이르는 경로 속 블랙 노드 수는 같음
      • 새로운 노드 삽입(*삽입 노드는 레드 노드) 시 RB 트리에 부합하지 않게 되면, 색상을 재지정하거나 트리의 회전으로 부합하게 만듦

대용량 입출력을 위한 트리: B 트리

• B트리는 다진 탐색 트리의 일종
  • 다진 탐색 트리: 한 노드가 여러 자식 노드를 가질 수 있는 탐색 트리
  • B 트리의 한 노드가 가질 수 있는 최소/최대 자식 노드 수는 정해져 있음
  • M차 B 트리 -> 한 노드가 가질 수 있는 최대 자식 노드의 개수가 M개인 B 트리
  • M차 B트리가 가질 수 있는 최소 자식 노드의 개수는 [M/2]개
    • 루트, 리프 노드를 제외
    • ex) 5차 B트리 -> 최대 5개의 자식 노드, (루트, 리프 노드를 제외한) 노드들은 최소 3개의 자식 노드를 가질 수 있음
• B 트리의 각 노드에는 하나 이상의 키값이 존재하고, 각 키들이 오름차순으로 저장
  • 일반적으로 키는 데이터를 찾을 인덱스로 활용
  • 키가 N개인 노드가 가질 수 있는 자식 노드의 수는 반드시 N+1개

• B트리의 활용 -> 파일 시스템, 데이터베이스와 같이 대량의 데이터를 기반으로 탐색, 접근, 저장을 수행할 때 활용
  • 최소한의 입출력 연산으로 파일 시스템, 데이터베이스 데이터 탐색/접근/저장
• B+ 트리(B트리의 변형)
  • B+ 트리에서는 실질적인 데이터가 모두 최하위 리프 노드에 위치
  • 최하위 리프 노드는 연결 리스트로 구성 -> 다른 리프 노드들 간의 범위 연산 용이

그래프

• 정점(vertex)을 간선(edge) 혹은 링크(link)로 연결한 형태의 자료구조
• 연결 관계를 표현하는 자료구조
• 트리도 그래프의 일종
  • 트리는 사이클을 형성하지 않고 연결된 노드 간에 상하 관계를 가짐 (계층적 구조)
  • 그래프는 사이클을 형성할 수 있고, 이웃한 정점까지 상하 관계를 갖지도 않음(더 일반적인 연결 관계 표현)

• 연결 그래프 - 그래프 상에 있는 임의의 두 정점 사이의 경로가 존재
• 비연결 그래프 - 어떤 정점 사이에는 경로가 존재하지 않음
• 방향 그래프 - 간선에 방향이 있는 그래프
• 무방향 그래프 - 방향이 없는 그래프 (사실상 양방향 그래프)
• 가중치 그래프
  • 간선에 가중치가 부여된 그래프
  • 간선에 부여된 값인 가중치는 비용이라고도 함
  • 간선에 부여할 수 있는 값이라면 양수, 음수 모두 가능
• 서브 그래프 - 부분 그래프
  • 특정 그래프의 정점과 간선의 일부분으로 이루어진 그래프

그래프의 구현 방법

• 인접 행렬로 표현 -> 이차원 배열을 기반으로 그래프를 구현
  • N은 정점의 개수
  • N*N 크기의 행렬로 그래프를 표현하는 방법
  • N*N 행렬의 <행, 열> 값은 <출발 정점, 도착 정점>
  • 두 정점이 단순히 연결되었을 때는 1, 연결되지 않았을 때는 0으로 표기
  • 가중치 그래프의 경우, 행렬에 가중치를 기입

정점의 개수가 4개이므로 4*4 크기의 이차원 배열로 나타낼 수 있음

• 인접 리스트로 표현 -> 연결 리스트를 기반으로 구현
  • 가중치 그래프의 경우 간선에 연결된 노드 정보뿐 아니라 간선에 할당된 가중치까지 함께 하나의 노드로 표현

 

그래프 기반 연산

1. 깊이 우선 탐색 (DFS, Depth-First Search)

• 그래프에서 더 이상 방문 가능한 정점이 없을 때까지 최대한 깊이 탐색하기를 반복하는 탐색 방법

a -> b -> e -> c -> f -> d

• 깊이 우선 탐색 구현
  • 정점 a 부터 탐색을 시작 -> 인접한 정점이 2개 이상일 경우에는 알파벳 순으로 탐색한다고 가정
  • 배열 & 스택: 깊이 우선 탐색 알고리즘 구현 시 활용
    • 배열: 특정 정점의 방문 여부를 확인 -> 미방문 정점을 파악하기 위해 방문한 적이 있는 정점들을 배열로 관리
    • 스택: 정점 방문 도중 뒤로가기가 필요할 때 사용 (위 이미지의 그래프에선, 노드 방문 시 push, 해당 노드와 연결된 간선이 없을 때 pop)

2. 너비 우선 탐색 (BFS, Breadth-First Search)

a -> b -> c -> d -> e -> f

• 최대한 넓게 탐색하기를 반복하는 탐색 방법
• 배열 & 큐: 너비 우선 탐색 알고리즘 구현 시 활용
  • 배열: 특정 정점의 방문 여부를 확인
  • 큐: 연결된 정점들을 줄 세우듯 저장