■ 자료구조(Data structure)
자료(data)를 효율적으로 저장하고, 효율적으로 접근하고, 관리하기 위한 구조(structure)이다.
프로그래밍에서 “데이터”는 언제나 핵심이다. 이 데이터를 어떻게 저장할지, 꺼낼지, 정렬할지, 검색할지가 프로그램의 성능을 좌우한다.
- 자료구조는 이러한 것을 잘할 수 있도록 도와주는 “틀”이다.
넓은 의미에서 int 변수처럼 단순한 데이터 저장도 자료구조에 포함되며, 구조체(struct), 배열(array) 그리고 파일이 데이터를 저장하는 방식까지 모두 자료구조의 한 형태로 볼 수 있다.
이름 | 특징 |
선형(Linear) 구조 | 각 요소가 일렬로 나열되며, 한 요소 다음에 오직 하나의 요소만 존재할 수 있는 구조. (예 : 리스트, 배열, 스택, 큐 등..) |
비선형(Non-Linear)구조 | 한 요소가 여러 요소와 연결될 수 있는 구조. (예 : 트리, 그래프) |
1. 자료구조와 알고리즘
자료구조와 알고리즘은 밀접한 관계를 가진다.
자료구조는 “데이터의 표현 및 저장방법”을 다룬다면, 알고리즘은 그 데이터를 대상으로 하는 “문제의 해결 방법”을 의미한다.
int[] arr = { 1, 2, 3, 4, 5 };
for(var i = 0; i < arr.Length; ++i)
{
sum += arr[i];
}
위는 “배열의 저장된 모든 값의 합”을 구하는 알고리즘이다.
- 이렇게 자료구조와 알고리즘은 밀접한 관계를 가지며, 자료구조가 결정되어야 그에 따른 효율적인 알고리즘을 설계할 수 있다.
■ 시간복잡도(Time Complexity)
시간복잡도는 알고리즘의 성능을 분석하기 위한 기준으로, 특정 작업을 수행하는 데 필요한 연산 횟수를 입력 크기(n)에 따라 표현한 것이다.
이는 알고리즘뿐 아니라, 자료구조에서의 삽입, 탐색, 삭제와 같은 연산의 효율성을 평가할 때도 사용된다.
지수식과 로그식의 수학적 특성을 이해해야 시간복잡도의 의미를 파악할 수 있다. 이들은 알고리즘의 성능을 설명할 때 주로 사용된다.
지수식($y = x^2$) | 로그식$(y = \log_2 x)$ |
입력 $x$에 대해 2를 $x$번 곱한다. | $x$가 되려면 2를 몇번 곱해야 하는가? |
입력값이 커질수록 급격히 증가 | 입력값이 커져도 서서히 증가 |
- 위처럼, 지수식과 로그식은 극단적으로 다른 성장 속도를 가진다.
1. 시간복잡도와 공간복잡도(Space Complexity)
"어떤 알고리즘이 어떠한 상황에서 더 빠르고 느리냐?"
"어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰고 또 많이 쓰냐?"
하나는 속도에 관한 것이고, 다른 하나는 메모리의 사용량에 관한 것이다.
- 수행시간의 분석결과를 “시간 복잡도”라 하고, 메모리 사용량에 대한 분석 결과를 “공간 복잡도”라 한다.
- 이미 검증이 끝난 알고리즘은 메모리 사용량보단 속도에 더 초점을 둔다.
그렇다고 해서 알고리즘의 수행 시간을 직접 측정하는 데에는 한계가 있다. 처리해야 할 데이터 양이 달라질 때 속도가 얼마나 빨라지거나 느려지는지를 확인하려면 수백, 수천번 실험해야 하는데, 이는 비현실적이다.
알고리즘의 수행 속도를 평가할 때는 :
- 연산의 횟수를 센다.
- 말 그대로 연산의 횟수를 통해서 알고리즘의 빠르기를 판한단다.
- 처리해야 할 데이터 수 $n$에 대한 연산 횟수의 함수 $T(n)$을 구성한다.
- 데이터의 수를 함수에 입력하면 연산의 횟수가 바로 계산되는 식을 구성한다.
즉 알고리즘 별 연산횟수를 함수$T(n)$의 형태로 구성하면, 위와 같은 그래프를 통해 데이터 수의 변화에 따른 연삿횟수의 변화도 한 번에 파악할 수 있다.
그렇다면 어떤 알고리즘을 선택해야 할까?
위 그래프를 보면 데이터가 적을 때는 B가 빠르지만, 많아지면 A가 압도적으로 빠른 성능을 보인다. 그렇다면 데이터가 적을 땐 B, 많을 땐 A 알고리즘을 쓰는 게 정답일까?
틀린 판단은 아니다. 하지만, “데이터가 적은 상황에서의 속도 차이가 과연 얼마나 큰 의미가 있을까?”를 생각해 볼 필요가 있다. 진짜 중요한 것은, 데이터 수가 증가할 때 연산 횟수가 얼마나 늘어나는지 이다.
그렇다면 “A가 더 좋으니 B는 없어도 되나?”인데, 사실 A처럼 로그 시간 복잡도를 가지는 알고리즘은 구현 난이도가 매우 높다.
즉, 절대적인 정답이 있는 것이 아니라, 상황에 맞는 판단이 중요하다. 그래서 자료구조의 특성과 알고리즘의 동작 원리를 정확히 이해하는 것이 핵심이다.
2. 순차 탐색(Linear Search) 알고리즘의 시간복잡도
static int LSearch(int[] arr, int target)
{
for(var i = 0; i < arr.Length; i++)
{
if (arr[i] == target)
{
return i;
}
}
return -1;
}
위 코드를 토대로 데이터 수 $n$에 대한 연산횟수의 함수 $T(n)$을 구해보자. 그렇다면, 위 코드에 존재하는 모든 연산자(==, <, ++)가 얼마나 많이 수행되는지를 분석하면 될까?
- 위와 같은 탐색 알고리즘에선 ==연산을 적게 수행하는 알고리즘이 좋은 탐색 알고리즘이다.
- ==의 횟수가 줄어들면 <연산과 ++연산도 자연적으로 줄어들기 때문.
즉, 핵심이 되는 연산을 찾고 그 연산을 토대로 연산횟수의 함수$T(n)$을 구하면 된다. 물론 객관적인 근거를 가지고 알고리즘 성능 분석하는 것 자체가 쉬운 일이 아니며, 흔히 하는 일도 아니기 때문에 부담은 갖지 않아도 된다.
최악의 경우(Worst Case) VS 평균적인 경우(Average case) VS 최선의 경우(Best case)
알고리즘의 시간복잡도를 평가할 때는 보통 촤악의 경우를 기준으로 삼는다. 평균의 경우는 입력 데이터의 분포나 조건을 명확히 가정해야 하므로 기준이 모호하고, 최선의 경우는 특정 상황에서만 빠른 결과를 내므로 일반적인 성능을 판단하기 어렵다.
- 최악의 경우는 이보다 더 느려지지 않는 확실한 기준이기 때문에 신뢰성이 높음.
구분 의미 예시(선형 탐색)
구분 | 의미 | 예시(선형 탐색) |
최악(Worst case) | 가장 오래 걸리는 경우 | 찾는 값이 없거나 마지막에 있음 |
평균(Average case) | 가장 빨리 끝나는 경우 | 찾는 값이 첫 번째에 있음 |
최선(Best case) | 모든 경우의 평균적인 수행 시간 | 배열 중간쯤에 있음 |
- 최악의 경우(Worst case)
위 상황에서 데이터 수가 $n$개일 때, 최악의 경우에 해당하는 연산 횟수는 $n$이다.
- 즉, $T(n) = n$이 되는 것이다.
■ 빅-오 표기법(Big-Oh Notation)
빅-오라는 것은 함수$T(n)$에서 가장 영향력이 큰 부분이 어딘가를 따지는 것인데, 이때 사용되는 표기법에 대문자 O를 사용하여 빅-오라 한다.
$$ T(n) = n^2 +2n +1 $$
[임의의 시간복잡도 함수]
위 식을 아래와 같이 간략화, 수학적으로 표현하면 근사치(approximation)식으로 구성해도 문제가 없을 것이다.
- $T(n) = n^2 + 2n$ ⇒ +1을 제거하여 간략화.
- $T(n) = n^2$ ⇒ $2n$을 제거하여 간략화.
+1을 식에서 제외한 것은 괜찮아 보이지만, $+2n$까지 제거한 것은 조금 과감해 보일 수 있다. 그렇다면 $T(n)$에서 $n^2$가 차지하는 비율을 확인해 보자.
$n$ | $n^2$ | $2n$ | $T(n)$ | $n^2$ |
10 | 100 | 20 | 120 | 83.33% |
100 | 10,000 | 200 | 10,200 | 98.04% |
1,000 | 1,000,000 | 2,000 | 1,002,000 | 99.80% |
10,000 | 10,000,000,000 | 20,000 | 100,020,000 | 99.98% |
- 위 표에서 확인할 수 있는 것처럼, $n^2$가 차지하는 비율을 절대적이다.
그래서 $T(n) = n^2 + 2n + 1$을 빅-오로 표기하게 되면 간단하게 $O(n^2)$이 되는 것이다.
1. 단순한 빅-오 계산법
$T(n)$이 다항식으로 표현된 경우, 최고차항의 차수가 빅-오가 된다.
- $T(n) = n^2 + 2n + 9$ ⇒ $O(n^2)$
- $T(n) = n^4 + n^3 + n^2$ ⇒ $O(n^4)$
물론 $n^2$인 경우와 $9999n^2$인 경우도 이 둘을 빅-오로 표기해 보면 둘 다 $O(n^2)$이다.
만약, $n$이 5라 한다면 $5^2 = 25$지만, $9999\cdot 5^2 = 249975$로 둘은 꽤 큰 차이를 보인다. 하지만 빅-오는 “데이터 수의 증가에 따른 연산 횟수의 증가 패턴”을 나타내는 표기법이다.
- 즉, 빅-오 입장에선 다음 둘은 동일하다.
- 데이터의 수가 2,3,4개로 늘어날 때 연산 횟수는 4,8,16으로 두 배씩 늘어났다.
- 데이터의 수가 2,3,4개로 늘어날 때 연산 횟수는 99, 198, 396으로 두 배씩 늘어났다.
그래서 위가 의미하는 바는 정확히 $O(\log n)$이 된다. 증가 횟수를 좌표평면상에 그려놓으면, 증가하는 추세가 둔화되기 때문이다.
2. 대표적인 빅-오
$O(1)$ | 상수형 빅-오. 데이터 수에 상관 없이 연산 횟수가 고정인 유형의 알고리즘. ⇒ 연산 횟수가 데이터 수의 관계 없이 3회인 경우도 $O(1)$로 표기. |
$O(\log n)$ | 로그형 빅-오. “데이터 수의 증가율”에 비해 “연산횟수의 증가율”이 훨씬 낮은 가장 바람직한 알고리즘. |
$O(n)$ | 선형 빅-오. 데이터의 수와 연산 횟수가 비례하는 알고리즘. |
$O(n\log n)$ | 선형 로그형 빅-오. 데이터의 수가 두 배로 늘 때, 연산 횟수는 두 배를 조금 넘게 증가하는 알고리즘. |
$O(n^2)$ | 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘. ⇒ 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우. |
'Unity,C# > 자료구조' 카테고리의 다른 글
[C#] 재귀호출(Recursive Call) / 팩토리얼, 피보나치, 하노이타워 (0) | 2025.10.03 |
---|---|
[C#, Unity] 우선순위 큐(PriorityQueue) (0) | 2025.04.08 |