[C언어로 쉽게 풀어쓴 자료구조] 1장 자료구조와 알고리즘 간단 정리

C언어로 쉽게 풀어쓴 자료구조 1장 정리입니다.
개정 3판을 기본으로 작성했습니다.
꼭 필요한 내용만 넣어 시험이나, 정리할 때 편히 볼 수 있게 적었습니다.

---

1.1 자료구조와 알고리즘

자료구조: 프로그램에서 자료를 정리하여 보관하는 여러 가지 구조

알고리즘: 컴퓨터로 문제를 풀기 위한 단계적인 절차

 

<알고리즘의 조건>

- 입력: 0개 이상의 입력이 존재하여야 함.
- 출력: 1개 이상의 출력이 존재하여야 함.
- 명백성: 각 명령어의 의미는 모호하지 않고 명확해야 함.
- 유한성: 한정된 수의 단계 후에는 반드시 종료되어야 함.
- 유효성: 각 명령어들은 종이와 연필, 또는 컴퓨터로 실행 가능한 연산이어야 함.

<알고리즘을 기술하는 방법>

(1) 한글이나 영어 같은 자연어
(2) 흐름도(flowchart)
(3) 의사 코드(psuedo-code)
(4) 프로그래밍 언어

-> (3), (4)번을 많이 씀.

 

1.2 추상자료형

자료형: 데이터 + 연산

추상 자료형(ADT: abstract data type): 추상적, 수학적으로 자료형을 정의한 것

-> 추상 자료형에서는 데이터나 연산이 무엇(what: 연산의 이름, 매개 변수, 반환형)인지는 정의되지만 데이터나 연산을 어떻게( how: 연산을 구현하는 구체적인 코드) 컴퓨터 상에서 구현할 지는 정의되지 않음.

 

1.3 알고리즘의 성능 분석

 

C언어에서 수행시간 측정방법

(1) clock() 함수: 호출 프로세스에 의해 사용된 CPU 시간 계산.
(2) time()함수: 초 단위로 측정된 시간을 반환.

알고리즘의 복잡도 분석 방법: 구현하지 않고도 모든 입력을 고려하여 알고리즘의 효율성을 평가할 수 있음.

시간 복잡도(time complexity): 알고리즘의 수행시간 분석.
-> 일반적으로 알고리즘 분석도 이야기할 때 사용.
: 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지 숫자로 표시.
: 연산의 수를 입력의 개수 n의 함수로 나타낸 것을 시간복잡도 함수라고 하고 T(n)이라고 표기.
-> 연산들의 수행 횟수는 보통 프로그램에 주어지는 입력의 개수에 따라 변함.

공간 복잡도(space complexity): 알고리즘이 사용하는 기억공간 분석

빅오표기법: 가장 큰 차수에 영향을 받는 표기법.
-> 시간복잡도를 간단히 표시 가능.

빅오 표기법에 의한 알고리즘 수행시간 비교: 
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)

O(1): 상수형 
O(log n): 로그형
O(n): 선형
O(n log n): 선형로그형
O(n^2): 2차형
O(2^n): 지수형
O(n!): 팩토리얼형

빅오메가 표기법: 가장 작은 차수에 영향을 받는 표기법
-> 잘 사용하지 않음

빅세타 표기법: 가장 큰 차수와 작은 차수에 영향을 받는 표기법
-> 잘 사용하지 않음

알고리즘의 효율성 3가지 경우

(1) 최악의 경우: 자료집합 중 알고리즘 수행시간이 가장 오래 걸리는 경우
-> 가장 많이 쓰임
(2) 최선의 경우: 자료집합 중 알고리즘 수행시간이 가장 적게 걸리는 경우
-> 의미 없는 경우가 많음
(3) 평균적인 경우: 알고리즘의 모든 입력을 고려하고 각 입력이 발생하는 확률 고려한 평균적인 수행시간
-> 구하기 어려움