열혈 자료구조 복습 1

참고문헌 - 윤성우 <윤성우의 열혈 자료구조>

♨ 개인적 해석이 들어간 글임으로, 인지하지 못한 오류가 있을 수 있습니다 ♨

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

 

1-1. 자료구조(Data Structure)에 대한 기본적인 이해

▣ 자료구조란 무엇인가

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

  -> 이때 데이터의 표현은 데이터의 저장을 포함하는 개념

이 데이터의 저장 = 자료구조 되시겠다. 즉, 넓은 범위에서 데이터를 저장하거나 표현하는 방법은 자료구조의 일종이다

  예) 정수를 저장하기 위해 int형 변수를 선언

      개인정보를 저장하기 위해 구조체를 정의

 

- 자료구조의 분류

  선형구조 : 리스트, 스택, 큐

  비선형구조 : 트리, 그래프

  파일구조 : 순차파일, 색인파일, 직접파일

  단순구조 : 정수, 실수, 문자, 문자열

 

파일도 데이터를 저장하는 도구이기 때문에 파일의 구조(파일이 데이터를 저장하는 방식)도 자료구조에 포함된다

 

책에서는 선형구조 · 비선형구조 위주로 공부할 예정

 

● 선형 자료구조 : 자료를 표현·저장하는 방식이 선형(Linear), 데이터를 선의 형태로 나란히 혹은 일렬로 저장하는 방식'

 예) 스택, 큐, 리스트

 

● 비선형 자료구조 : 나란하지 않는 방식으로 저장하는 구조

  예) 트리, 그래프

 

 

 

▣ 자료구조와 알고리즘

- 자료구조가 데이터의 표현 및 저장방법을 의미한다면,

  알고리즘은 표현 · 저장된 데이터를 대상으로 하는 문제의 해결방법

 

예)

자료구조와 알고리즘은 밀접한 관계를 갖는다

자료구조가 결정되면, 그 구조에 가장 효율적인 알고리즘을 결정할 수 있다

-> 자료구조에 따라 알고리즘은 달라진다(알고리즘은 자료구조에 의존적이다)

 

 

 

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

 

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

 - 자료구조와 알고리즘을 평가하는 두 가지 요소

 시간 복잡도 : 어떤 것이 어떠한 상황에서 더 빠르고 느린가 (수행시간 분석결과)

 공간 복잡도 : 어떤 것이 어떠한 상황에서 메모리를 적게 쓰고 많이 쓰는가 (메모리 사용량 분석결과)

 

일반적으로 알고리즘을 평가할 떄는 공간 복잡도 보다는 시간 복잡도에 중점을 둔다

-> 그렇다면 어떻게 속도를 평가할 수 있는가

  연산의 횟수를 센 후, 처리해야할 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 구성한다

  데이터 수가 동일할 때 각각의 알고리즘이 연산을 한 횟수를 비교하여 더 적은 것이 빠르다고 판단한다

 

예)

데이터의 수가 적다면 알고리즘 B가 더 빠르고, n을 넘어서는 기점에서 부터 알고리즘 A가 더 빠르다

 

But! 데이터 수가 적다면 속도차이는 미비하다(인간 기준) 그렇기 때문에 데이터 수가 많아짐에 따른 연산횟수의 증가가 중요하게 여겨진다 -> 알고리즘 A가 더 좋은 알고리즘이다

 

But!! 현실에서 A와 같은 효율을 갖는 알고리즘은 구현 난이도가 높은 편이기 때문에, 데이터 수가 많지 않고, 성능에 덜 민감한 경우라면, 편의성에 따라서 B를 선택하기도 한다

 

∴ 상황과 조건에 맞는 알고리즘을 선택하는 것도 능력이다 e말이야

 

 

▣ 순차 탐색(Linear Search) 알고리즘 시간 복잡도 분석의 핵심요소

 

순차 탐색 알고리즘이 들어간 함수 LSearch를 토대로 시간 복잡도를 분석하여

