[자료구조] 4-1. 자료구조의 큰 그림

자료구조와 알고리즘

💡자료구조 (Data Structure)

• 데이터를 효율적으로 저장하고 관리하기 위한 방법
• 예를 들면, 데이터를 쉽게 꺼내 쓰기 위해 정리된 책장처럼 체계적으로 보관하는 방법이다.

💡알고리즘 (Algorithm)

• 어떤 목적을 이루기 위한 효율적인 연산 방법
• 예를 들면, 김치찌개 만드는 요리 레시피이다. 물을 붓고, 고기를 볶고, 김치를 넣고, 끓인다의 순서 자체가 알고리즘이다.

---

시간 복잡도와 공간 복잡도

시간 복잡도와 공간 복잡도는 소스 코드나 프로그램이 얼마나 효율적인지 판단하는 척도이다.

 

💡시간 복잡도 (Time Complexity)

• 입력의 크기에 따른 프로그램 실행 시간의 관계를 의미한다.
• 입력의 크기에 따른 연산 횟수라고 할 수도 있다.
• 예를 들어, 주어진 입력 데이터 n이 있을 때 반복문을 살펴보면 아래와 같다.

🔎 Python 예제

for _ in range(n):
	1 + 1

🔎 Java 예제

for (int i = 0; i < n; i++) {
    int result = 1 + 1;
}

➡️ 주어진 입력값을 n회 반복

 

🔎 Python 예제

for _ in range(2 * n):
	1 + 1

🔎 Java 예제

for (int i = 0; i < 2 * n; i++) {
    int result = 1 + 1;
}

➡️ 주어진 입력값을 2n회 반복

 

🔎 Python 예제

for _ in range(n):
    for _ in range(n):
        1 + 1

🔎 Java 예제

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        int result = 1 + 1;
    }
}

➡️ 주어진 입력값을 n^2회 반복

 

🔎 Python 예제

for _ in range(n):              # 입력으로 주어진 값 n; n회 반복하며
    for _ in range(n):          # 각각의 반복을 n회씩 반복하며
        1 + 1                   # 한 번씩 연산
                                 # → n^2번

for _ in range(3 * n):          # 입력으로 주어진 값 n; 3n회 반복하며
    1 + 1                       # 한 번씩 연산
                                 # → 3n번

1 + 1                           # 한 번씩 연산
1 + 1                           # 한 번씩 연산
                                 # → 2번

🔎 Java 예제

// n^2번 반복 (중첩 루프)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        int result = 1 + 1;
    }
}

// 3n번 반복
for (int i = 0; i < 3 * n; i++) {
    int result = 1 + 1;
}

// 단순 연산 2번
int result1 = 1 + 1;
int result2 = 1 + 1;

➡️ 주어진 입력값을 n^2 + 3n + 2회 반복

NOTE : 예제를 통해 반복문이 시간 복잡도에 많은 영향을 끼친다는 것을 알 수 있다. 실제로 가장 많은 영향을 주는 문법은 반복문이다.

• 하지만, 예제처럼 입력의 크기가 결정된다고 해서 연산 횟수와 실행 시간이 무조건적으로 결정되지는 않는다. 입력하는 n이 같다고 하더라도 프로그램의 연산 횟수와 실행 시간이 달라질 수 있다. 따라서 제대로된 성능 판단의 척도로 빅 오 표기법 (Big O notation)을 사용한다.

 

💡빅 오 표기법 (Big O Notation)

대표적인 시간 복잡도 크기

• 함수의 점근적 상한을 표기하는 방법
• 입력에 따른 실행 시간의 점근적 상한을 의미하는 것이다.

점근적 상한이란? 입력하는 n이 무한대로 커짐에 따라 증가하는 실행 시간의 한계

• 표기법 → O(상한(n))
  • n이 무한대로 커지더라도 실행 시간이 대략 상한(n) 이상 커지지 않을 것이라는 의미
    • ex. O(n^2)은 입력값 n이 증가하더라도 실행 시간의 증가율이 n^2보다 작다는 것을 표현한다.
  • 이때, n이 무한대로 커지면 계수와 낮은 차수의 항이 끼치는 영향은 무시되므로, 최고차항의 차수만 고려된다.

 

 

💡시간 복잡도 별 비교

 

입력 n이 충분히 커질 때, 각 복잡도가 의미하는 실행 시간의 증가 속도는 다음과 같다.

시간 복잡도	설명
O(1)	상수 시간, 입력 수와 관계없이 항상 일정 시간
O(log n)	로그 시간, 이진 탐색 등
O(n)	선형 시간, 입력을 한 번씩 훑는 방식
O(n log n)	효율적인 정렬(병합, 퀵 등)
O(n²)	중첩 반복문, 비효율적인 정렬(버블 등)
O(n!)	순열 / 완전탐색(브루트포스), 매우 비효율적

• n이 충분히 클 때 가장 성능이 좋지 않은 시간 복잡도는 O(n!)이다.
• 가장 성능이 좋은 시간 복잡도는 O(1)이다. O(1)은 입력값이 10개, 1억개가 주어지든 상관없이 항상 알고리즘의 실행 시간이 일정하다(상수 시간이 소요된다)는 의미이다.

 

💡정렬 알고리즘별 시간 복잡도 비교

 

같은 정렬 알고리즘이라도 시간 복잡도가 다르며, 정렬 방식에 따라 성능 차이가 크다.

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

• 정렬 알고리즘 추가 학습 자료 깃허브 링크 : https://github.com/kangtegong/cs/tree/main/ds/sorting

 

