[자료구조] 연속된 자료 구조와 연결된 자료구조 (1) with C++

<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>

---

시간 복잡도

　데이터를 처리하기에 앞서 데이터를 어떻게, 어떤 형식으로 저장할 건지에 대한 자료 구조를 선택하는 것은 중요한 일이다. 이러한 선택을 하는데 있어 적합한 지표로는 알고리즘 복잡도인  시간 복잡도(Time complexity)가 있다. 이때 시간 복잡도란 특정 작업를 수행하는 데 걸리는 시간을 데이터 크기에 대한 수식으로 표현하는 방식이다. 

 

　시간 복잡도는 데이터 크기가 변경되면 연산 시간이 어떻게 변하는지 시각적으로 파악할 수 있게 한다. 이때 표기식은 일반적으로 점근 표기법(asymptotic notation) 중 BIG-O 표기법(BIG-O notation)을 사용하는데, 이는 함수의 증감 추세를 비교하여 알고리즘의 효율성을 파악하는 표기법이다. 이 표기법의 큰 특징은 최악의 경우까지 고려한다는 것이다. 빅오 표기법의 형태는 다음과 같다. 이때 위에서 아래로 갈수록 복잡해진다(빅오 표기법을 제외하고 빅오메가, 빅세타 표기법이 존재하지만 따로 다루지는 않겠다).

빅오 표기법의 종류와 효율성

• 상수(Constant) 형태
• 로그(Logarithmic) 형태
• 선형(Linear) 형태
• 선형 로그 형태
• 다차원(Polynomial) 형태
• 지수(Exponential) 형태
• 팩토리얼(Factorial) 형태

　

　이러한 시간 복잡도는 그 내부에서 데이터를 어떻게 저장하여 사용하는가에 따라 달라진다. 같은 알고리즘을 채택하더라도, 어떤 자료 구조를 사용하느냐에 따라 O(n)이 될 수도, O(nlogn)이 될수도 있다는 의미다. 

 

요약

시간 복잡도
1. 정의: 특정 작업를 수행하는 데 걸리는 시간을 데이터 크기에 대한 수식으로 표현하는 방식
2. 특징
　- 빅오 표기법을 이용해 효율성을 비교

빅오 표기법 
1. 정의: 함수의 증감 추세를 비교하여 알고리즘의 효율성을 파악하는 표기법
2. 종류
　- 상수, 로그, 선형, 선형 로그, 다차원, 지수, 팩토리얼

---

연속된 자료 구조

　자료 구조를 크게 구분하면 선형 자료 구조, 비선형 자료 구조, 그리고 파일 구조로 나눌 수 있다. 이번 파트에서는 선형 자료 구조를 다룰 것이다. 선형 자료 구조를 크게 보면 연속된 자료 구조(Contiguous data structures)와 연결된(Linked) 자료 구조로 나눌 수 있다.

자료 구조의 구분

　

　우선 연속된 자료 구조부터 살펴보자. 연속된 자료 구조는 용어처럼 연속적으로 메모리에 할당하는 자료 구조이다. 우리가 일반적으로 알고 있는 배열을 떠올리면 이해하기 쉬울 것이다.

선형 자료 구조 구분

 

　이때 모든 원소를 하나의 연속된 메모리 덩어리(청크 - Chunk)에 저장하는데, 이를 그림으로 표현하면 다음과 같다. 그림을 보면 알 수 있듯이 모든 원소는 같은 크기의 메모리를 사용하고 있다.

크기가 n인 배열 array을 선언했을 때 데이터가 저장되는 방법

　

　예를 들어 다음과 같은 코드가 있다고 해보자.

int ary[4] = { 0,1,2,3 };

이를 앞선 그림처럼 표현해보면 다음과 같다.

만약 ary의 시작 주소가 00000031CD37FB38라면, ary[1]은 00000031CD37FB3C가 되겠고, ary[2]는 00000031CD37FB40가 된다. 

 

　그렇다면 배열의 또다른 특징은 무엇이 있을까? 먼저 시간 복잡도를 알아보자. 앞서 배운 빅오 표기법으로 배열의 시간 복잡도를 표현해보면 O(1)이다. 왜냐하면 모든 원소에 임의 접근이 곧바로 가능하기 때문이다. 즉, 데이터 접근 시간이 항상 일정하다는 것이다. 

 

　두 번 째는 캐시 지역성이다. 캐시 지역성(Cache locality)은 하나의 원소에 접근할 때 주위 원소도 캐시로서 가져오는 작업을 의미한다. 배열은 원소에 접근하는 속도가 매우 빠르므로 캐시 지역성이 좋다고 할 수 있다. 

 

　이러한 배열의 종류에는 메모리를 미리 예약하는 것을 시작으로 선언된 블록이 끝나면 소멸되는 정적(Static) 배열과 프로그래머가 유동적으로 배열의 크기를 조절하여 생성 시점과 해제 시점을 조절할 수 있는 동적(Dynamic) 배열로 나뉜다. 각각의 이유는 메모리 구조를 파악해야 하는데, 지금은 간단하게 정적 배열은 스택(Stack) 영역에 할당되고 동적 배열은 힙(Heap) 영역에 할당된다는 정도만 알고 넘어가자.

 

요약

연속된 자료 구조
1. 정의: 모든 원소를 단일 메모리 청크에 저장하여 연속적으로 메모리에 할당하는 자료 구조
2. 특징
　a. 모든 원소는 같은 크기의 메모리를 사용
　b. 데이터 접근 시간이 항상 일정
　c. 캐시 지역성이 좋음
3. 종류
　a. 정적 배열
　b. 동적 배열