[엘리스 AI 트랙 2기] 2주차-실시간 이론강의. 자료구조(06/28)

자료의 출처는 '엘리스 AI 트랙 2기 (https://aitrack.elice.io/)' 실시간 강의이며, 학습 후 정리한 내용입니다.

⚡️올바르지 않은 내용이 있을 경우 댓글로 남겨주시면 감사하겠습니다.⚡️

---

실습

자료구조

자료구조는 컴퓨터 공학부에서도 1학기 전공 필수 과목

실시간 이론강의 시간에 모두 이해한다는 것은 거의 불가능하니 
 개인 시간을 내서라도 꼭 공부해야 하는 과목이다.

자료구조

자료구조란 데이터를 효율적으로 다루기 위한 기초학문으로, 데이터들을 어떻게 저장할 것인지, 저장한 데이터들을 어떻게 처리할 것인지를 정해야한다.

자료구조를 통해 언제 어떤 상황에서, 얼마나 많이 들어올지 모르는 데이터들을 효율적으로 저장하고, 추가 / 삭제하고, 검색하는 프로그램을 만든다.

대표적인 자료구조

• 배열 (Array)
• 스택 (Stack)
• 큐 (Queue)
• 링크드-리스트 (Linked-List)
• 트리 (Tree)
• 그래프 (Graph)
• 해시테이블 (Hash Table)

자료구조의 특징

데이터를 어떻게 저장할까 (삽입)

데이터를 어떻게 삭제할까 (삭제)

데이터를 어떻게 가져올까 (검색)

데이터를 어떻게 정렬할까 (Sorting...)

# 삽입, 삭제, 검색 등의 소요 시간까지 예측할 수 있어야 한다. (sorting은 제외해도 된다고 생각)

각 연산에 대해 동작하는 방법과 속도를 알아 두면 좋다.

Big-O notation

어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 방법으로

자료구조에서는 데이터 수의 증가량 대비 연산 속도의 증가량을 나타낸다.

O(n) 으로 표기하며, n은 자료의 수라고 생각하면 편하다.

O(1) : 자료의 수와 상관없이, 연산의 속도가 동일하다.

O(n) : 자료의 수가 증가하는 속도에 비례하여 연산의 속도가 증가한다.
O(n^2) : 자료의 수가 증가하는 속도의 제곱에 비례하여 연산의 속도가 증가한다.

O(log n) : 자료의 수가 증가하는 속도의 로그에 비례하여 연산의 속도가 증가한다.

Big-O 표기법은 주로 자료의 양에 따른 연산 속도 증가량을 대략적으로 판단하는데 쓰고,

보통 최악의 경우를 생각하고 판단함

이것을 시간복잡도라고 하고,

나의 프로그램이 어느 정도의 시간복잡도를 갖는지 판단하는 능력은 매우 중요하다.

# 시간복잡도를 고려하는 것이 코드의 성능과 연관되어 있다 -> 매우 중요!!!!

# 삽입, 삭제, 검색에 대한 시간 복잡도를 공부해볼 것 추천

---

배열

배열이란?

자료들을 순서대로 저장하는 가장 기본적인 자료구조

자료의 위치를 기반으로 검색하며, Random access가 가능하다.

메모리상에 연속적으로 저장되는 자료구조

배열의 데이터 타입과 크기를 갖는다.

데이터를 조회할 때는 데이터의 위치를 이용한다.


배열의 여러가지 연산 속도

배열에 원소를 수정하는데 얼마나 걸릴까?

수정하고 싶은 위치에 직접 수정해주면 OK!

배열 수정의 시간복잡도는 O(1)

배열에 원소를 삽입하는데 얼마나 걸릴까?

최악의 경우, 가장 앞에 원소를 삽입해야 하는 경우 O(n)

배열을 정렬하는 것은 얼마나 오래 걸릴까? O(n^2)

삭제할 때 최악의 경우: O(n)

O(n) - 선형 자료구조
# 배열은 무난한 자료 구조(엄청나게 빠르지도, 느리지도 않음)

---

스택 (Stack)

스택이란?

후입선출 (Last-In, First-Out / LIFO) => 프링글스 

즉, 가장 나중에 들어온 것이 먼저 나오는 자료구조

