자료구조의 큰 그림

최종 수정 : 2025.04.18

자료구조

데이터를 효율적으로 저장하고 관리하는 방법을 학습하는 과목이다. 어떠한 구조로 데이터를 다룰지에 대해 학습한다.

---

■ 자료구조와 알고리즘

자료구조와 더불어 알고리즘을 함께 학습하는 것이 좋다. 둘 사이에는 깊은 연관성이 있다. 어떤 자료구조가 사용되었느냐에 따라 사용 가능한 알고리즘이 달라질 수 있기 때문이다.

• 자료구조(data structure) : 데이터를 효율적으로 저장하고 관리하기 위한 방법
• 알고리즘(algorithm) : 어떠한 목적을 이루기 위해 필요한 일련의 연산 절차

---

■ 시간 복잡도와 공간 복잡도

자료구조와 알고리즘을 고려하며 작성한 코드는 훨씬 더 품질 좋은 코드가 될 가능성이 높다. 자료구조와 알고리즘의 고려 여부에 따른 성능의 차이는 '시간 복잡도'와 '공간 복잡도'를 통해 알 수 있다. 이 둘은 소스 코드나 프로그램이 얼마나 효율적인지를 판단하는 척도이다.

 

1. 시간 복잡도(time complexity)

입력의 크기에 따른 프로그램 실행 시간의 관계를 의미한다. 프로그램의 실행 시간과 입력의 크기는 서로 밀접한 관계가 있다. 대개, 실행 시간은 연산의 횟수에 비례한다.

 

따라서 시간 복잡도는 입력의 크기에 따른 프로그램 실행 시간이라고 할 수도 있고, 입력의 크기에 따른 연산 횟수라고 할 수도 있다.

정렬 알고리즘	시간 복잡도
삽입 정렬	O(n^3)
선택 정렬	O(n^2)
버블 정렬	O(n^2)
병합 정렬	O(n log n)
퀵 정렬	O(n log n)
힙 정렬	O(n log n)

 

2. 공간 복잡도(space complexity)

프로그램이 실행되었을 때 필요한 메모리 자원의 양을 의미하며, 입력에 따른 메모리 사용량의 척도라 할 수 있다.

 

모든 프로그램은 실행을 위해 메모리에 적재되어야 한다. 같은 동작을 하는 프로그램이라고 하더라도 실행 과정에 많은 메모리가 필요한 경우가 있고, 그렇지 않은 경우가 있다.

 

3. 빅 오 표기법(big O notation)

시간 복잡도와 공간 복잡도를 표현할 때에는 대중적으로 '빅 오 표기법'을 사용한다. 이는 점근적 상한을 표기하는 방법이다. 입력 크기 n에 대한 빅 오 표기법은 흔히 실행 시간의 O(상한(n)) 형태로 표현되며, 쉽게 말해 입력하는 n이 점점 증가해 무한대로 커진다고 하더라도 실행 시간이 대략 이 이상(상한)은 커지지 않을 것이라는 의미이다.

 

빅 오 표기에서는 점근적 상한을 표현할 때에는 최고차항의 차수만 고려한다는 점을 유의해야 한다. n이 점점 증가하여 무한대로 커진다면 계수와 낮은 차수의 항이 끼치는 영향은 무시할 수 있기 때문이다.

 

다양한 표기법

표기법	수식	설명
빅 오	두 함수 f(n), g(n)이 있을 때, n₁ ≤ n, f(n) ≤ C * g(n)이 성립하는 상수 C, n₁이 존재하면 f(n) = O(g(n))이다.	어떤 알고리즘의 실행 시간이 최악의 경우에 얼마나 오래 걸릴 수 있는지 나타낸다. 그래서 점근 상한선을 통해 나타난다.
빅 세타	두 함수 f(n), g(n)이 있을 때, n₁ ≤ n, f(n) ≥ C * g(n)이 성립하는 상수 C, n₁이 존재하면 f(n) = Ω(g(n))이다. 두 함수 f(n), g(n)이 있을 때, f(n) = O(g(n))이면 g(n) = Ω(f(n))이다.	어떤 알고리즘의 실행 시간이 평균적으로 정확히 어느 정도 걸리는지를 나타낸다. 즉, 상한선과 하한선이 같아서, 그 함수의 정확한 성장 속도를 표현할 수 있다.
빅 오메	두 함수 f(n), g(n)이 있을 때, n₁ ≤ n, C₁ * g(n) ≤ f(n) ≤ C₂ * g(n)이 성립하는 상수 C₁, C₂, n₁이 존재하면 f(n) = Θ(g(n))이다.	어떤 알고리즘의 최선의 경우에 얼마나 빠르게 실행될 수 있는지를 나타낸다. 그래서 점근 하한선을 통해 나타난다.

---

참고 도서

이것이 컴퓨터 과학이다