기초 자료구조

자료구조란?

자료를 쉽게 처리하기 위해 효율적으로 자료를 저장하는 방법이다. 각 데이터의 종류(가장 많이 쓰이는 연산)에 따라 알맞은 자료구조 선택이 중요하다.

시간복잡도와 공간 복잡도

자료구조와 알고리즘에 있어서 가장 중요한 것이 바로 시간복잡도와 공간복잡도라고 할 수 있다.

시간 복잡도(time complexity)

말 그대로 시간이 얼마나 걸리는지를 표현하는데 사용한다.
그러나 같은 프로그램이 실행되더라도 동시에 몇 개의 프로그램이 실행중인지, 하드웨어적인 스펙이 얼마나 되는지, 그 외 다양한 환경에 따라 실행 시간이 달라질 수 있다. 따라서 시간복잡도를 표현할 때는 단순히 실행 시간만을 가지고 표현하지 않는다.
일반적으로 우리는 시간복잡도를 계산할 때 RAM 모델 상에서 실행할 때 필요한 명령어의 개수를 다룬다.
최악의 경우 시간복잡도는 입력의 개수가 n인 모든 가능한 입력에 대한 최대 실행 시간을 말하고, 평균 시간복잡도는 크기 n인 입력에 대한 실행 시간의 평균을 말한다.
일반적으로 시간복잡도는 최악의 경우 시간복잡도를 의미한다.

공간복잡도(Space Complexity)

얼마만큼의 공간을 필요로 하는 지를 의미한다.
입력의 개수가 n일 때 사용하는 메모리의 양을 n에 따른 함수로 표현한다.
시간복잡도처럼 최악의 경우 공간 복잡도, 평균 공간 복잡도의 2가지로 나뉘며 일반적으로 공간 복잡도는 최악의 경우 공간복잡도를 의미한다.

빅-오 표기법

각각의 복잡도는 정확히 계산하기 보다 그 상계(Upper bound)를 표시하는 방법을 일반적으로 사용한다. T(n)이 다항식으로 표현이 된 경우 최고 차항의 차수가 빅-오가 된다.
정확히 표현하자면, 상수 $c$와 $n_0$가 존재할 때 $n \ge n_0$인 모든 n에 대하여 $T(n) \le c \cdot f(n)$을 만족할 때 $T(n) = O(f(n))$이라고 한다.
즉, f(n)의 상수배가 일정 수 이상인 모든 n에 대해 T(n)보다 크다면 그것이 O(n)이 되는 것이다.
예를 들어, $T(n) = 3n^3+100n+10000$이라고 하자. $T(n) = O(n^3)$이고, $T(n) = O(n^4)$이지만 $T(n) = O(n^2)$는 될 수 없다.
일반적으로는 알고리즘의 시간복잡도는 작을수록 유리하기 때문에 빅-오표기법으로 표기하더라도 상계의 하한값으로 표기한다.

선형 자료구조

자료구조는 크게 선형구조와 비선형구조로 나뉜다. 선형구조는 일반적으로 배열 형태를 생각하면 된다. 세부적으로는 리스트, 스택, 큐, 덱이 있다.

리스트

리스트는 자료를 순차적으로 나열하여 저장한다. 구현 방법에 따라 선형 리스트와 연결 리스트로 나뉜다.

선형 리스트(Array)

연속되는 기억장소에 저장되는 리스트이다.
즉, 논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 인덱스(index)로 각각의 원소(element)에 접근 할 수 있다. 따라서 찾고자 하는 원소의 인덱스 값을 알고 있다면 O(1)에 해당 원소로 접근할 수 있다. 즉 random access가 가능하다. 장점 접근속도가 빠르다.
구현이 간단하다.
단점 삽입 - 삭제 연산 시간이 오래 걸린다.(최악의 경우 O(N))
이는 삽입 - 삭제시 배열의 연속성이 깨지기 때문에 원소들을 shift해줘야 하는 비용(cost)이 발생하기 때문이다.

연결 리스트

각 노드가 데이터와 다음 노드의 주소를 가지고 연결돼있는 방식이다.
장점 삽입 - 삭제 연산이 상수시간 안에 해결된다.(O(1))
단점 접근 시간이 O(n)이다.
인덱스로 접근할 수 없다.
원하는 위치 주소값을 가지고 있지 않다면 삽입 - 삭제 시간또한 탐색시간을 포함해 O(n)이 소요된다.

Tree를 구현할 때 유용하게 사용된다.

스택(Stack)

FILO(First In Last Out)구조이다. 처음에 들어간 원소는 가장 마지막에 나오고, 항상 꼭대기에 마지막에 들어간 원소가 있다. 삽입, 삭제, 꼭대기 원소 확인의 시간복잡도는 모두 상수시간이다.
기본 구현 문제 : [백준] 10828 - 스택
스택을 활용한 문제 : [백준] 2493 - 탑

큐(Queue)

FIFO(First In First Out)구조이다. 처음에 들어간 원소가 가장 먼저 나온다. 일반적으로 은행 대기줄을 예시로 들고는 한다. 원소의 삽입, 삭제, 가장 앞 / 뒤 원소의 확인 시간 복잡도는 모두 상수시간이다.
기본 구현 문제 : [백준] 10845 - 큐
큐를 활용한 문제 : [백준] 2164 - 카드2

덱(Deque)

양방향 자료구조로, 스택과 큐를 합쳐놓은 것이라고 할 수 있다. 양쪽에서 삽입 / 삭제가 일어나는 경우에 사용한다. 따라서 삽입 / 삭제를 제한된 방향으로만 사용할경우 Queue, Stack처럼 사용할 수 있다. 역시 삽입, 삭제, 원소 확인 시간은 상수 시간이다. 기본 구현 문제 : [백준] 10866 - 덱
덱을 활용한 문제 : [백준] 5430 - AC

비선형 자료구조

트리

트리는 자료 사이의 계층적 구조를 나타내는 자료구조이다.
트리는 사이클이 없는 연결 그래프로, 즉 그래프의 일종이다.
트리를 구성하고 있는 구성 요소들은 다음과 같다.

• Node(노드) : 트리를 구성하고 있는 각각의 요소
• Edge(간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선
• Root Node(루트 노드) : 트리 구조에서 최상위에 존재하는 노드
• Terminal Node(단말 노드, (= leaf, 외부 노드(external node)) : 하위에 다른 노드가 연결되어 있지 않은 노드
• Internal Node(내부 노드, (= nonleaf, 비단말 노드(nonterminal)) : 단말 노드를 제외한 모든 노드(루트 노드 포함)
• parent(부모 노드)
• child(자식 노드)
• sibling(형제 노드)
• ancestors(조상 노드)
• descendants(후손 노드)
• degree(분지수, 차수) -> 방향에 따라 indegree, outdegree로 표현한다.
• depth(깊이), level(레벨)
• height(높이) : 트리의 최고 레벨
• subtree(부분 트리) 그 외 자잘한 요소는 생략한다.

Binary Tree(이진 트리)

분지수가 2 이하인 트리를 말한다.

아래는 참고 문헌입니다. 앞으로 올릴 모든 알고리즘 관련 포스팅은 다음 문헌들을 참고하여 포스팅 되었습니다. [참고]
JaeYeopHan님이 기술면접 대비 자료
윤성우의 열혈 자료구조 / 윤성우 저 / 오렌지미디어
C로 쓴 자료구조론 / HOROWITZ, Sahni 외 1명 저 / 이석호 역 / 교보문고
프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 / 구종만 저 / 인사이트
그 외 ALCUK 세미나 자료들..