데이터의 수 n에 대한 연산 횟수의 함수 T(n)을 구해보면

 

1.  LSearch에 사용된 연산자들(< ,++, ==) 중 핵심적인 연산자는 == 비교 연산자이다

-> == 연산의 횟수가 적을 수록 다른 연산자들의 횟수도 적어진다

   (다른 연산자들은 ==연산에 의존적이다)

 

2. 최선의 경우(best case)는 비교연산의 횟수가 단 1번인 경우

   최악의 경우(worst case)는 n (최대치)가 될 것이다

-> 알고리즘을 평가하는데 최선의 경우는 고려되지 않는다

    = 최악의 경우는 알고리즘별로 많은 차이를 보인다

       (평균적인 상황-average case도 좋은 지표가 될 수 있으나 이를 위해 다양한 자료가 필요하다)

 

3-1. 최악의 경우의 T(n)

 LSearch에 인자로 입력된 배열의 데이터의 수가 n개일 때, 최악의 경우에 해당하는 연산횟수는 n이다

∴ T(n) = n

 

3-2. 평균적인 경우의 T(n)

평균적인 경우의 연산횟수를 계산하기 위한 2가지 가정

 ① 탐색 대상이 배열에 존재하지 않을 확률은 50%다

 ② 배열의 첫 요소부터 마지막 요소까지, 탐색 대상이 존재할 확률은 동일하다

 

우선 탐색 대상이 존재하지 않는 경우는 데이터의 총 갯수만큼 계산을 해야 알 수 있다

(다 검사해봐야 없는 것이 확실하게 알 수 있기 때문)

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

 

반면에 탐색 대상이 존재할 경우는 각 배열요소에 대상이 존재할 확률이 동일하기 때문에(②)

평균적인 비교 연산횟수는 n/2 이다

 

①을 고려하여 탐색 대상이 존재하지 않은 경우 + 존재할 경우의 연산횟수를 구하면

 

 ∴ 평균적인 경우의 T(n) = 1/2 * n (존재하지 않은 50%의 확률)  + 1/2 * n/2 (존재하는 나머지 50%의 확률)

                                = 3/4* n

 

그러나 위의 상황이 간단한 수준이 였다는 것을 생각해보면, 최악의 경우에 비해서 상대적으로

시간 복잡도를 구하기가 어렵다

그리고 평균을 구하기 위해 사용한 가정들의 신뢰성 문제도 있기 때문에

평균적인 경우 보다는 최악의 경우를 시간 복잡도의 기준으로 삼는다

 

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

이진 탐색은 순차 탐색보다 훨씬 좋은 성능을 보이지만, 배열에 저장된 데이터가 정렬되어 있어야 한다는 제약이 있다

(정렬의 기준 및 방식과 상관없이 정렬이 되어있어야 활용 가능)

 

- 이진 탐색 알고리즘의 원리의 예

아래와 같은, 길이가 9인 배열에 정렬된 상태로 데이터가 저장되어 있다고 한다면

이 배열을 int형 배열 arr 이라고 하자

이 배열을 대상으로 숫자 3이 저장되어 있는지 확인하기 위해 이진 탐색 알고리즘을 적용해보면

 

①. 배열 인덱스의 시작과 끝이 0과 8이므로, 0과 8을 더하여 2로 나눈 결과값(4)을 인덱스 값으로 하여

    arr[4]에 저장된 값이 목표값(3)인지 확인한다

 

 

②-1. arr[4]의 값(9)이 목표값(3)보다 크므로, 탐색의 범위를 인덱스 4보다 작은 수(0~3)로 제한한다

   -2. 0과 3을 더하여 그 결과를 2로 나누고 나머지는 버린다

   -3. 그 결과값(1)을 인덱스로 하는 배열요소(arr[1])가 목표값과 비교한다

 

 ☆ 여기서 주목할 점은 탐색의 대상을 반으로 줄였다는 사실이다

  -> 데이터가 정렬되어 있기에 가능한 일

 

