- 목적: 연산(삽입, 삭제, 탐색)의 시간·공간 복잡도를 최적화한다
- 구분: 선형(배열, 연결 리스트, 스택, 큐) vs 비선형(트리, 그래프)
- 선택 기준: 삽입이 많으면 연결 리스트, 탐색이 많으면 배열·트리를 선택한다
- 딥러닝 유저들간에도 자료구조를 이해하는 것에 대한 의견이 분분하지만
- 올바른 자료구조를 사용하는 것은 프로그램을 조직적으로 만들 수 있는 능력을 키울 수 있다.
- 데이터의 수가 많아질수록 효율적인 자료구조가 필요하다.
- 예시) 학생 수가 1,000,000명 이상인 학생 관리 프로그램
- 매일 자료 조회가 1억번 이상 발생한다면 더 빠르게 동작하는 자료 구조를 사용해야 프로그램의 효율성을 올릴 수 있다.
- 자료구조의 필요성에 대해서 이해할 필요가 있다.
- 성능 비교: 자료구조/알고리즘의 성능 측정 방법에 대해 이해할 필요가 있다.
- A: 적당한 속도의 삽입 & 적당한 속도의 추출 (삽입: \(O (log N)\) / 추출: \(O(log N)\))
- B: 느린 삽입 & 빠른 추출 (삽입: \(O (N)\) / 추출: \(O (1)\))
- A vs B? 상황에 따라 A를 만들지 B를 만들지 선택해야 한다. 삽입 연산이 많으면 A를, 추출 연산이 많으면 B를 택해야 한다. (속도 비교: \(O (N) < O (log N)< O (1)\))
- 하지만, 실무적으로 많은 개발자들이 A를 택한다. 왜냐면 log 복잡도는 상수 복잡도와 속도가 비슷하기 때문
- 데이터의 양이 많을수록 자료구조 선택이 프로그램 성능을 좌우한다.
- 동일한 문제라도 적합한 자료구조를 사용하면 시간 복잡도를 크게 낮출 수 있다.
- 배열, 연결 리스트, 스택, 큐, 트리, 그래프 각각의 특성을 이해해야 상황에 맞는 선택이 가능하다.
- 알고리즘 설계에서 자료구조는 시간 복잡도와 공간 복잡도에 직접 영향을 준다.
- 이처럼 상황에 맞게 알고리즘의 연산 속도를 결정해야 하므로 데이터를 효과적으로 저장하고, 처리하는 방법에 대해 바르게 이해할 필요가 있다.
- 자료구조를 제대로 이해해야 불필요하게 메모리와 계산을 낭비하지 않는다.
- C언어를 기준으로 정수(int) 형식의 데이터가 100만 개가량이 존재한다고 가정하자.
- 해당 프로그램을 이용하면, 내부적으로 하루에 데이터 조회가 1억 번 이상 발생한다.
- 이때 원하는 데이터를 가장 빠르게 찾도록 해주는 자료구조는 무엇일까?
- 트리(tree)와 같은 자료구조를 활용할 수 있다.
선형 자료 구조(linear data structure) 선형 자료구조는 하나의 데이터 뒤에 다른 데이터가 하나 존재하는 자료구조이며 데이터가 일렬로 연속적으로(순차적으로) 연결되어 있다.
- 배열(array)
- 연결 리스트(linked list)
- 스택(stack)
- 큐(queue)
비선형 자료 구조(non-linear data structure)
비선형 자료구조는 하나의 데이터 뒤에 다른 데이터가 여러 개 올 수 있는 자료구조이며 데이터가 일직선상으로 연결되어 있지 않아도 된다.- 트리(tree)
- 그래프(graph)
- 효율적인 자료구조 설계를 위해 알고리즘 지식이 필요하다.
- 효율적인 알고리즘을 작성하기 위해서 문제 상황에 맞는 적절한 자료구조가 사용되어야 한다.
- 프로그램을 작성할 때 자료구조와 알고리즘 모두 고려해야 한다.
- 시간 복잡도(time complexity): 알고리즘에 사용되는 연산 횟수를 측정 (시간 측정)
- 공간 복잡도(space complexity): 알고리즘에 사용되는 메모리의 양을 측정 (공간 측정)
- 공간을 많이 사용하는 대신 시간을 단축하는 방법이 흔히 사용된다.
- 프로그램의 성능 측정 방법: Big-O 표기법
- 복잡도를 표현할 때는 Big-O 표기법을 사용한다.
- 특정한 알고리즘이 얼마나 효율적인지 수치적으로 표현할 수 있다.
- 가장 빠르게 증가하는 항만을 고려하는 표기법이다.
- 복잡도를 표현할 때는 Big-O 표기법을 사용한다.
\(O(1)\): 데이터 수에 무관하게 항상 같은 시간 — 냉장고에서 우유 꺼내기
\(O(\log N)\): 데이터가 두 배 늘어도 연산이 1번만 더 필요 — 전화번호부 이진 탐색
\(O(N)\): 데이터에 비례 — 교실에서 특정 학생 이름 호명하며 찾기
\(O(N^2)\): 데이터의 제곱에 비례 — 모든 학생 쌍이 악수하는 경우
- 아래의 알고리즘은 \(O(n)\) 의 시간 복잡도를 가진다. 왜냐면, n에 따라
summary += i의 연산 횟수가 정해지기 때문이다.
- 아래의 알고리즘은 \(O(n)\) 의 시간 복잡도를 가진다. 왜냐면, n에 따라
- 다음 알고리즘은 \(O (n^2)\) 의 시간 복잡도를 가진다. 2 중 for loop은 i와 j가 n에 따라 각 각 n 번씩 연산되기때문에 \(n \times n\) 회 만큼 연산된다.
일반적으로 연산 횟수가 10억 (\(1.0 \times 10^9\))을 넘어가면 1초 이상의 시간이 소요된다.
[예시] n이 1,000일 때를 고려해 보자.
- \(O(n)\): 약 1,000번의 연산
- \(O(nlogn )\): 약 10,000번의 연산 (약 \(log10=10\))
- \(O(n^2)\): 약 1,000,000번의 연산
- \(O(n^3)\): 약 1,000,000,000번의 연산
그러므로, 알고리즘 짤 때 코딩 레벨로 연산 횟수를 계산해서 연산 시간을 어림잡아 추정할 수 있다.
시간 복잡도 속도 비교
Big-O 표기법으로 시간 복잡도를 표기할 때는 가장 영향력이 큰 항만을 표시한다.
- \(O(3n^2 + n) = O(n^2)\)
- 현실 세계에서는 동작 시간이 1초 이내인 알고리즘을 설계할 필요가 있다.
- 실무적으로 프로그램 동작 시간이 1초 이상이면 매우 느린 것으로 간주.
공간 복잡도를 나타낼 때는 MB 단위로 표기한다.
int a[1000]: 4KB int a[1000000]: 4MB int a[2000][2000]: 16MB
자료구조를 적절히 활용하기
- 자료구조의 종류로는 스택, 큐, 트리 등이 있다.
- 프로그램을 작성할 때는 자료구조를 적절히 활용하여 시간 복잡도를 최소화하여야 한다.
- 데이터베이스 인덱스: B-트리 자료구조로 수백만 레코드에서 \(O(\log N)\) 탐색을 구현한다.
- 딥러닝 연산: 행렬(배열)이 텐서 연산의 기본 단위로 GPU에서 병렬 처리된다.
- 운영체제 스케줄링: 우선순위 큐로 프로세스 실행 순서를 결정한다.
- 네트워크 라우팅: 그래프 자료구조로 최단 경로를 탐색한다.
- 추천 시스템: 그래프로 사용자-아이템 관계를 모델링한다.
1 Data Structure
자료구조란 다수의 데이터를 효율적으로 저장하고 처리하기 위해 데이터를 조직하는 방법이다.
딥러닝은 다양한 알고리즘의 조합으로 수행되기 때문에 다양한 알고리즘을 정확하게 작성하기 위해서는 다수의 다양한 자료(data)를 담기 위해 사용되는 자료 구조를 이해할 필요가 있다. 즉, 자료구조는 정확한 알고리즘을 구현하기 위해 다수의 자료(data)를 담기 위한 구조이다.
1.1 자료구조의 개요
2 왜 필요한가
3 자료 구조의 필요성
4 자료 구조의 종류
5 자료구조와 알고리즘
6 프로그램의 성능 측정 방법
Big-O 표기법은 “데이터가 10배 늘었을 때 연산 시간이 몇 배 늘어나는가”를 나타내는 척도다.
#| warning: false
#| code-fold: true
n = 10
summary = 0
for i in range(n):
summary += i
print(summary)
# 출력: 45#| warning: false
#| code-fold: true
n = 3
for i in range(1, n + 1):
for j in range(1, n + 1):
print(f"{i} X {j} = {i * j}")
# 출력:
# 1 X 1 = 1
# 1 X 2 = 2
# 1 X 3 = 3
# 2 X 1 = 2
# 2 X 2 = 4
# 2 X 3 = 6
# 3 X 1 = 3
# 3 X 2 = 6
# 3 X 3 = 9