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

 

 

 

* 본 포스팅은 윤성우의 열혈 자료구조론을 읽으며 공부한 내용을 정리한 글입니다.

저의 부족한 생각과 주관으로 틀린 내용이 있을 수 있으니, 자세한 내용이 궁금하시다면 해당 책을 읽어보시길 추천드립니다.

 

 

 

 

---

목차

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

1-1. 필요한 배경지식

1-2. 자료구조란?

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

2-1. 측정방법

   2-2. 빅오 표기법

3. 프로그래밍 문제 풀이

---

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

1-1. 필요한 배경지식

해당 책은 C언어로 짜여져 있으며, 아래의 수준을 충족시켜야 정상적으로 이해할 수 있다고 합니다.

1. 구조체를 정의하며, typedef선언을 할 줄 안다.
2. 메모리 동적 할당을 이해하고 있으며, malloc과 free에 대해 이해해야 한다.
3. 포인터 변수의 선언과 포인터 연산에 능숙하다. 헤더파일의 필요이유에 대해 이해하고 있다.
4. 해더파일을 정의할 줄 알며, 포함되야 할 내용에 대해 이해하고 있다.
5. #ifdef ~ #endif의 의미를 알고 있다.
6. 하나의 프로그램을 둘 이상의 소스파일과 헤더파일에 담을 수 있다.
7. 재귀함수의 동작방식을 이해하고 있으며, 간단한 예제를 분석할 수 있다.

뭐.. 책 내에서도 자세히 설명해주진 않고, 직접 공부해보는것을 추천합니다.

개념적으로 이해하는건 어렵지 않아서요! 추가2로 포스팅 해보도록 하겠습니다 ㅎㅎ

 

1-2. 자료구조란?

자료구조란 데이터를 표현하고 저장하는 방법 입니다.

그러므로, 변수 타입이나 구조체의 정의도 자료구조에 속한다고 할 수 있습니다.

자료구조를 분류하면 파일구조, 단순구조, 선형구조, 비선형 구조 등등으로 나뉩니다.

하지만 본 서적에서는 선형 구조와 비선형 구조만을 다룹니다.

그리고 코드레벨 보다는 모델 레벨에서 서술해 개념적 이해를 위주로 서술합니다.

자료구조와 알고리즘이 밀접한 관련을 맺는 이유는 자료구조가 결정되야 효율적인 알고리즘을 선택할 수 있기 때문입니다.

 

 

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

2-1. 측정방법

수행시간과 메모리 사용량으로 나눌 수 있는데, 둘다 만족시키면 좋겠지만 일단 실행속도에 초첨을 둡니다.

실행속도는 연산 횟수를 세어 측정합니다.

제일 관심이 있는 것은 데이터 수가 증가함에 따른 연산횟수의 증가 정도에 있다.

아래는 데이터 증가량에 따른 연산횟수의 증가를 표현한 시간복잡도 그래프입니다,

아래의 그래프를 보신다면, 자신있게 n^2함수보다 n함수가 좋은 알고리즘이라고 말할 수 있어야 합니다.

 

그럼 어떤 상황을 기준으로 잡고 시간복잡도를 계산해야 할까요?

 최선의 경우와 최악의 경우, 그리고 평균으로 크게 세가지로 나눌 수 있습니다.

만약, 탐색알고리즘으로 비유하자면 최선의 경우는 무조건 1입니다. 처음에 찾을 경우이죠. 별로 변별력이 없죠?

평균을 구하는 경우는 순차탐색으로 예를 들어보겠습니다.

탐색대상이 목표 집단에 존재할 확률을 50%라고 하자.
평균시간복잡도를 구한다면, 탐색 대상이 배열에 있을 경우와 없을 경우를 더해 (3/4)n이다.
왜냐하면, 존재하지 않을 경우(n)와 존재할 경우(2/n)은 각각 50%의 확률이므로,
2/n * 1/2 + n * 1/2 = (3/4)n이기 때문이다.

너무 복잡하고 난해하죠? 단순한 순차탐색인데도 불구하고 가정이 필요하고 데이터가 필요합니다.

그래서, 최악의 경우가 바로 우리의 관심대상입니다. 마지막 작업에서 우리가 원하는 결과가 나오는 경우이죠.

 

이진탐색의 최악의 경우를 구현해 보도록 하겠습니다.

우측은 이진탐색 시간복잡도를 구하는 수식이며, 우측은 이진탐색을 코드로 구현한 것입니다.

우선 수식부터 보겠습니다.

탐색대상 n에 대해 이진탐색은 다음의 순서를 지닙니다.

수식의 n은 데이터의 수이며, k는 중앙값을 찾는(2로 나눈) 횟수입니다.

