자료구조와 알고리즘
-
프로그램은 모두 자료 구조와 알고리즘으로 이루어져있다.
-
그렇기 때문에 효율적인 개발을 하기 위해선 이해가 필수적이다.
-
또한, 빠르게 변화하는 기술들과 달리 자료 구조와 알고리즘은 변하지 않으므로 배우면 좋다.
자료구조(Data Structure)
-
메모리를 효율적으로 사용하여 빠르고 안정적으로 데이터를 처리하는 것이 궁극적인 목표이다.
-
상황에 맞는 적절한 자료구조를 사용해야 효율적인 메모리 관리가 가능하다.
-
자료구조는 단순 구조, 선형 구조, 비선형 구조로 나뉜다.
-
단순 구조
- 정수
- 실수
- 문자열
- 논리
-
선형 구조
선형으로 이루어진 구조를 말하며, 한 원소 뒤에 하나의 원소만이 존재하는 형태를 가진다.
- 배열(Array)
- 연결 리스트(Linked List)
- 스택(Stack)
- 큐(Queue)
-
비선형 구조
선형 구조와 다르게 하나의 원소가 다른 여러 개의 원소와 관계를 맺을 수 있는 구조다.
- 트리(Tree)
- 그래프(Graph)
알고리즘(Algorithm)
-
정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것을 말한다.
-
특정 문제를 효율적이고 빠르게 처리하는 것이 목표
-
이진 탐색(Binary Search), 최단 경로(Shortest Path) 등이 여기에 해당한다.
빅오 표기법(Big-O notation)
-
개발자가 프로그램의 성능을 정확히 측정하기 어렵기 때문에, 대략적인 성능을 비교하기 위해서 상대적인 표기법을 사용하기로 함.
-
그렇게 탄생한 것이 빅오 표기법이다.
-
성능은 다음과 같다.
O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!)
- 빅오 표기법은 다양한 법칙이 있지만, 중요한건 상수와 가장 큰 영향력을 가지는 항 외의 항들은 무시한다.
선형 구조
배열(Array)
-
데이터를 연속적인 형태로 구성하며, index를 이용해 원소에 접근이 가능하다.
-
고정된 크기를 가지며, 일반적으로는 동적으로 크기를 늘릴 수 없다.
-
데이터 추가/삭제 시 빈 공간을 채우는 연산 때문에 O(N)의 시간 복잡도를 가진다.
연결 리스트(Linked List)
-
데이터의 추가/삭제 시 O(1)의 시간 복잡도를 가지기 때문에, 추가/삭제가 자주 일어나는 자료에 사용한다.
-
반대로 탐색은 O(N)의 시간 복잡도를 가지기 때문에, 배열과 상반된다고 볼 수 있다.
-
각 요소를 포인터로 연결하여 관리하며, 요소는 노드라고 부른다.
-
노드는 데이터 영역과 포인트 영역으로 분리된다.
-
첫 노드를 Head, 마지막 노드를 Tail 이라고 한다.
-
종류는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다.
-
단일 연결 리스트(Singly Linked List)
-
Head에서 Tail까지 단방향으로 이어지는 연결 리스트
-
각 노드의 포인터는 다음 노드만 가리킨다.
-
-
이중 연결 리스트(Doubly Linked List)
- 단일 연결 리스트와 다르게 이전 노드를 가리키는 포인터도 사용하기 때문에, 메모리를 더 많이 사용한다.
-
원형 연결 리스트(Circular Linked List)
- Tail 노드가 Head 노드를 가리키는 리스트다.
스택(Stack)
-
LIFO(Last In First Out) 구조로, 나중에 들어간 데이터가 먼저 나오는 형태로 되어있다.
-
배열과 연결 리스트를 이용해서 구현이 가능하며, 연결 리스트를 이용할 경우 Head 노드가 스택의 TOP이 된다.
큐(Queue)
-
FIFO(First In First Out) 구조로, 먼저 들어간 데이터가 먼저 나오는 형태로 되어있다.
-
큐의 가장 앞부분을 Front, 가장 뒷부분을 Rear라고 부른다.
-
데이터를 넣을때는 Enqueue, 데이터를 꺼낼때는 Dequeue 라고 한다.
-
선형 큐(Linear Queue)와 원형 큐(Circular Queue)가 있다.
-
선형 큐(Linear Queue)
-
배열을 이용해 구현이 가능하지만, Dequeue 동작시 동적 길이를 가지지 않는 배열의 특성상 length를 초과하는 경우가 생긴다.
-
그래서 보통 연결 리스트로 구현한다, 이때 Head가 Front가 되고, Tail이 Rear가 된다.
-
JavaScript의 배열 메서드 중 shift() 함수는 queue로 동작하는 것으로 보이지만, O(N)의 시간 복잡도를 가지기 때문에 사용하지 않는다.
JavaScript Array의
shift()함수는 기본적으로 O(N)으로 동작하지만, 요소가 적을 경우 JavaScript Engine이 어느정도 최적화를 해준다.
그러므로 알아서 잘 판단해서 사용하면 될 것 같다.
-
-
원형 큐(Circular Queue)
-
Front와 Rear가 연결되어있는 큐
-
한정된 메모리를 효율적으로 이용하려고 할 때 사용하는 자료구조다.
-
해시 테이블(Hash Table)
-
키(Key)를 해싱(Hashing)하여 나온 인덱스(Index)에 값을 저장하는 자료구조.
-
데이터 삽입은 O(1)의 시간이 소요되며, 키 값을 알고있다면 삭제와 탐색도 O(1)의 시간이 소요된다.
-
각 테이블에 해당하는 인덱스를 버킷(Bucket)이라고 부른다.
-
key-value 한 쌍으로 이루어져 있다.
-
최악의 경우 탐색에 O(N)의 시간이 소요될 수 있지만, 배열이나 연결 리스트보다는 낫다.
해시 함수
-
입력받은 값을 특정 범위 내의 숫자로 변경하는 함수.
-
특정한 구현 방법이 존재하지 않기 때문에, 개발자 임의로 구현해도 된다.
-
해시 함수의 결과가 동일한 경우가 생기는데, 이를 해시 충돌(Hash Collision)이라고 한다.
-
해시 충돌의 해결법은 대표적으로 선형 탐사법, 제곱 탐사법, 이중 해싱, 분리 연결법이 있다.
-
선형 탐사법(Linear Probing)
-
충돌이 발생하면 옆으로 한 칸씩 이동하는 방식.
-
개방 주소법(Open Address) 이라고도 부른다.
-
옮긴 곳에서 또 충돌이 일어나면 다시 한 칸씩 옮기기 때문에 최악의 경우 O(N)의 시간이 소요된다.
-
-
제곱 탐사법(Quadratic Probing)
-
충돌이 발생한 지점에서, 충돌이 발생한 횟수의 제곱만큼 옆으로 이동하는 방식.
-
선형 탐사법보다 데이터가 겹치는 경우가 적어진다.
-
- 이중 해싱(Double Hashing)
- 충돌이 발생하면 다른 해시 함수를 이용해서 새로운 인덱스를 만들어내는 방식.
-
분리 연결법(Seperate Chaining)
-
버킷의 값을 연결 리스트로 사용하여, 충돌이 발생하면 리스트에 값을 추가하는 방식.
-
최악의 경우, 하나의 버킷에 값이 무한정 중첩될 수 있다.
-
