[자료구조] ep1) 자료구조 기본 지식들

ㅇ다차원 배열

- 3차원 배열

e.g. 4분기별 3학생의 8과목에서의 점수

 

- 4차원 배열

e.g. 3년간 4분기별 3학생의 8과목에서의 점수

 

 

 

ㅇ빅오(Big O) 표기법: 연산의 횟수를 대략적(점근적)으로 표기

"최악의 case 실행시간을 고려한다"

 

[예시]

(1) 7n-2: O(n)

(2) 3n^3 + 20n^2 + 5: O(n^3)

(3) 3log(n) + log(log(n)): O(log(n))

(4-1) n까지의 반복문: O(n)

(4-2) n까지의 이중반복문: O(n^2)

(4-3) n까지의 삼중반복문: O(n^3)

(5) 조건문에서의 실행시간은 최악의 case로 합산한다

+ O(log*n)은 중첩 log(n)을 의미

 

 

t = O(n) 함수라 생각하자

 

함수 증가율의 상한을 표시!

※ 빅오메가, 빅세타 표기법과 공간복잡도는 생략

 

 

 

ㅇ의사코드 or 수도코드(pseudo-code): 컴퓨터가 아닌 인간에게 읽히기 위해 알고리즘을 간략하게 설명한 코드 - python 문법과 비슷하다

의사코드 문법(따로 문법이 정해져 있지는 않다)

 

(주의) c언어 for문 의사코드에서

for i ← 1 to n-1 는

for(i = 1; i < n; i++) (O)

for(i = 1; i < n-1; i++) (X)

 

 

 

 

ㅇADT(Abstract Data Type): 추상 데이터 타입

데이터 타입을 추상적(수학적)으로 정의한 것

즉, 특정 자료형과 그 자료형을 바탕으로 하는 기능들(함수들)의 집합을 ADT라 한다

 

간단한 예로 연결리스트와 스택을 들어보자

연결리스트: add, delete, get, print, 등과 같은 기능들(함수들)과 함께 작동하는 ADT 자료구조

스택: push, pop, peek, empty, 등과 같은 기능들(함수들)과 함께 작동하는 ADT 자료구조

 

 

 

 

 

 

 

 

참고 및 출처: 데이터 구조 원리와 응용(국형준), C언어로 쉽게 풀어 쓴 자료구조(천인국)