Chap1. 자료구조와 알고리즘 이해

1. 자료와 자료구조

  • 자료(data)는 현실 세계로부터 단순한 관찰이나 측정을 통해서 수집한 사실(fact)들 또는 값이다.
  • 자료는 가공되지 않은 상태를 의미하고, 정보(information)는 어떤 기준에 의해 정리되고 기록된 것을 의미한다.
  • 자료 구조(Data Structure)는 자료 개체(Data Object)의 집합, 자료 값 사이의 관계 그리고 자료에 적용 가능한 함수 또는 연산 등을 의미한다.
  • 프로그램이란 데이터를 표현하고, 그렇게 표현된 데이터를 처리하는 것이다.
  • 데이터의 표현은 데이터의 저장을 포함하고, 데이터의 저장을 담당하는 것이 자료구조이다.

2. 자료의 구성

  • 비트, 바이트, 단어, 항목, 레코드, 파일, 데이터베이스

3. 자료구조의 분류

  • 단순 구조 : 정수, 실수, 문자, 문자열
  • 파일 구조 : 순차 파일, 색인 파일, 직접 파일
  • 선형 구조 : 리스트, 스택, 큐
  • 비선형 구조 : 트리, 그래프

4. 자료구조와 알고리즘

  • 자료구조가 '데이터의 표현 및 저장방법'을 뜻한다면, 알고리즘은 이를 대상으로 하는 '문제의 해결 방법'을 의미한다.
  • 자료구조에 따라 효율적인 알고리즘이 바뀌므로 자료구조에 따라 효율적인 알고리즘을 선택할 수 있어야 한다.
  • 알고리즘은 '자연언어(일상언어)', 순서도, 특정 프로그램 언어, 의사코드를 이용하여 표현할 수 있다.
  • 순서도를 사용하여 표현할 경우 단순한 알고리즘은 이해하기 쉬워지나, 특별한 구조나 세밀한 부분, 규모가 큰 알고리즘은 표현하기 어렵다는 단점도 있다.
  • 순서도에는 N-S차트, HIPO, RERT, 자료흐름도(PFD) 등의 기법이 있다.

5. 알고리즘 성능분석 방법

  • 알고리즘 분석을 위한 판단 기준

    • 정확성 (Correctness)
    • 간결성 (Simplicity)
    • 작업량 (Amount of work done) : 시간 복잡도 (time complexity)
    • 기억장소 사용량 (amount of space used) : 공간 복잡도 (space complexity)
    • 최적성 (Optimality)

  • 현대에는 하드웨어 성능이 향상되어 대부분의 경우 작업량을 중요하게 생각한다.

  • 시간 복잡도는 기본적으로 최악의 경우의 명령문의 수행 빈도수를 데이터 수 n과 그에 따른 함수 T(n)을 만들어서 확인한다.

  • T(n) : 빅-오 표기법 → 가장 큰 차수항 만을 가지고 함수 G(n)을 만들어 시간 복잡도 비교

6. 계산 차수에 따른 성능 순서

df

7. 빅오 표기법의 한계

  • 복잡한 알고리즘의 분석이 매우 어렵다
  • 평균 계산 차수를 구하기 어렵다
  • 세밀한 측정이 곤란하여, 작은 차이를 반영하지 못한다.
  • 자료가 적은 경우는 알고리즘의 성능을 반영하지 못한다.