자료구조와 알고리즘의 관계를 이해하고, ADT와 시간복잡도 개념에 대해 알아보겠다.

앞으로 자료구조와 알고리즘을 파이썬으로 구현하고 공부할 예정이다. 파이썬은 기존의 객체 지향 언어인 자바, C++ 과는 개념에서의 차이가 꽤 있다. 자료구조에서 말하는 개념과 자료구조 구현을 위한 파이썬의 문법이 혼동되어서는 안된다.

따라서 마지막에는 정적 배열과 동적 배열 대해 정리해보았다.

---

자료구조와 알고리즘의 관계

자료구조란?

데이터를 다루는 방식으로, 데이터를 저장하고, 꺼내고, 찾고, 처리하는 구조를 자료구조라고 한다.

자료구조의 종류

1. 선형 자료구조 : 리스트, 스택, 큐, 덱
2. 비선형 자료구조 : 트리, 그래프

자료구조는 배열 혹은 연결된 구조로 구현이 가능하다.

Array list와 Linked List

---

알고리즘이란?

문제를 해결하기 위한 절차이다.

다음 그림을 통해 알고리즘과 자료구조의 관계를 쉽게 이해할 수 있다.

a 노드에서 f 노드까지 도달하려고 할 때, 가장 적은 노드를 거쳐 이동하는 프로그래밍을 작성하려고 한다.

좌측 상단 처럼 데이터가 그래프 형태로 저장되어 있을 때, 이것이 자료구조이며, 좌측 하단처럼 a에서 f로 이동하기 위한 절차를 담은 것이 알고리즘이다.

그래프 자료구조에서 최단 거리 이동 알고리즘을 활용한 코드를 작성할 수 있다. 이를 프로그래밍이라고 한다.

---

ADT와 시간복잡도

ADT

추상 자료형(Abstract Data Type)이란 정의가 되어 있지 않은 데이터를 말한다. 다른 말로 하면, interface만 있고 실제로 구현은 되지 않은 자료형을 의미한다.

예를 들면,

def print_Hello() 

def print_Hi(): 
	print("Hi")

여기서 print_Hello()가 추상 자료형이다. 이름만 만들어 두었으며 구현된 것이 없기 때문이다. 반면 print_Hi()는 구현 되어 있으므로 추상자료형이라 말할 수 없다.

모든 자료구조는 추상형 자료구조로 이루어져 있다. 특정 함수를 정의해서 사용자가 원하는 형식으로 만들 수 있다.

다만 충돌하는 상황을 막기 위해 각각의 자료구조마다 키워드가 정해져 있으므로 코드를 작성할 때 해당 키워드를 사용하면 된다.

---

시간복잡도

시간복잡도를 표기하는 다양한 방법들이 있다.
그중 빅오(Big-O) 표기법은 알고리즘이 수행되는 과정에서 최악의 상황에서의 실행 시간(또는 연산 횟수)이 어떻게 증가하는지를 나타내는 표기법이다.

빅오 표기법은 입력 크기가 커질수록 알고리즘의 성능이 얼마나 빨리 나빠질 수 있는지를 분석하는 데 주로 사용된다.

참고로, 시간복잡도 표기법에는 빅오($O$), 빅오메가($\Omega$), 빅세타($\Theta$) 등이 있으며, 각각 최악, 최선, 정확한 성능 분석에 활용된다.

주어진 배열에서 target을 찾는 함수 search()를 예시로 시간 복잡도를 확인해보겠다.

def search(myString, target):
	n = len(myStirng)
	for i in range(n):
		if myString(i) == target:
			return i
	return -1

search("apple","l")

문자열을 저장하고 있는 myStirng이 있고 그 길이값을 n이라고 할 때, myStirng의 문자 중에서 target과 일치하는 값을 찾기 위한 반복문이 돌아가고 있다.

만약 일치하는 값을 찾을 수 없거나 myStirng의 맨 마지막 요소가 target과 일치하는 값이라면 비교 연산 myString(i) == target은 총 n번 수행될 것이다.

그러므로 함수 search()의 시간복잡도는 n이며, $O(n)$이라고 표기할 수 있다.

표기 방법

시간 복잡도를 계산했을 때, $1000n + 38$ 혹은 $100n^2+897$ 처럼 나온다면 계수와 상수항을 버리고 다음과 같이 표기한다.

$1000n + 38$ -> $O(n)$
$100n^2+897$ -> $O(n^2)$

---

배열

변수를 크게 두 종류로 구분할 수 있는데, 데이터가 한 개만 들어가는 경우는 변수라고 부
르고, 한 개 이상이 들어간다면 배열이라고 한다.

배열은 배열의 길이와 메모리 할당을 기준으로 정적 배열과 동적 배열로 구분된다.

정적 배열(Static Array)

정적 배열은 길이값이 정해져 있으며 연속된 메모리 공간을 할당한다. 주로 절차적 언어에 존재한다.

자바나 C++처럼 기존의 객체지향 언어에서의 일반적인 배열은 정적 배열이다. 배열을 선언할 때 설정한 길이값을 초과할 수 없다. 자료구조에서 나오는 배열 또한 정적 배열을 기준으로 한다.

정적 배열의 단점 중 하나는 배열의 크기가 정해져 있다는 것이다.

동적 배열(Dynamic Array)

동적 배열은 배열의 길이가 정해져 있지 않아 유동적으로 배열의 크기를 조절할 수 있다. 또한 메모리 상에서는 더 큰 공간이 필요하면 다른 메모리 공간에 복사하여 이동하게 된다.

주로 객체지향언어에 존재하며, 파이썬의 list가 동적 배열에 해당한다.