코딩테스트 문제를 보다 효율적으로 풀기 위해 '자료구조가 왜 존재하는지', '어떤 종류의 개념들이 있는지'에 대해 간단히 정리하고자 한다.
자료구조란?
"현실을 프로그래밍적으로 표현한 것"
데이터 값의 모임, 데이터 간의 관계, 데이터에 적용할 수 있는 함수나 명령을 자료구조라고 한다. 자료구조를 통해 보다 효율적인 알고리즘을 사용할 수 있고 큰 데이터를 효율적으로 관리할 수 있기 때문에, 코드로 로직을 구성할 때 참고하면 도움을 받을 수 있다.
1. Hash Table
Key, Value로 데이터를 저장하는 자료구조 중 하나이다.
검색 속도가 빠르다는 장점이 있다.
Hashing 흐름:
HashFunction(Key) -> Hash Code -> Index(HashValue) -> Value
- Key는 원래 데이터를 뜻하며 string, number, file data 등이 올 수 있다.
- Hash Code는 항상 정수이며, 데이터 위치에 바로 접근할 수 있다.
- Index는 일종의 공간으로 이 공간을 잘 나누는 것이 공간 사용 효율에 큰 영향을 끼친다. 공간이 부족하다면 Collision(해시충돌) 현상이 나타날 수 있다.
Collision(해시충돌) 현상
해시충돌을 최소화하는 것이 좋은 해시 알고리즘이다.
발생원인:
1. different keys -> same code
2. different code -> same index
2. Big-O
알고리즘의 성능을 수학적으로 표현해주는 표기법이다. 시간 복잡도를 판별할 때 많이 사용된다.
- 장점
-> 알고리즘의 시간, 공간 복잡도 표기.
-> 데이터 및 사용자 증가율에 따른 알고리즘 성능 예측.
1) O(1)
입력데이터의 크기에 상관 없이, 언제나 일정한 시간이 걸리는 알고리즘
2) O(n)
입력데이터의 크기만큼 시간이 걸리는 알고리즘
3) O(n²)
for문을 2 번 겹쳤을 때가 대표적인 예시로, i x j만큼 시간이 걸리는 알고리즘
4) O(n의 m제곱)
n을 m만큼 돌릴 때, 그만큼의 시간이 걸리는 알고리즘
5) O(n³)
3차원이다. n x n x n만큼의 시간이 걸리는 알고리즘
6) O(2ⁿ)
Fibonacci 함수가 대표적인 예다.
1, 1, 2, 3, 5, 8, 13 등 다음 숫자를 구하기 위해서는 n-1, n-2 수가 필요하기 때문에, 재귀함수를 통해 피보나치 수열을 구할 수 있다.
7) O(mⁿ)
8) O(logN)
검색시마다 판별할 데이터의 1/2이 줄어드는 알고리즘
2진 검색이 대표적이다.
속도가 현저히 빠르고, 데이터가 증가해도 성능이 좋다는 장점이 있다.
8) O(sqrt(n))
중요한 것!
Big-O 표기법에서 상수는 과감하게 버린다.
빅-오 표기법은 데이터 증가에 따른 처리시간의 증가율을 예측하고자 만들어진 표기법이다. 따라서 증가하지 않는 숫자는 신경쓰지 않기 때문에 고정된 상수도 신경쓰지 않는다.
3. Tree
계층구조를 표현할 때 사용하는 자료구조이다.
- root node: 부모가 없는 최상위 노드이다.
- leaf node(단말 노드): 자식이 없는 노드이다.
- size(크기): 트리에 포함된 모든 노드의 개수이다.
- depth(깊이): root node로부터의 거리이다. 예를 들어, root node는 0 깊이를 가지고, root node의 자식의 자식 노드는 2 깊이를 가진다.
- height(높이): 깊이 중 최댓값이다.
- degree(치수): 각 노드의 자식 방향 간선 개수이다. 즉, 각 노드가 지닌 가지의 수이다. (트리의 크기가 N일 때, 전체 간선 개수는 N-1이다.)
이진 탐색 트리
왼쪽 자식노드 값 < 부모노드 값 < 오른쪽 자식노드 값
만약 새로운 노드가 삽입되면, 위랑 동일하게 노드 순서를 변경한다.
트리 순회
각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정이다.
아래는 노드 방문 순서에 따른 분류이다.
전위 순회
부모노드 -> 왼쪽 자식노드 -> 오른쪽 자식노드
중위 순회
왼쪽 자식노드 -> 부모노드 -> 오른쪽 자식노드
후위 순회
왼쪽 자식노드 -> 오른쪽 자식노드 -> 부모노드
4. List
Array = fixed, static array
List = dynamic array
노드에는 링크 필드와 데이터 필드가 있다. 이 링크의 수와 흐름을 기준으로 List는 세 가지로 분류된다.
1) Singly Linked List
링크 1개 / 한 방향 이동
2) Doubly Linked List
링크 2개 / 양방향 이동
3) Circular Linked List
링크 1개 혹은 2개 / 환형 이동 (마지막 노드가 첫 번째 노드를 가리켜서 계속 회전한다.)
List 장/단점
장점:
- 메모리 효율이 높다.
- 중간 데이터 추가 및 삭제 효율이 높다.
중간에 한 요소를 삭제하거나 추가할 때, 링크 연결만 변경해주면 된다. 아무것도 링크가 연결되지 않은 요소는 가비지 컬렉팅에 의해 삭제된다.
단점:
- 링크 1개 당 4byte를 소모하므로, 데이터 저장 값을 많이 차지한다.
5. Priority Queue (우선순위 큐)
우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다.
(자료구조 -> 추출되는 데이터)
1. Stack -> 가장 나중에 삽입된 데이터
2. Queue -> 가장 먼저 삽입된 데이터
3. Priority Queue -> 가장 우선순위가 높은 데이터
구현방법
1) 리스트 이용
2) heap 이용 (완전 이진 트리를 따른다.)
- 최소힙
- 최대힙
(번외) 의사코드란?
프로그램을 작성할 때, 각 모듈이 작동하는 논리를 표현하기 위한 언어이다. 특정 문법이 아닌 일반언어로 코드를 흉내내어 알고리즘을 작성한 코드를 말한다.
