자료구조

👉 자료구조는 사용하는 언어나 프레임워크에 따라 조금씩 다르며 가장 기본적으로 숙지하고 있어야 한다고 생각한다.
따라서 정보처리기사 필기를 준비하는 겸 자료구조에 대해 최대한 쉽게 학습해보려고 한다.

🔶정의

• 데이터를 저장하고
• 효율적(빠름, 정확)인 처리를 위해 사용

🔶분류

🔶Array & ArrayList & LinkedList

Array

Index를 통해 데이터를 호출

장점

• 임의 접근: index 사용
• 순차 접근: 연결리스트보다 빠르다.

  ❓ 연결리스트를 사용 안해봐서 잘 와닿지가 않았다.

단점

• 확장 불가
• 자료 삽입, 삭제가 어려움
• 메모리 재사용이 불가능

  💡 python에서 list보다는 tuple에 가까운 것 같다.

ArrayList

인덱스로 객체에 접근할 수 있고, 배열의 크기가 동적으로 할당되는 자료구조

장점

• 크기가 동적으로 할당되기 때문에 데이터 삽입/삭제 용이
• 인덱스를 사용해서 빠르게 접근 가능

단점

• 요소를 삽입/삭제하는 경우 데이터의 복사가 많아지기 때문에 성능저하 발생

LinkedList

• 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조. 포인터를 사용해서 연결된다.
• 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성

장점

• 크기를 동적으로 조절할 수 있다.
• 삽입/삭제 시 데이터를 복사하는 일이 없기 때문에 유리하다.
• 불연속적으로 메모리를 사용하기 때문에 메모리 관리와 재사용 용이

단점

• 임의접근이 불가능. 첫번째 노드부터 순차적으로 접근해야한다.
  -> 느림

요약

• Array
  인덱스로 빠르게 값을 찾을 수 있지만, 크기가 고정되어있어서 삽입/삭제가 불편하다.
• ArrayList
  인덱스로 빠르게 값을 찾을 수 있고 삽입/삭제가 용이하지만, 연산 수가 많아서 느리다.
• LinkedList
  인덱스로 접근할 수 없어서 검색은 느리지만, 이전/다음 노드의 주소값만 수정해주면 되기 때문에 삽입/삭제가 빠르다.

🔶Stack & Queue

Stack

LIFO(Last In First Out, 후입선출): 가장 나중에 들어온 것이 가장 먼저 나감

Queue

FIFO(First In First Out: 선입선출): 가장 먼저 들어온 것이 가장 먼저 나옴

• 시작과 끝을 표시하는 두 개의 포인터가 있다.
• F, Front 포인터: 가장 먼저 삽입된 자료의 기억 공간을 가리키는 포인터
• R, Rear 포인터: 가장 마지막에 삽입된 자료가 위치한 기억 공간을 가리키는 포인터

  💡 BFS 에서 주로 사용
  python은 deque라는 모듈을 불러와서 사용해야함.

🔶Tree

개념

• 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조
  ex) 조직도
• 트리 내에 다른 하위 트리가 있고, 그 하위 트리 안에 또 다른 하위 트리가 있는 재귀적 자료구조
• 노드(node): 하나의 기억 공간
• 간선(edge): 노드를 연결
• cycle이 존재할 수 없다.
• 부모와 자식 관계가 있음

특징

• 트리는 하나의 루트 노드를 가짐
• 루트 노드는 0개 이상의 자식 노드를 가지고, 그 자식 노드 또한 0개 이상의 자식 노드를 가지며, 이는 반복적(재귀적)으로 정의됨
• 모든 자식 노드는 한 개의 부모 노드만 가짐
• 데이터를 순차적으로 저장하지 않음 -> 비선형 자료구조
• 트리에는 사이클(cycle)이 존재할 수 없음
• 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성
• 노드가 n개인 트리는 항상 n-1개의 간선을 가짐
• 이진 트리, 이진 탐색 트리, 이진 힙(최대힙, 최소힙) 등

이진 트리(Binary Tree)

• 각 노드가 최대 2개의 자식을 갖음

  💡 Tree 알고리즘 문제에서 Heap과 함께 주로 나옴

🔶Heap

개념

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
• 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안됨
• 반정렬 상태(느슨한 정렬 상태) : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리
• 힙 트리는 중복된 값을 허용(이진 탐색 트리는 허용 X)
• 키 값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립(형제 사이에서는 성립 X)
• 각 노드의 자식 노드의 최대개수는 힙의 종류에 따라 다르지만, 대부분의 경우 자식 노드의 개수가 최대 2개인 이진 힙(binary heap) 사용
• 가장 높은(낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징 → 우선순위 큐와 같은 추상적 자료형 구현 가능

종류

최대 힙(max heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙
• key(부모 노드) ≥ key(자식 노드)

최소 힙(min heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙
• key(부모 노드) ≤ key(자식 노드)

💡 python에서 heapq 모듈로 사용합니다.

활용

• 우선순위 큐 구현
  - 배열, 연결리스트, 힙으로 구현 가능하지만, 힙으로 구현하는 것이 가장 효율적
  
• 허프만 코드 구현
• 힙 정렬 구현

🔶Hash

임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것

해시테이블?

해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 인덱스 또는 주소삼아 데이터를 key와 함께 저장하는 자료구조. key-value

해시함수

key를 고정된 길이의 hash로 변경해줌. hashing

해시충돌

서로 다른 key가 hashing 이후 값은 hash 값으로 나오는 경우

문제 해결

• Open Addressing (개방주소법) : 해시 충돌이 발생하면, 다른 해시 버킷에 해당 자료를 삽입하는 방식 이다. 버킷이란 바구니와 같은 개념으로 데이터를 저장하기 위한 공간이라고 생각하면 된다.

  1. Linear Probing (선형 탐사) : 정해진 고정 폭으로 옮겨 해시값의 중복을 피함

  2. Quadratic Probing (제곱 탐사) : 정해진 고정 폭을 제곱수(2차 함수)로 옮겨 해시값의 중복을 피함

  3. Double Hashing Probing (2차 해시 함수) : 충돌이 발생하면 2차 해시 함수를 사용하여 새로운 주소를 할당한다. 연산량이 위의 두가지보다 많이 요구된다.

     공개 주소 방식이라고도 불리는 이 알고리즘은 Collision 이 발생하면 데이터를 저장할 장소를 찾아 헤맨다. Worst Case 의 경우 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 되돌아 올 수 있다.

• Separate Chaining (분리 연결법) : 연결리스트로 노드를 계속 추가해나가는 방식 (제한 없이 계속 연결 가능, but 메모리 문제) 일반적으로 Open Addressing 은 Separate Chaining 보다 느리다. Open Addressing 의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문이다. 반면 Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조정할 수 있다면 Worst Case 에 가까워 지는 빈도를 줄일 수 있다. Java 7 에서는 Separate Chaining 방식을 사용하여 HashMap 을 구현하고 있다.
  • 연결 리스트를 사용하는 방식(Linked List) 각각의 버킷(bucket)들을 연결리스트(Linked List)로 만들어 Collision 이 발생하면 해당 bucket 의 list 에 추가하는 방식이다. 연결 리스트의 특징을 그대로 이어받아 삭제 또는 삽입이 간단하다. 하지만 단점도 그대로 물려받아 작은 데이터들을 저장할 때 연결 리스트 자체의 오버헤드가 부담이 된다. 또 다른 특징으로는, 버킷을 계속해서 사용하는 Open Address 방식에 비해 테이블의 확장을 늦출 수 있다.
  • Tree 를 사용하는 방식 (Red-Black Tree) 기본적인 알고리즘은 Separate Chaining 방식과 동일하며 연결 리스트 대신 트리를 사용하는 방식이다. 연결 리스트를 사용할 것인가와 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 key-value 쌍의 개수이다. 데이터의 개수가 적다면 링크드 리스트를 사용하는 것이 맞다. 트리는 기본적으로 메모리 사용량이 많기 때문이다. 데이터 개수가 적을 때 Worst Case 를 살펴보면 트리와 링크드 리스트의 성능 상 차이가 거의 없다. 따라서 메모리 측면을 봤을 때 데이터 개수가 적을 때는 링크드 리스트를 사용한다.

🔶Trie

prefix tree?

• retrieve (되찾다, 찾아오다)에서 유래
• 어떤 대상(문자열)을 찾아서 돌려준다는 의미
• 문자열에서 검색을 빠르게 도와주는 자료구조
• 검색어 자동완성, 문자열 검사, 검색 등에서 사용
• 시간 복잡도 O(N)에 검색 가능(문자열의 길이 N)
• 같은 부모노드(루트노드 제외)를 가진 자식들은 같은 접두어를 가진다
• 루트 노드는 비워두고 그 다음 노드부터 문자열의 문자 하나씩을 노드에 저장

장/단점

• 문자열 검색에서 시간 복잡도를 크게 줄여줌 ( O(N))
• 공간 복잡도가 크다는 단점
  - 알파벳 a-z(26개)에 대해 트라이를 구성한다면, 각 노드가 모든 알파벳에 대한 포인터 배열을 가지고 있어야 하므로 메모리 크기= (포인터의 크기) (포인터 배열의 개수(26개)) (총 노드의 개수)
  
  <그림> app, apple, apply, babo 라는 단어를 insert한 경우

출처

https://m.blog.naver.com/limje1623/221842023446