자료구조란
저장공간(memory) + 연산(읽기, 쓰기, 삽입, 삭제, 탐색 등)으로 구성된 형태
자료구조에서 입력을 통해 유한한 횟수의 연산으로 정답을 출력하는 과정이 알고리즘!
자료구조의 예시
- 변수(variable) : a = 5(→쓰기 연산), print(5)(→읽기연산)
- 배열(array), 리스트(list) ...
알고리즘의 시간복잡도
→ 가상컴퓨터(RAM=CPU+Memory+기본연산) + 가상언어(Pseudo-language) + 가상코드(Pseudo-code) 를 가정
기본연산 : 배정/대입/복사, 산술, 비교, 논리, 비트연산 등 단위시간에 수행되는 연산들의 모음
가상언어 : 기본연산, 비교(if/if else...), 반복(for/while), 함수(정의/호출/return) 등이 가능한 가상의 언어
가상코드 : 알고리즘을 구현하는 가상의 코드
이때 시간복잡도 T(n) = 최악의 입력에 대한 알고리즘 수행시간
Big-O 표기법 O(n) = T(n)에서 n→∞일때, 증가율을 결정하는 n의 최고차항(n, n^2, log(n) 등)
배열과 리스트
▶︎ 배열과 리스트는 가장 기본적인 순차적 자료구조
1. C언어에서의 배열
int A[4] = {2,4,0,5}→ A에 할당된 메모리에 각각 값을 저장한다.
따라서, A[2]의 주소 = A[0]주소 + 2*4byte
→ 값을 추가하려면 malloc으로 메모리를 할당해주어야 함
2. Python에서의 리스트
A = [2,4,0,5]→ A의 각 인덱스에 각각 객체(2,4,0,5)의 주소를 지정한다.
→ 용량이 자동조절(dynamic array)될 수 있어 append,insert,pop,remove 등의 메서드가 제공됨
순차적 자료구조의 종류
1. 배열, 리스트
→ index를 통해 임의의 원소에 접근 가능
참고) append, pop의 시간복잡도 = O(1) // insert, remove의 시간복잡도 = O(n)
2. Stack, Queue, Dequeue
→ 제한된 접근(삽입, 삭제)만 허용
Stack → LIFO
Queue → FIFO
Dequeue → Stack + Queue
3. 연결 리스트(Linked list)
→ 연속되지 않은 공간에 저장된 자료구조
따라서, 자기 값 주소와 다음 값의 주소를 같이 저장하고 있으며, 접근하기 위해서는 처음부터 링크를 따라가야함
