[내일배움캠프] - DAY14 자료구조와 알고리즘-2

빅오 표기법(Big-O Notation)

빅오 표기법(Big-O Notation)은 알고리즘 성능을 수학적으로 표현하는 기법으로, 입력 데이터의 크기(n)이 증가할수록 실행 시간이 얼마나 증가하는지를 나타냅니다. 이는 실제 실행 시간을 측정하는 것이 아니라, 알고리즘의 효율성을 비교하기 위한 상대적인 기준으로 사용됩니다. 이와 같이 빅오 표기법을 통해 알고리즘의 성능을 분석할 때, 주로 시간 복잡도와 공간 복잡도 두 가지 측면에서 평가합니다.

 

 

시간 복잡도(Time Complexity)

시간 복잡도는 프로세스가 수행해야하는 연산을 수치화한것이라고 정의할 수 있습니다. 컴퓨터 성능에 따라 실행시간은 달라질 수 있지만 실제 실행 시간보다는 명령문의 실행 빈도수를 계산하여 실행시간을 구하게 됩니다.

 

공간 복잡도(Space Complexity)

공간 복잡도는 알고리즘이 실행되는 동안 필요로 하는 메모리 사용량이라고 정의할 수 있습니다. 이는 입력 데이터를 저장하기 위한 공간뿐만 아니라, 연산 과정에서 사용되는 변수, 배열, 객체 등 추가적으로 사용되는 메모리 공간을 모두 포함합니다.

 

---

시간 복잡도 종류

 

O(1) - 상수 시간

입력 크기와 상관없이 항상 같은 시간이 걸림

int x = arr[0];

• 배열의 특정 인덱스 접근
• 변수 대입

 

O(n) - 선형 시간

입력 크기 n에 비례하여 시간 증가

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

• 배열 전체 순회
• 리스트 탐색

 

O( n² ) - 이차 시간

중첩 반복문으로 인해 입력이 커질수록 급격히 느려짐

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println(i + j);
    }
}

• 버블 정렬
• 선택 정렬

 

O(log n) - 로그 시간

입력 데이터가 커져도 증가 속도가 매우 완만함

// 이진 탐색

• 이진 탐색
• 트리 탐색

 

O(n log n) - 선형 로그 시간

효율적인 정렬 알고리즘에서 자주 사용됨

• 퀵 정렬
• 병합 정렬
• 힙 정렬

 

시간 복잡도 비교 (성능 기준)

 

 

왼쪽에서 부터 오른쪽 순서이며, 오른쪽으로 갈수록 비효율적입니다.

---

완전탐색

모든 경우의 수를 전부 확인해서 정답을 찾는 방식입니다. 구현은 단순하지만 시간 복잡도가 크다는 단점이 있습니다.

따라서 데이터 개수가 적을 때나 정확한 최적해가 필요할 때 사용합니다.

 

선형탐색

앞에서부터 끝까지 하나씩 비교하며 탐색하는 기법입니다.  데이터 개수가 적을 때나 데이터가 정렬되어 있지 않을 때, 빠른 구현이 필요할 때 사용합니다. (ex: 배열에서 특정 값 찾기)

 

백트래킹

가능한 모든 경우를 탐색하되, 현재 선택이 조건을 만족하지 않으면 더 이상 탐색하지 않고 이전 단계로 되돌아가는 기법입니다. 중간 단계에서 불필요한 경우를 미리 제거하는 "가지치기"를 통해 탐색 횟수를 줄일 수 있으며, 조합/순열 탐색과 같이 경우의 수가 많은 문제를 효율적으로 해결할 수 있습니다. 다만 최악의 경우에는 여전히 많은 연산이 필요하다는 한계가 있습니다. (ex: 스도쿠, N-Queen 문제)

 

조합/순열 탐색

가능한 모든 조합 / 순열을 생성해서 조건을 검사하는 기법입니다. 경우의 수가 명확히 작을 때, N ≤ 8 ~ 10 정도일 때 사용합니다. (ex: 숫자 카드로 만들 수 있는 모든 경우)

---

분할 정복

 

병합정렬

배열을 반으로 나눠 정렬 후 병합하는 기법입니다. 특징으로는 항상 O(N log N)을 보장합니다. 안정 정렬이 필요하거나 최악의 경우 성능이 중요할 때 사용합니다. (ex: 대용량 데이터 정렬)

 

퀵 정렬

기준값(Pivot)을 기준으로 분할하는 기법입니다. 평균적으로 매우 빠르며, 추가 메모리를 최소화해야하거나 평균 성능이 중요한 경우 사용합니다.

 

이분 탐색

정렬된 데이터에서 중간값을 기준으로 탐색 범위를 반으로 줄이는 기법입니다. 데이터가 정렬되어 있을 때나 최적의 값과 조건을 만족하는 최소/최대 문제에서 사용합니다. (ex: 특정 수 찾기, 파라메트릭 서치)

---

탐욕 알고리즘(Greedy)

매 순간 가장 좋아 보이는 선택을 하면서 문제를 해결하는 기법입니다. 현재 단계에서 가장 이득이 큰 선택을 하며, 한 번 선택한 결과를 되돌릴 수 없기 때문에 구현은 단순하지만 항상 최적해를 보장하지 않는다는 단점이 있습니다.

 

크루스칼 알고리즘

그래프의 모든 정점을 최소 비용으로 연결하기 위해 가중치가 가장 작은 간선부터 선택하는 최소 신장 트리(MST) 알고리즘입니다. 간선을 선택할 때 사이클이 발생하지 않도록 주의하며, 매 순간 가장 비용이 적은 간선을 선택하는 그리디 방식으로 동작합니다. 구현이 비교적 간단하고 희소 그래프에서 효율적이지만, 간선 정렬과 사이클 판별을 위한 Union-Find 자료구조가 필요합니다. (ex: 최소 비용 네트워크 구성, 도시 간 도로 연결, 통신망 설계)

 

프림 알고리즘

하나의 정점에서 시작하여 현재 연결된 정점들 중 가장 비용이 적은 간선을 선택해 점진적으로 그래프를 확장하는 최소 신장 트리(MST) 알고리즘입니다. 매 단계에서 트리에 가장 유리한 선택을 하는 그리디 방식으로 동작하며, 우선순위 큐를 활용해 효율적으로 구현할 수 있습니다. 정점 수가 많고 간선이 많은 밀집 그래프에서 효율적이지만, 시작 정점에 따라 구현 방식이 달라질 수 있습니다. (ex: 모든 지점을 최소 비용으로 연결하는 문제)

 

다익스트라 알고리즘

하나의 시작 정점에서 다른 모든 정점까지의 최단 거리를 구하는 최단 경로 알고리즘입니다. 현재까지의 거리가 가장 짧은 정점을 선택해 거리를 갱신하는 그리디 전략을 사용하며, 우선순위 큐를 통해 빠르게 탐색할 수 있습니다. 모든 간선의 가중치가 양수일 때만 정확한 결과를 보장하며, 음수 가중치가 포함된 그래프에서는 사용할 수 없다는 제약이 있습니다. (ex: 네비게이션, 네트워크 지연 시간 계산)

---

[ 오늘 배운 학습 ]

1. 알고리즘 심화

2. 시간/공간 복잡도

 

[ 다음 학습 계획 ]