이름에서 알 수 있듯이, 원소를 계속 쌓는 형태 (회전 초밥집의 초밥 그릇)

스택의 연산

Push(x) : 스택에 x라는 원소를 넣는 함수

Pop : 스택에서 원소를 빼는 함수(top이 위치한 변수를 뺀다)

top : 스택의 가장 마지막 원소의 인덱스를 가리키는 변수

# 스택또한 배열 기반이다.

# 배열의 크기가 10이고, top이 마지막 인덱스를 가리키고 있으면 스택은 꽉 찬 상태이다.

# 배열의 크기와 상관 없이 top = -1이면 스택은 비어있는 상태다.

# 스택은 검색에는 좋은 방식은 아님 (시간 복잡도는 O(2n)이고, 뺏던 데이터는 다시 넣어주어야 하기 때문에 적합하지 않음)

스택의 사용

메모리의 콜 스택 (Call Stack)에 사용된다.

ex) 하노이의 탑....

---

큐 (Queue)

큐란?

선입선출 (First-In, First-Out) / FIFO) 
=> 놀이공원 대기열
즉, 가장 먼저 들어온 것이 먼저 나오는 자료구조

이름에서 알 수 있듯이, 원소를 들어온 순서대로 처리하는 자료구조

큐의 연산

Push(x) : 원소 x를 큐에 삽입하는 연산

Pop() : 큐의 가장 첫 번째 원소를 가져오는 연산

front : 큐의 가장 첫 원소를 가리킴

rear : 큐의 가장 마지막 원소를 가리킴

If front == rear, Queue is empty.

If (rear + 1) % (arraySize) == front, Queue is Full.
* Initial front & rear value = 0

큐의 사용

컴퓨터에서 큐는 주로 스케줄링 작업이 필요한 곳에 많이 사용

# 큐는 먼저 들어온 것이 먼저 나가므로, 큐는 직관적인 편이라고 생각

예를 들어, 무수히 쏟아지는 작업들을 순서대로 처리하기 위한 운영체제(OS)

비슷한 환경에서 작업들을 순서대로 처리하기 위한 Back-end Infrastructure

삽입 시간 복잡도: O(1)
삭제 시간 복잡도: O(1)
검색 시간 복잡도: O(n)
'''
큐는 검색과 잘 어울리지 않고, 많은 데이터를 순서대로 처리하는 데 적합

front = 0 rear = 0으로 변수를 설정할 경우
0번째 index는 버리게된다.

원형 큐의 경우 index가 꽉찰 경우에 add하면 0번째에 insert되는데, 이를 방지해야한다.

'''

우선순위 큐

단순히 선입선출이 아니라, 우선순위를 매기며 지속적으로 정렬하는 큐

최소 우선순위 큐 : 가장 작은 값이 먼저 나오는 큐

최대 우선순위 큐 : 가장 큰 값이 먼저 나오는 큐

---

Linked-List

링크드 리스트란?

배열처럼 자료들을 순서대로 저장하지만, 현재 원소가 다음 원소를 가리키도록 저장하는 자료구조

배열과 차이점

탐색

배열은 각 원소의 위치를 기반으로 Random-Access가 가능하지만,

링크드 리스트는 Random-Access가 불가능하다.

따라서, 링크드 리스트에서 어떤 위치의 원소에 접근하고자 할 때는,


첫 번째부터 찾고자 하는 위치까지 순서대로 들어가면서 찾아야 한다.

# 검색 시간 복잡도: O(n)

삽입, 삭제

배열에서 원소를 삽입하려면 중간에 자리를 만들기 위해 이후의 모든 원소를 뒤로 미뤄야 하지만,

링크드 리스트에서는 가리키고 있는 다음 원소의 정보만 바꿔주면 된다.

# 해당 언어가 garbage collecting 지원여부를 확인해볼 것(코테를 위해)

링크드 리스트 연산의 속도

탐색 – O(N)

삽입/ 삭제–O(1)orO(N)
O(1) : 단순하게 삽입, 삭제 작업만을 생각해볼 경우

O(N) : 처음부터 삽입, 삭제 작업까지 생각해볼 경우

링크드 리스트의 사용

Java의 ArrayList, List 종류들

이외의 리스트

Double Linked List