💡Java 배열 크기 별 정렬 알고리즘

 

정렬 알고리즘마다 시간 복잡도와 성능 특성이 다르기 때문에 실제로 Java에서는 배열 크기 별로 다른 정렬법을 사용한다.

public static void sort(int[] arr) {
    int length = arr.length;

    if (length < 47) {
        insertionSort(arr);           // 작은 배열: 삽입 정렬
    } else if (length < 286) {
        quickSort(arr);               // 중간 배열: 퀵 정렬
    } else {
        dualPivotQuickSort(arr);      // 큰 배열: 이중 피벗 퀵 정렬
    }
}

 

➡️ 배열 크기에 따른 최적 정렬 알고리즘 선택 기준

배열 크기 구간	사용 알고리즘	설명
작은 배열 (< 47)	Insertion Sort	- 단순한 구현으로 오버헤드가 적음 - 작은 데이터에서 복잡한 알고리즘은 오히려 손해 - 이미 정렬된 부분이 많을 때 매우 효율적
중간 배열 (47~285)	Single-Pivot QuickSort	- 전통적인 퀵 정렬 방식 - 적당한 크기에서 좋은 성능 - 구현이 비교적 단순하고 안정적
큰 배열 (≥ 286)	Dual-Pivot QuickSort	- 피벗을 2개 사용해 3구간으로 분할 - 대형 배열에서 단일 피벗보다 약 10% 더 빠름 - 작은 배열에선 오히려 오버헤드로 느려질 수 있음

 

 

💡버블 정렬과 병합 정렬로 알아보는 시간 복잡도 측정 방법

 

• 버블 정렬

버블 정렬은 인접한 두 수를 비교해서 순서를 바꾸는 방식으로, 가장 큰 값을 뒤로 밀어내는 작업을 반복한다.

이미지 1) 출처 : https://sfida.tistory.com/30

 

📌 왜 시간복잡도가 O(n²)인가?

for (int i = 0; i < n - 1; i++) {       // 바깥 반복: 총 n-1번 패스
    for (int j = 0; j < n - i - 1; j++) { // 안쪽 반복: 인접 요소 비교
        if (arr[j] > arr[j+1]) {
            swap(arr[j], arr[j+1]);
        }
    }
}

➡️ 버블 정렬은 이중 반복문으로 구성되어 있기 때문에 O(n²)의 시간이 걸린다.

➡️ 공간 복잡도를 생각해보면, 배열 arr 안에서 숫자 위치만 바꿔가며 정렬하는 방법이기 때문에 추가적으로 필요한 공간이 없다. 따라서, 공간 복잡도에 영향을 주지 않으므로 O(1)이 된다.

 

• 병합 정렬

전체 데이터를 반씩 나눠서 정렬한 뒤, 다시 작은 단위부터 차례대로 합쳐가며 정렬을 완성하는 분할 정복(Divide and Conquer) 방식의 알고리즘이다.

이미지 2) 출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

📌 왜 시간복잡도가 O(n log n)인가?

 

 

💡이외 표기법

 

이외에 빅 세타 표기법과 빅 오메가 표기법이 있다.

• 빅 세타 표기법 : 평균적인 실행 시간
  • ex. θ(n^2)은 입력값 n이 증가하더라도 실행 시간의 증가율은 n^2과 같다는 의미
• 빅 오메가 표기법 : 입력에 대한 실행 시간의 점근적 하한
  • ex. Ω(n^2)은 입력값 n이 증가하더라도 실행 시간의 증가율은 n^2보다 크다는 것을 의미

NOTE : 시간 복잡도를 표현할 때는 빅 오 표기법이 가장 대중적으로 사용되고 있다.

 

 

💡시간 복잡도 요약

표기법	의미	예시
Big-O (O)	최악의 시간 (가장 널리 사용됨)	O(n²)
Big-Ω (Omega)	최선의 시간	Ω(n)
Big-Θ (Theta)	평균적인 실행 시간 (정확한 성장률)	Θ(n log n)

---

 

💡공간 복잡도 (Space Complexity)

• 프로그램이 실행되었을 때 필요한 메모리 자원의 양을 의미한다.
• 시간 복잡도가 입력에 따른 실행 시간의 척도라면, 공간 복잡도는 입력에 따른 메모리 사용량의 척도하고 할 수 있다.
• 공간 복잡도는 시간 복잡도처럼 빅 오 표기법으로 표현된다.
  • 공간 복잡도를 빅오 표기법으로 표현하면, 입력에 따라 필요한 메모리 자원의 양에 대한 점근적 상한으로 표현할 수 있다.
• 알고리즘 성능 판단에 사용되는 척도는 주로 공간 복잡도 보다는 시간 복잡도로 표현된다.

---

자료구조 지도 그리기

이렇게 다음 챕터에서 학습할 자료구조의 개념과 자료구조의 성능을 판단할 수 있는 시간 복잡도와 공간 복잡도에 대해 정리해보았다.

아래는 다음 챕터에서 학습할 7가지 핵심 자료구조이다.

---

자료구조 관련 코딩 테스트 문제

[스택] https://www. .net/problem/10828

[큐] https://www.acmicpc.net/problem/18258

[덱] https://www.acmicpc.net/problem/28279

---

출처

https://www.hanbit.co.kr/store/books/look.php?p_code=B3079890360

이것이 취업을 위한 컴퓨터 과학이다 with CS 기술 면접

---

이미지 출처

1. https://sfida.tistory.com/30

[Algorithm] JAVA 정렬 알고리즘 - 버블정렬(Bubble Sort)

 

2. https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog