[자료구조] 자료구조와 알고리즘의 이해

[자료구조] 자료구조와 알고리즘의 이해

” 참고 : 윤성우의 열혈 자료구조 책을 보고 혼자 공부한 내용입니다.”

자료구조란 무엇인가?

---

• 프로그램이란 데이터를 표현하고, 그렇게 표현된 데이터를 처리하는 것이다.

  • 데이터의 표현 = 데이터의 저장을 포함하는 개념
  • 데이터의 저장을 담당 = 자료구조

• 자료구조의 기본적 분류

  

  • 선형 자료구조 : 자료를 표현 및 저장하는 방식이 선형 (linear)

    = 데이터를 선의 형태로 나란히 혹은 일렬로 저장하는 방식

  • 비선형 자료구조 : 데이터를 나란히 저장하지 않는 구조

자료구조와 알고리즘

---

• 자료구조 : 데이터의 표현 및 저장 방법
• 알고리즘 : 표현 및 저장된 데이터를 대상으로 하는 문제의 해결 방법
  • ex) 배열 선언
  • 자료구조 : int arr[10] = {1,2,3,4,5,6,7,8,9,10};
  • 알고리즘 : for (idx = 0; idx <10; idx++) sum += arr[idx];
• 자료구조에 따라서 알고리즘은 달라집니다.
• 알고리즘은 자료구조에 의존적입니다.

알고리즘의 성능 분석 방법

---

시간 복잡도 (Time Complexity) 와 공간 복잡도 (Space Complexity)

알고리즘을 평가하는 두 가지 요소

• 어떤 알고리즘이 어떠한 상황에서 더 빠르고 또 느린가? - 속도
  • 속도에 해당하는 알고리즘의 수행시간 분석 결과 : 시간 복잡도
• 어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰고 또 많이 쓰는가? - 메모리의 사용량
  • 메모리 사용량에 대한 분석 결과 : 공간 복잡도

시간 복잡도의 평가 방법

• 중심이 되는 특정 연산의 횟수를 셉니다.
• 그리고 처리해야할 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 구성합니다.
  • 식을 구성하면 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단할 수 있습니다.

순차 탐색 알고리즘

for (i = 0; i < len; i++) {
    if (ar[i] == target)
        return i; 	// 찾은 대상의 인덱스 값 반환
}

• 어떠한 연산을 적게 수행하는 탐색 알고리즘이 좋은 탐색 알고리즘이겠는가?
  • 값의 동등을 비교하는 == 연산을 적게 수행하는 탐색 알고리즘
  • 탐색 알고리즘의 핵심 : 동등 비교를 하는 비교 연산
  • 다른 연산들은 == 연산에 의존적이다.

순차 탐색 알고리즘의 시간 복잡도

최악의 경우 (Worst Case)

• 데이터의 수가 n 개 일때, 최악의 경우에 해당하는 연산횟수는 n이다.
• T(n) = n

평균적인 경우 (Average Case)

• 계산을 위해 두 가지 가정
  • 탐색 대상이 배열에 존재하지 않을 확률을 50%
  • 배열의 첫 요소부터 마지막 요소까지 탐색 대상이 존재할 확률은 동일하다.
• 배열에 탐색 대상이 존재하지 않는경우
  • 데이터의 수가 n 개 일 때, 총 n 번의 비교연산을 해야합니다.
• 배열에 탐색 대상이 존재하는 경우
  • n/2
• T(n) = n * 1/2 + n/2 * 1/2 = 3n/4

이진 탐색 (Binary Search) 알고리즘의 소개

• 이진 탐색 알고리즘을 적용하기 위해서는 다음 조건을 만족해야 합니다.
  • 배열에 저장된 데이터는 정렬되어 있어야 합니다.

이진 탐색 알고리즘의 첫 번째 시도

(가정 : 길이가 9인 배열에 정렬된 상태로 데이터가 저장되어 있다)

• 배열 인덱스의 시작과 끝은 각각 0과 8입니다.
• 0과 8을 합하여 그 결과를 2로 나눕니다.
• 2로 나눠서 얻은 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 찾고자 하는 값인지 확인합니다.
• 저장된 값이 찾고자 하는 값이 아니라면 두 번째 시도로 넘어갑니다.

이진 탐색 알고리즘의 두 번째 시도

• arr[4]에 저장된 값과 찾고자 하는 값의 대소비교를 합니다.
• 대소의 비교 결과 arr[4]에 저장된 값보다 찾고자 하는 값이 작은 경우 0~3으로 인덱스 기준을 제한합니다.
• 0과 3을 더하여 2로 나눕니다. 나머지는 버립니다.
• 2로 나눠서 얻은 결과인 1을 인덱스 값으로 하여 arr[1]에 저장된 값이 찾고자 하는 값인지 확인합니다.
• 저장된 값이 찾고자 하는 값이 아니라면 세 번째 시도로 넘어갑니다.

이진 탐색 알고리즘의 세 번째 시도

• arr[1]에 저장된 값과 찾고자 하는 값의 대소비교를 합니다.
• 대소의 비교 결과 arr[1]에 저장된 값보다 찾고자 하는 값이 큰 경우 2~3으로 인덱스 기준을 제한합니다.
• 2와 3을 더하여 2로 나눕니다. 나머지는 버립니다.
• 2로 나눠서 얻은 결과인 2를 인덱스 값으로 하여 arr[2]에 저장된 값이 찾고자 하는 값인지 확인합니다.
• 저장된 값이 찾고자 하는 값이 아니라면 다음 시도를 반복합니다.

-> 이진 탐색 알고리즘은 탐색의 대상을 반복해서 반 씩 떨구어 내는 알고리즘입니다.

이진 탐색 (Binary Search) 알고리즘의 구현

int first = 0; // 탐색의 시작 위치에 해당하는 값
int last = n-1; // 탐색 대상의 마지막 인덱스 값
int mid;

while (first <= last) {
    mid = (first+last)/2; // 탐색 대상의 중앙을 찾는다.
    
    if (target == ar[mid]) // 중앙에 저장된 값이 target이라면
        return mid;			// 탐색 종료
    else { // 중앙에 저장된 값이 target이 아니라면 탐색 대상을 반으로 줄인다.
        if (target < ar[mid])
            last = mid-1;
        else
            first = mid+1;
    }
    return -1;
}

• last = mid -1; first = mid + 1;
  • 값을 하나 빼거나 더해서 그 결과를 변수 last와 first에 저장하지 않으면
  • mid 에 저장된 인덱스 값의 배열 요소도 새로운 탐색의 범위에 포함됩니다.
  • -> mid에 저장된 인덱스 값의 배열 요소는 이미 위에서 검사가 끝났기 때문에 불필요한 작업입니다.

이진 탐색 알고리즘의 시간 복잡도

최악의 경우 (Worst Case)

• 연산 횟수를 대표하는 연산?
  • == 연산
• 데이터 수가 n개일 때, 최악의 경우에 발생하는 비교연산의 횟수는 어떻게 되는가?
  • n이 되기까지 2로 나눈 횟수 k회, 비교연산 k회 진행
  • 데이터가 1개 남았을 때, 이 때 마지막으로 비교연산 1회 진행
• 최악의 경우에 대한 시간 복잡도 함수
  • T(n) = k+1
  • n과 k에 대한 식 : n*(\(\frac{1}{2}\))^k = 1
    • n = 2^k -> k = log₂n
  • T(n) = log₂n

빅-오 표기법 (Big-Oh Notation)

• 빅-오 : 함수 T(n)에서 가장 영향력이 큰 부분이 어딘가를 따지는 것
• T(n) = n²+2n+1
  • = n²+2n
  • = n²
• T(n) 이 다항식으로 표현이 된 경우, 최고차항의 차수가 빅-오가 된다.
  • T(n) = a_mn^m+a_m-1n^m-1+…+a₁n¹+a₀ = O(n^m)
• 빅-오 : 데이터의 수의 증가에 따른 연산횟수의 증가 형태(패턴)을 나타내는 표기법

대표적인 빅-오

데이터 수의 증가에 따른 연산횟수의 증가 형태를 표현한 것 : 빅-오

• 상수형 빅-오 : O(1)
  • 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘
• 로그형 빅-오 : O(log_n)
  • 데이터 수의 증가율에 비해서 연산횟수의 증가율이 훨씬 낮은 경우
• 선형 빅-오 : O(n)
  • 데이터의 수와 연산횟수가 비례하는 알고리즘
• 선형로그형 빅-오 : O(nlog_n)
  • 데이터의 수가 두배로 늘 때, 연산횟수는 두 배를 조금 넘게 증가하는 알고리즘
• O(n²)
  • 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘
• O(n³)
  • 데이터 수의 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘
• 지수형 빅-오 : O(2ⁿ)
  • 사용하기에 매우 무리가 있는 비현실적인 알고리즘

빅-오 표기들의 성능의 대소

• O(1) < O(log_n) < O(n) < O(nlog_n) < O(n²) < O(n³) < O(2ⁿ)

---