# Single Linked List는 처음 공부할때 쓸거 아니면 잘 사용하지 않는다.
더블은 양쪽을 모두 저장해야하기 때문에 용량을 더 차지 한다는 단점이 있다.
일반적으로는 리스트는 내장된 형태를 많이 쓰기 때문에, 그걸 따라가는 경향이 큰 것 같다.

---

Hash-Table

해시 테이블이란?

해시함수를 이용하여 자료를 (Key – Value) 쌍으로 저장하는 자료구조

해시 함수란?

원본 자료를 정해진 알고리즘을 이용해 다른 값으로 바꾸는 함수로, 단방향 함수, 또는 비가역적인 함수

# 해시 함수의 역은 불가능하다고 볼 수 있다.

Ex) SHA1, SHA3, SHA256, SHA512, MD5, etc...

해시 함수를 사용하는 이유

해시 테이블은 Key-Value로 이루어진 자료의 쌍
원본 자료의 해시값을 Key로 사용하기 위해 해시함수를 사용

(원본 자료의 해시값을 배열의 index로 사용하기 위해 해시 함수를 사용한다.)

해시 Conflict

자료의 해시값을 이용해 구한 index가 겹치는 경우, Conflict이 발생했다고 한다

해시 Conflitc 극복 전략

1. 충돌이 발생한 인덱스 바로 뒤에다가 삽입한다. (Open-Addressing)

# 단점: 테이블이 꽉 찰 경우 넣을 수 없다.
2. 링크드 리스트를 이용하여 동일 인덱스에 계속 삽입한다. (Separate chaining)

# 링크드 리스트로 배열을 만든다!

해시테이블의 연산 속도

조회

Open Addressing
최악의 경우 O(N) -> 모든 원소가 Conflict이 발생해서 가장 끝에 위치하는 경우

통상적인 경우 O(1)

Separate Chaining

최악의 경우 O(N) -> 마찬가지로 모든 원소가 Conflict 발생 및 리스트 끝 조회

통상적인 경우 O(1)

해시테이블의 사용

Key-value로 데이터를 저장할 수 있고, 

연산 속도가 매우 빠르기 때문에 Front, Back-end를 가리지 않고 많이 사용되는 자료구조

# 단점: 정렬 불가능 문제가 있다. (이런 상황에선 이진 탐색 트리 구현체를 사용해서 해결, 뒤에 나옴)

Java의 Map, Python의 Dictionary 구조 등 유용하게 사용

---

Tree

트리란?

부모 노드와 자식 노드로 이루어진 나무 모양의 자료구조

ex) 컴퓨터의 파일 시스템

노드

트리의 각 노드는 적당한 자료와 자식 노드의 주소 혹은 레퍼런스를 포함하는 데이터

Bianry Tree(이진 트리)

바이너리 트리(Binary Tree)는 자식이 최대 2개인 트리

ex) Binary Search를 구현할 때, 바이너리 트리를 이용

Binary Search Tree (BST)

부모 노드의 데이터를 x라고 했을 때,

삽입되는 데이터가 x보다 작으면 왼쪽 자식 X보다 크면 오른쪽 자식에 추가

삭제의 경우 해당 노드를 삭제하고, 아래 두개의 노드 중 하나를 삭제된 노드의 자리에 위치한다.

• 왼쪽 SubTree중 가장 큰 값
• 오른쪽 SubTree중 가장 작은 값

BST의 장점

검색 속도가 매우 빠름 O(logN)

일반적인 삽입, 삭제, 검색의 시간 복잡도 : O(log n)
그러나 최악의 경우 삽입, 삭제, 검색의 시간 복잡도는 O(n)

배열을 이용한 BST의 구현

i번째 인덱스의 자식 노드는 (2*i + 1), (2*i + 2)번째 인덱스로 한다.

BST Worst Case

자식노드가 1개씩 밖에 없는 연속된 트리 -> O(n)

이외의 트리

BST가 한 쪽으로 편향될 가능성이 있기 때문에
이를 방지하기 위해 적절하게 트리를 재구성해주는 Balanced Tree도 존재

---

참고

• https://devraphy.tistory.com/88

Algorithm - 자료구조 핵심정리

• https://devraphy.tistory.com/75?category=928262

Advanced Algorithm - 그래프의 이해(basic concepts of the graph)