③. 목표값을 찾을 때 까지 ①, ②번 반복

 

 

이진 탐색 알고리즘은 탐색의 대상을 반복해서 반씩 떨구어 내는 알고리즘

-> 그래서 순차 탐색 알고리즘에 비해 좋은 성능을 보인다

 

 

▣ 이진 탐색 알고리즘의 구현

이진탐색 알고리즘의 탐색 시작위치의 배열 인덱스를 first, 끝을 last라고 했을 때, 탐색 알고리즘이 진행됨에 따라서

first와 last는 가까워진다

 

계속해서 가까워지다가 둘이 일치하는 때 마지막 탐색이 이루어지고, 추가적인 탐색이 일어나지 않아야 한다

(first와 last가 동일해질떄 마지막 1개의 요소가 남은 상태이므로, 그 요소의 검색이 마지막 탐색이어야 한다)

+

first가 last보다 큰 경우 탐색은 종료되고 이렇게 종료되었음은 탐색에 실패했음을 의미한다

 

지금까지의 내용을 종합하여 이진 탐색 알고리즘을 구현해 본다면 아래와 같다

 

 

▣ 이진 탐색 알고리즘의 시간 복잡도 계산하기 : 최악의 경우를 기준으로

위의 코드에서 연산횟수를 대표하는 연산은 목표값과 탐색값을 비교하는 비교연산자이다

대표하는 연산을 찾았지만 최악의 경우에 대한 시간 복잡도를 바로 말하기는 어렵다

전체 데이터 수 n을 1/2로 몇번을 나누어야 남은 데이터가 1이 되는지 명확하지 않기 때문

 

                 n -> n/2 -> n/4 -> n/8 -> ... -> 2 -> 1

 

예) n = 8일 경우   8 -> 4 -> 2 -> 1

    n이 1이 되기까지 3회 + n이 1일때 마지막 1회

     ∴ 총 4회의 비교연산

 

일반화를 해보면

   n이 1이 되기까지 k회 + n이 1일때 마지막 1회

     ∴ 최악의 경우에 대한 시간 복잡도 T(n) 는 k + 1회의 비교연산

 

그러나 T(n)은 n에 대한 식을 의미하므로 k를 n에 대한 식으로 나타내야 한다

k는 데이터 수 n을 절반으로 나누어 1이되게 하는 횟수를 의미하므로

이를 정리하여 k를 n에 대하여 나타내면

그러나 T(n)을 구성하는 목적은 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단하는 것이다

 

최악의 경우 시간 복잡도에 따르면 데이터 수 n이 증가함에 따라서

비교연산의 횟수가 로그적(logarithmic)으로 증가한다

 

로그적으로 증가한다는 사실이 중요하기 때문에 +1은 무시해도 된다

책에서는 빅-오(대문자 O)표기법을 통해 위의 내용을 설명한다

 

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

데이터의 수 n과 그에 따른 시간 복잡도 함수 T(n)을 정확히, 오차 없이 구하는 것은 대부분의 경우 쉽지 않다

그럴때 빅-오만 따지면 되는데, 빅-오란 T(n)에서 가장 영향력이 큰 부분이 어딘가를 따지는 것이다

 

예)

시간 복잡도 함수를 구하는 이유가 연산횟수의 변화정도를 따지기 위함이므로

그래프의 모양이 어떻게 나오느냐가 중요하지 정확한 수치가 어떻게 되는지는 중요하지 않다

(간략화, 근사치 식을 구성해도 문제가 되지 않는다)

 

그러므로 +1 정도는 가뿐하게 지울 수 있다 또한 2n도 지울 수 있는데 그 이유를 아래 표를 보면 알 수 있다

글씨가 참 이쁘다

표에서 보이듯이 n^2이 차지하는 비율이 절대적이다 즉 n이 증가함에 따라서 2n+1이 미치는 영향은 미미해지므로

