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

아래 내용은 "윤성우의 열혈 자료구조" 책 내용을 기반으로 작성한 것입니다. 단순 복습 및 요약을 위한 것이니 공부 시 도서 구매를 추천합니다!

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

자료구조란? '데이터의 표현 및 저장방법'을 뜻한다.

알고리즘이란? 자료구조에서 표현 및 저장된 데이터를 대상으로 하는 '문제의 해결 방법'

⇒ 따라서 자료구조에 따라서 알고리즘은 달라지고, 알고리즘은 자료구조에 의존적이다.

알고리즘의 성능 분석 방법

• 지수식 로그식을 다 안다고 가정한다.

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

• 좋은 성능 및 동작을 보장받기 위해 자료구조와 알고리즘을 공부하는 것이다.

• 핵심

  - 어떤 알고리즘이 어떠한 상황에서 더 빠르고 더 느린가 ⇒ 속도 ⇒ 시간 복잡도 (Time Complexity)

  - 어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰고 또 많이 쓰는가. ⇒ 메모리의 사용량 ⇒ 공간 복잡도 (Space Complexity)

  But, 메모리의 사용량보다 실행 속도에 초점을 맞춘다. 즉, 시간 복잡도가 더 중요하다.

• 결론

  - 알고리즘은 정답이 없는 것이 아니라 상황에 맞게 답을 내려야 한다.

  - 단순 알고리즘 구현 능력에만 관심을 두는 것이 아니라 종합적으로 사고하고 판단하는 능력이 중요!!!

  ex) 스도쿠 게임!!

순차 탐색 알고리즘의 시간 복잡도 계산하기1 : 최악의 경우(worst case)

순차 탐색 알고리즘의 '데이터 수 n에 대한 연산 횟수의 함수 T(n)'은 아래 공식과 같다.

$T(n) = n$

순차 탐색 알고리즘의 시간 복잡도 계산하기2 : 평균적인 경우(average case)

가정 1. 탐색 대상이 배열에 존재하지 않을 확률을 50%

가정 2. 배열의 첫 요소부터 마지막 요소까지, 탐색 대상이 존재할 확률은 동일하다. ⇒ n/2

• 탐색 대상이 존재하지 않는 경우의 연산 횟수 n

• 탐색 대상이 존재하는 경우의 연산 횟수 n/2

길이가 7인 배열로 연산 해보면 알 수 있다.

배열순서 : [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ]

연산횟수 : 1 2 3 4 5 6 7

평균 연산 횟수는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 / 7 = 4번.

⇒ 각 요소별 평균적 비교연산의 횟수가 n/2임을 알 수 있지 않은가?

딱 n/2는 아니지만 배열이 길어질 수록 근사치 계산 결과에 더 가까워진다.

• 배열에 탐색 대상이 존재할 확률이 50%보다 낮을 수도 있고 높을 수도 있다.

  ⇒ 즉, 평균적인 경우는 최악의 경우보다 신뢰도가 낮다.

평균적인 연산 횟수는 아래와 같다.

$T(n) = \frac{3}{4}\times n$

이진 탐색(Binary Search)

• 정렬된 데이터가 아니면 적용이 불가능하다.(정렬의 기준 및 방식과는 관계없다)

이진 탐색 알고리즘의 시간 복잡도 계산하기: 최악의 경우(worst case) 기준

• 비교 연산 진행

  - 처음에 데이터의 수가 n개일 때의 탐색 과정에서 1회의 비교 연산 진행

  - 데이터의 수를 반으로 줄여서 그 수가 n/2개일 때 탐색 과정에서 1회 비교 연산 진행

  - 데이터의 수를 반으로 줄여서 그 수가 n/4개일 때 탐색 과정에서 1회 비교 연산 진행

  ...

  - 데이터의 수를 반으로 줄여서 그 수가 1개일 때의 탐색 과정에서 1회의 비교 연산 진행

• 수학적인 Think!

  - 8이 1이 되기까지 2로 나눈 회수 3회, 따라서 비교 연산 3회 진행

  - 데이터가 1개 남았을 때, 이때 마지막으로 비교 연산 1회 진행

  ⇒ 아래와 같이 만들 수 있다.

  → n이 1이 되기까지 2로 나눈 횟수 k회, 따라서 비교 연산 k회 진행

  → 데이터가 1개 남았을 때, 이때 마지막으로 비교 연산 1회 진행

  아래 공식과 같다.

  $T(n) = k + 1$

  k를 구해보자

  $n \times (\frac{1}{2})^k = 1$

  ⇒ 연산을 하다보면 아래와 같아진다

  $\log_{2}{n} = k$

  따라서 이진 탐색 알고리즘의 시간 복잡도(최악의 경우) 공식은 아래와 같다.

  $T(n) = \log_{2}{n}$

  But, +1은 어디로 갔는가???

  +1은 중요하지 않다. 중요한 것은 데이터의 수 n이 증가함에 따라서 비교 연산의 횟수가 로그적으로 증가한다는 사실이다.

  즉, n에 대한 식 T(n)을 구성하는 목적은 데이터 수의 증가에 따른 연산 횟수의 변화 정도를 판단하는 것이므로 +1은 중요하지 않다.

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

• 빅오란?

  함수 T(n)에서 가장 영향력이 큰 부분이 어딘가를 따진 것이다.

• 예시

  $T(n) = n^2 +2n + 1$

  n이 커지면 커질 수록 결과 값에 대한 n^2의 비율이 점점 증가한다.

  따라서 위의 공식은 아래 빅오로 표현 될 수 있다.

  $O(n^2)$

단순하게 빅-오 구하기

"T(n)이 다항식으로 표현이 된 경우, 최고 차항의 차수가 빅-오가 된다."

빅오는 '데이터 수의 증가에 따른 연산 횟수의 증가 형태(패턴)'을 나타내는 표기법이다.

대표적인 빅-오

• O(1)

  - 상수형 빅-오라 한다.

  → 반복문이 없는 경우를 말한다. 가장 빠른 알고리즘. 가장 난이도가 높은 알고리즘.

  - 연산 횟수가 데이터 수에 상관 없이 3회 진행되는 알고리즘 일지라도 O(3) 이라 하지 않고 O(1)이라 한다.

  - O(1)에는 연산 횟수가 고정인 유형의 알고리즘을 대표한다는 의미가 담겨 있다.

• O(log n)

  - 로그형 빅-오

  → 이진 탐색 알고리즘이 대표적이다. 가장 이상적인 알고리즘.

  - '데이터 수의 증가율'에 비해서 '연산 횟수의 증가율'이 훨씬 낮은 알고리즘을 의미한다.

• O(nlogn)

  - 선형로그형 빅-오

  - 데이터의 수가 두 배로 늘 때, 연산 횟수는 두 배를 조금 넘게 증가하는 알고리즘

  - 이에 해당하는 알고리즘이 많다.

빅-오 표기들의 성능(수행시간, 연산횟수)의 대소를 정리하면 다음과 같다.

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

순차 탐색 알고리즘과 이진 탐색 알고리즘의 비교

⇒ O(n)의 알고리즘을 O(logn)의 알고리즘으로 개선시키는 것은 약간의 개선이 아닌, 혁신적인 성능 개선이다.