[자료구조론] 1주차

자료구조(Data structure): 컴퓨터에서 데이터를 보관하는 구조

알고리즘(Algorithm): 주어진 문제를 풀기 위한 단계적인 절차(procedure)

 

프로그램 = 자료구조 + 알고리즘

문제 해결을 위해 적절한 자료구조를 선택하고, 이 자료구조를 사용하는 효율적인 알고리즘 작성이 필요하다.

 

알고리즘의 조건

입력과 출력: 입력은 없어도 되지만 출력은 반드시 존재해야 한다.

명백성(Definiteness): 모든 명령어는 모호해서는 안 된다.

유한성(Finiteness): 반드시 종료되어야 한다.

유효성(Effectiveness): 모든 명령어는 실행가능해야 한다.

 

 

 

추상 자료형(Abstract data type)

자료형

데이터의 종류

데이터의 집합과 연산의 집합: 연산(operation)에는 함수(function)도 포함될 수 있다

 

자료형은 다음의 세 가지로 나눌 수 있다.

기초 자료형(Primitive type)

파생 자료형: 배열, 포인터

사용자 정의 자료형: 구조체, 공용체, 열거형

 

추상화(Abstraction)

핵심적인 구조나 동작을 위주로 간략하게 기술한 명세(Specification)

: 중요한 정보는 강조하고 그 외의 디테일은 제거하기 위함

 

추상 자료형(ADT)

수학적으로만 정의된 자료형

데이터와 연산이 '무엇'인지만 정의하고 '어떻게' 구현되는지는 정의하지 않는다.

= 데이터와 연산 정의 시 구체적인 코드는 제시하지 않는다.

 

사용자는 ADT가 제공하는 연산만 사용할 수 있다.

사용자는 ADT 내부의 데이터나 코드에 접근할 수 없다.

사용자는 ADT가 어떻게 구현되었는지 몰라도 사용할 수 있다.

사용자는 ADT의 구현이 변경되더라도 인터페이스가 같다면 이전과 같이 사용할 수 있다.

 

Ex) $printf()$ 함수의 내부 구현이 바뀌었어도 사용하는 데에는 문제가 없다.

 

 

 

알고리즘의 성능 분석

성능 분석

실제 구현이 필요하다

실제 수행 시간을 측정하되 동일한 하드웨어 조건 하에 측정해야 한다.

 

<수행 시간 측정>

#include <time.h>
 
int main()
{
    long long start = time(NULL);
 
    ...
 
    long long stop = time(NULL);
 
    double duration = (double)difftime(stop, start);
}
 

 

 

복잡도 분석

실제 구현은 필요없다.

알고리즘이 수행하는 연산 횟수를 측정한다(보통 데이터의 크기: $n$의 함수)

 

시간 복잡도(Time complexity): 알고리즘 수행에 얼마나 걸리는가?

공간 복잡도(Space complexity): 알고리즘 수행에 메모리 공간이 얼마나 필요한가?