1주차 - 자료구조 개요

수강일시 : 2020.09~ 2020.12

출처:  고려대학교 정연돈 교수님 자료구조 강의

 

알고리즘이란 특정 또는 일반적인 문제를 해결하기 위한 방법도(혹은 순서도)

input의 갯수는 상관없지만 output이 존재해야함.

결과는 명확하고 효과적이어야 한다.

 

알고리즘을 설명하는 방법으로는

1.자연어

2.pseudocode

3.flow chart

4.programming language

가 있다.

 

pseudo code는 자연어와 프로그래밍 언어의 중간 성격으로 작성하기 쉽고 컴퓨터 언어를 사용하는 사람이라면 그 언어가 무엇이든간에 쉽게 알아볼 수 있도록 작성해야 한다. pseudo code를 읽으면 컴퓨터 언어로 쉽게 작성할 수 있지만 이를 컴퓨터가 직접 해석할 수 있도록 작성할 필요는 없다.

ADT란 spec의 나열이다.

무엇을 할 수 있는지 적힌것을 ADT라고 한다. 하지만 그 구동방식을 포함하지는 않는다.

 

알고리즘의 효율성은

1.공간복잡도

2.시간복잡도

두가지로 나뉘는데

공간복잡도는 얼마나 많은 저장공간을 차지하는지에 관한것이고

시간복잡도는 얼마나 오래 걸리는지에 대한 것이다.

 

일반적으로는 시간복잡도가 더 중요하나 이는 상황에 따라 다르다.

시간복잡도는 자료의 수 n에 대한 함수 f(n)으로 작성하는데 비교시에는 보통 big-O notation을 이용하여 작성한다.

big-O notation은 f(n)의 최고차항만을 적은것으로 이때 계수는 1로한다.

즉 f(n)= 3n^3+2n+1 인 함수의 O(n)=n^3이 된다.