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

이 글은 윤성우 저 - "윤성우의 열혈 자료구조"를 공부하고 정리하여 작성하였습니다.

 

1. 자료구조에 대한 기본적인 이해

• 자료구조: “데이터를 표현하고 저장하는 방법”
• 알고리즘: “자료구조를 대상으로 하는 문제의 해결 방법”
• 자료구조의 분류
  

  

 

 

2. 알고리즘의 성능분석 방법

2.1. 시간복잡도와 공간 복잡도

• 시간 복잡도(time complexity) : 속도에 해당하는 알고리즘 수행시간 분석결과
• 공간 복잡도(space complexity) : 메모리 사용량에 대한 분석결과
• 일반적으로 알고리즘을 평가할 땐 시간 복잡도에 초점을 맞춤

2.2. 순차 탐색 알고리즘과 시간 복잡도 분석

n개의 원소를 갖고 있는 배열 내에서 타겟 값을 찾는 경우

• 최선의 경우: 바로 찾을 경우 1
• 최악의 경우: 모든 원소를 다 탐색해야 할 경우 n
• 알고리즘의 평가는 “최악의 경우”를 주로 염두하여 평가함

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

• 전제 조건: 배열에 저장된 데이터는 정렬되어 있어야 함
• 이진 탐색 알고리즘 과정

const array = [1,2,3,7,9,12,21,23,27]
// 3이 어디있는지를 찾는 과정

// 1. 배열의 시작 인덱스와 끝을 지정함
const [start, end] = [0, 8]

// 4. start <= end 일 때까지 1~3을 반복하고 arr[middle] == 3이면 종료
while(start <= end){
    // 2. 해당 값을 합하여 그 결과를 2로 나눔
    let middle = Math.floor((start + end) / 2) // 4

    // 3. 얻은 결과 4를 인덱스로 하여 arr[4]에 저장된 값이 3인지 확인
    if (arr[middle] > 3) {
        end = middle - 1 // 3
    } else if(arr[middle] < 3) {
        start = middle + 1
    } else if(arr[middle] == 3) {
        console.log(middle)
        break
    }
}

• 이진 탐색 알고리즘은 탐색의 대상을 반복해서 반씩 떨궈내는 알고리즘이기 때문에 성능이 순차 탐색 알고리즘보다 훨씬 좋음
• 이진 탐색 알고리즘 시간 복잡도(최악) : $T(n) = log_2n$

2.4. 대표적인 빅-오(Big-O)

• 빅-오(Big-O): 시간복잡도 함수 T(n)에서 가장 영향력이 큰 부분만을 표시하는 기법

(크기순)	설명
O(1)	상수형 빅-오, 데이터 수와 상관없이 연산횟수가 고정인 유형의 알고리즘
O($logn$)	로그형 빅-오, 데이터 수 증가율에 비해 연산횟수 증가율이 훨씬 낮은 알고리즘 가장 바람직한 유형
O($n$)	선형 빅-오, 데이터 수와 연산횟수가 비례함.
O($nlogn$)	선형로그형 빅-오
O($n^2$)	데이터의 제곱에 해당하는 연산횟수, 주로 중첩 반복문
O($n^3$)	데이터의 세제곱에 해당하는 연산횟수, 삼중 중첩 반복문
O($2^n$)	지수형 빅-오

 

자료

• 윤성우의 열혈 자료구조 (윤성우 저, 2023.10)