1. 대상의 중앙값을 찾는 값과 비교합니다.
2. 찾는값이 아니라면 다시 탐색 범위를 지정합니다.

어떻게 이런 시간복잡도 함수가 나왔는지 설명드라겠습니다.

데이터 수가 8개라면 8개에서 4번쨰를, 4개에서 2번째를, 2개에서 1번째를 확인하고 0번째가 탐색대상이므로,

3번의 중앙값을 찾고 1번째를 확인했으니 3 + 1,

데이터 수가 16개면 16개에서 8번째를 확인하고, 나머지 과정은 위와 같으니 4 + 1,

32개면 32개에서 16번째를 확인해고, 나머지는 위와 같으니 5 + 1,

64개면 6+1, 128개면 7+1 입니다.

그래서  T(n) = k+1 이라는 식이 나온 것이죠.

횟수 k를 구하자면, n이 1이 되기까지 2로 나눈 횟수가 k이므로,

n*(1/2)^k = 1이므로, 이를 k에 관한 식으로 정리하면

n = 2^k가 됩니다.

그리고 양변에 로그를 취해 지수를 정리하면, log n=k가 되므로,

최악의 횟수 'k'는 log n. 즉,

T(n) = log  n이 됩니다.

 

우측의 구현에서 탐색후 없이 없을떄 mid값에 증감을 해주는 이유는, 증감하지 않으면 무한루프를 돌기 때문입니다.

mid 변수는 index를 가르키므로 '수'가 아닌 '번째'의 의미라서 그렇습니다.

 

2-2. 빅오 표기법

 빅오에서는 가장 영향력이 큰 부분을 따지므로, n의 최고차항만을 시간복잡도에서 차용해 표기합니다.

ex) T(n) n^2 + n + 1 -> O(n^2)

빅오 표기법에서 최고차항만 차용해서 사용하는 이유는,
처음에도 말씀드렷듯 우리의 관심사는 '데이터 증가량에 따른 연산횟수의 증가'입니다.

오른쪽 표를 보시면 아시겠지만, 데이터 개수가  100개만 넘어가도 n^2가 98%의 비율임을 알 수 있죠.

그러면 2^n, n^3, n^4 그 이상의 지수들 더욱 더 심하겠죠?

그렇기 떄문에 빅오 표기법은 n의 최고차항만을 차용합니다.

 

2-3. 빅오 표기법의 대략적인 종류

• O(1)
  입력값에 상관없이 일정한 실행시간을 갖습니다. 최고의 알고리즘일까요?
  여기서 1은 1ms, 1초의 뜻이 아니라 1단위시간입니다. 1시간이 될수도, 1년(!!)이 될 수도 있습니다.
  항상 일정한 시간이 걸리지만, 1개의 데이터를 처리하는데 1시간이 걸리면 문제가 되겠죠?
  신중하게 사용해야 합니다.
• O(log n)
  로그는 매우 큰 입력값에서도 크게 영향을 받지 않습니다.
  견고한 알고리즘으로 평가받으며, 이진 탐색의 경우가 이에 해당합니다.
  
• O(n)
  모든 입력값을 적어도 한 번 이상은 살피는 알고리즘 입니다.
  모든 입력값을 살피므로, 걸리는 시간은 입력값에 1:1 비례하는 선형 시간 알고리즘입니다.
  정렬되지 않은 리스트에서 최대 / 최솟값을 찾는 경우가 해당됩니다.
• O (n log n)
  아무리 좋은 알고리즘이라 할지라도 대부분 n log n 보다 빠를 수 없습니다.
  대부분 효율이 좋은 알고리즘(병합 정렬등)이 이에 해당 합니다. 
  입력값이 최선일 경우, 비교를 건너 뛰어 O(n)이 될 수도 있습니다.
• O(n^2)  
  지수함수로, 입력되는 데이터가 많아질수록 기하급수적으로 연산횟수가 증가합니다.
  여기서부턴 비효율적인 정렬 알고리즘이라 부를 수 있으며, 버블정렬이 이에 해당됩니다.
• O(2^n)
  여기서부터는 쓰면 안되는 알고리즘이라고 할 수 있습니다.  n^2와 비교도 안되게 더 큽니다.
  피보나치의 수를 재귀로 계산하는 알고리즘이 이에 해당 합니다(다음장에 나옵니다!)

2-4. 빅오표기법의 수학적 정의

수학적 정의라서 어려워 보일 수 있는데요, 별거 아닙니다.

T(n) = n^2 + 1 이라고 하고,

g(n)=n^2, c=5,  n0=3이라고 하겠습니다.

 

n^2+1 <= 5(n^2) 는 n이 3보다 같거나 클때 항상 성립하죠?

따라서 T(n) = O(n^2)이라고 나타낼 수 있습니다.