[Data Structure] CHAP 0. 자료구조 입문 & ADT

이번학기 자료구조론이 끝난 기념으로(?) 복습 겸 정리를 해보자..! 이번 챕터의 목표

 

✅자료구조가 무엇인지 이해하기

✅자료구조의 효율성을 판단하는 방법 알기
✅Abstract Data Type(ADT)에 대해 이해하기

그럼 스타-투!

---

1. 자료구조

교수님께서 자료구조를 "데이터를 논리적으로 정리할 수 있는 방법과 효과적으로 데이터에 접근할 수 있는 기술을 제공해주는 자료들의 집합" 이라고 설명하셨다. 자료구조가 필요한 이유는 방대한 양의 데이터를 효율적으로 처리하기 위함이다.

 

자료구조를 듣고 놀랐던 건, 1년 내내 썼던 int, char등 자료형도 자료구조의 일부라는 것이었다.

- Simple Data Type : 쪼갤 수 없는 것으로 전체가 하나를 나타내는 데에 다 사용되는 것 ex) integer, boolean, etc.

- Complex Data Type : 여러 개가 모여 구성된 container 성격을 갖는 자료구조 ex ) arrays, lists, dictionaries, etc.

---

2. 알고리즘 분석

한 문제에도 여러 알고리즘이 있는데, 어떤 알고리즘이 더 나은지 판단하는 기준에는 메모리 효율성, 러닝타임이 있다. 그러나 러닝타임을 비교하려면 프로그램을 직접 구현해야 한다는 점, 프로그램을 돌리는 하드웨어 차이, 돌릴 때마다 러닝타임에 조금씩 차이가 날 수 있다는 문제가 있다.

 

이를 해결하기 위해 input값에 의존하지 않는, 구현이 필요하지 않는 방법이 나왔는데, 이것이 worst case일 때 시간복잡도를 비교하는 Big-O Rotation이다. 자료구조론에서는 알고리즘을 수도코드(Pseudo-code)로 작성한 후 7Function을 이용해 수식으로 바꾼다. 그 후 Big-O로 worst case를 나타내어 성능을 비교한다.

 

Pseudo-Code

쉽게 말하면 사람의 언어와 컴퓨터 프로그래밍 언어의 중간 어딘가로 생각하면 된다. 코드의 알고리즘을 구상할 때 사용하고, Algorithm, Input, Output등의 단어를 이용해 구상한다. 또 프로그래밍언어로 코딩하듯이 for,if,while 등의 문법을 사용한다. 그런데 특이점은 '←'를 할당의 뜻으로 이용하고, '='를 같다는 뜻으로 이용한다는 점이었다.

 

7 Important Function

이거는 함수그래프의 종류를 의미한다. x축을 데이터의 양, y축을 러닝타임으로 설정하여 그래프를 그리고, g(n)이라는 함수로 정의한다.
그래프의 종류는 7가지로 상수함수, lg n, n, n lg n, n^2, n^3, 2^n 이 있다. 오른쪽으로 갈수록 그래프의 기울기가 기하급수적으로 커지며, 이는 데이터의 양이 많아지면 러닝타임이 급격히 길어짐을 의미한다. 왼쪽의 함수일수록 좋은 함수라고 볼 수 있다. 실질적으로 성능이 좋은 코드는 g(n) = n lg n 함수로 다루며 성능이 나쁜 코드도 g(n) = n^2로 커버 가능하다. 만약 내 코드가 n^3이나 2^n이 나온다면.. 그 코드는 버리라고 하셨다..😂

 

Big-O

이 개념을 설명하려면 러닝타임에 대해 먼저 설명해야한다. 러닝타임이 좋은 케이스, 평균치인 케이스, 최악인 케이스가 있다면 무엇을 중심으로 봐야할까? 정답은 최악인 케이스(Worst case)이다. 얘가 가장 중요하다.

big-o는 시간복잡도를 다룰 때 사용하는 표기법 중 하나로 n의 값이 충분히 커지면 그 이상의 어떤 n을 대입하여도 c*g(n)보다 결과값이 작은 상수 c가 존재한다는 뜻이다.

f(n)<=cg(n)이라는 것은 충분히 커진 n값을 넣으면 g의 y값이 항상 크다는 것이고, 이는 러닝타임이 항상 길다는 것이며 쉽게 말하면 worst case인 것이다! O(n)은 최고차항만 취하고 나머지를 버리면서 쉽게 구할 수 있다.

big-O는 worst case와 관련된 것이고 이 외에도 big-Omega (best case), big-Theta (average case)가 있다.

 

---

3. ADT ( Abstract Data Type )

ADT는 '어떤 과정으로 구현하는지'가 목적이 아니라 해당 자료구조의 특성을 잘 정의하기 위해 사용한다. 즉 순수하게 기능이 무엇인지만 쓰는 것이다. 그래서 operation에만 관심이 있을 뿐, 무엇으로 구현했는지 관심없다. 

 

ADT 정의에는 이 세가지가 꼭! 포함되어야한다.
▶특정 자료구조를 생성하는 함수
▶값을 변형해주는 함수
▶자료구조에 어떤 데이터가 있는지 찾고 출력해주는 함수

 

자바에서는 (객체지향) Class, Interface가 ADT 정의 수단이다.