다음과 가티 간략화 할 수 있다

이것을 빅-오 표기법으로 표현하면 다음과 같으며

이를 "빅-오 오브 n제곱"으로 읽는다

 

정리하면 함수 T(n)의 빅오는 n제곱이며, 이는 n의 증가 및 감소에 따른 T(n)의 변화정도가

n제곱의 형태를 띰을 의미한다

 

▣ 단순하게 빅-오 구하기

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

예)

이를 일반화하면 아래와 같다

즉 다항식으로 표현된 시간 복잡도 함수 T(n)에서 실제로 큰 의미를 갖는 것은 최고차항의 차수(n의 m제곱)이다

이때 최고차항의 계수(am)가 신경쓰일 수 있는데 빅-오는 '데이터 수의 증가에 따른 연산횟수의 증가패턴'을 나타낸

표기법이기 때문에,

     2    →    4      →     8     이나

999 * 2 → 999 * 4 → 999 * 8 이나

 

둘다 '2배씩 증가하는 패턴임'에 중점을 두는 것이다

 

따라서 다음이 의미하는 바는

'데이터 수가 증가함에 따라 연산횟수의 증가하는 추세가 둔화되는 형태를 띈다'를 의미한다

 

▣ 대표적인 빅-오

상수형 빅-오, 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘을 의미한다

상수함수 생각하면 된다

특이점은 연산 횟수가 아무리 많아도 상수형 빅-오라면 O(1)로 표기한다는 것이다

 

로그형 빅-오, '데이터 수의 증가량'이 '연산횟수의 증가율'보다 훨씬 낮은 경우의 알고리즘을 의미한다

-> 매우 바람직한 형태라고 한다

 

선형 빅-오, 데이터의 수와 연산횟수가 비례하는 알고리즘을 의미한다

 

선형로그형 빅-오, 데이터의 수가 두 배로 늘때, 연산횟수는 두 배보다 조금 더 넘게 증가하는 알고리즘을 의미한다

 

데이터 수의 두 배에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다

그래서 데이터의 양이 많은 경우에 적용하기 부적절하다

(예- 이중 반복문, for안에 for가 있는 경우같이 반복문 안에 반복문)

 

지수형 빅-오, 실질적으로 사용하기 어려운 알고리즘이다

(데이터 양이 늘어나는 수보다 연산횟수의 증가량이 기하급수적으로 늘어나기 때문이다)

 

 

- 지금까지의 빅-오 표기들을 성능(연산횟수에 따른 수행시간)의 대소를 정리하자면 아래와 같다

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

앞서 나온 두 탐색 알고리즘의 빅-오를 판단, 둘의 성능 비교

이 둘의 성능을 비교하기 위해서 저자는 실험을 해보셨다

실험은

1. 최악의 경우를 대상으로 비교한다 (탐색의 실패를 유도)

2. 탐색이 실패할 때까지 몇번의 연산이 진행되는지를 센다

3. 데이터의 수는 500, 5000, 50000일 때를 기준으로 각각 진행한다

 

O(n)인 순차 탐색 알고리즘의 경우 실험을 하지 않아도 비교연산의 횟수가 500, 5000, 50000임을 알 수 있다

이진 탐색 알고리즘의 경우는 예제를 통해서 비교연산의 횟수를 확인

위 실행결과를 토대로 순차 탐색과 이진 탐색 알고리즘의 연산횟수를 아래와 같이 정리할 수 있다

n	순차 탐색 연산횟수	이진 탐색 연산횟수
500	500	9
5,000	5,000	13
50,000	50,000	16

이를 통해 O(n)의 알고리즘과 O(log n)의 알고리즘의 연산횟수의 차이를 확실하게 알 수 있다

 

▣ 빅-오에 대한 수학적 접근 : 이해가 되지 않으면 다음 기회에 공부하라

다음에 공부해야겠다