자료구조와 알고리즘

알고리즘과 자료구조

문제를 어떻게 해결할지에 대한 일련의 단계를 알고리즘이라고 한다. 어떤 문제에 어떤 알고리즘을 쓰냐에 따라 처리 시간이 달라진다.

 

이 문제를 해결하는 과정에서 수많은 데이터를 처리하는데, 데이터를 체계 없이 저장하면 한정된 메모리 공간을 비효율적으로 쓰게 된다. 자료구조는 데이터를 효율적으로 처리하기 위해 메모리에 어떻게 저장하고 어떻게 관리할지의 방법을 말한다.

 

개발할 때 우리는 얼마나 빨리 해결할 수 있을지와 얼마나 메모리 공간을 절약할 수 있을지에 초점을 둔다. 적합한 알고리즘과 자료구조를 선택하면 처리 효율성을 높일 수 있다.

 

자주 쓰이는 자료구조는 대부분 프로그래밍 언어에 따라 이미 구현된 라이브러리가 있기 때문에 모든 로직을 구현하지 않아도 된다. 자료구조와 알고리즘을 공부하는 목적은 자료구조들의 특징을 잘 알아두고 상황에 따라 적합한 것을 선택할 수 있는 사고력을 기르기 위함이다.

참고) 메모리란?

프로그램에서 사용되는 데이터는 RAM 이라는 메모리에 저장된다. RAM(Random Access Memory) 는 말 그대로 랜덤하게 엑세스할 수 있는 메모리다. 랜덤 액세스란 어디든 바로 액세스할 수 있다는 뜻이다. RAM의 모양은 보통 여러 칸으로 나누어져 있는 상자로 그려진다. 칸마다 주소가 있고 주소만 안다면 첫 번째 칸부터 하나하나 찾아갈 필요 없이 그 칸에 바로 액세스할 수 있다.

 

알고리즘 성능 측정법

컴퓨터는 매우 빠른 속도로 연산한다. 그래서 자료구조와 알고리즘의 성능을 말할 때 '몇초 걸린다' 라고 하지 않고, 얼마나 많은 단계를 거쳐야 하는지로 비교한다.

 

데이터가 n개 입력되었을 때 얼마나 많은 단계를 거쳐야 하는지를 시간복잡도(Time Complex)라고 한다. 이것을 표기하는 방법 중에는 대표적으로 Big-O 표기법이 있다. 

 

빅오(Big-O) 표기법

빅오 표기법은 시간 복잡도를 나타내는 대표적인 표기법 중 하나이다. 따질 수 있는 최선, 평균, 최악의 경우의 수 중에서 최악을 따지기 때문에 수행 시간의 상한을 나타낸다. 입력되는 데이터의 개수를 n이라고 하면 O(n) 로 표기한다.

 

빅오 표기법에서는 아래와 같은 사항을 주의한다.

 

1. 적은 양의 데이터를 고려하지 않는다.

상한을 따지기 때문에 10개, 100개 등 적은 량의 데이터에 따른 성능 차이는 미미하다.

 

2. 최고차항만 표기한다.

'최대 이런 비율로 증가할 것이다' 라는 의미이므로 일정하게 증가하는 상수항은 의미가 없어 표기하지 않는다.(n*n-1 이나 n*n 이나 의미는 같으니...)

 

아래는 자주 쓰이는 빅오 표기법을 정리한 표이다.

표기법	설명
O(1) - constance time	한 단계만 거침. 데이터가 증가해도 성능에 변화가 없음.
O(n)	데이터가 증가할 때마다 단계가 추가됨. n개면 n번의 단계를 거쳐야 하는 셈.
O(n*m)	n번의 단계가 m번 반복됨
O(n^2)	n번의 단계가 각 회차 때 n번 더 반복되는 것.
O(2^n) - exponential time	2진트리처럼 각 단계는 2가지의 하위 단계가 있고 하위 단계도 그 아래 2가지 하위 단계를 가짐.
O(m^n) - expoenetial time	위 처럼 각 단계의 하위 단계가 m 개라면 O(m^n) 으로 표현.
O(log n)	단계를 거칠 때마다 해야되는 작업이 반절로 줄어듦

 

---

자료구조

• 배열 (Array)
• 연결리스트 (Linked List)
• 스택 (stack)
• 큐 (Queue)
• 트리(Tree)
• 힙 (Binary Heap)
• 트라이(Trie)