[자료구조💾] 1장 자료구조 개요

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스)

 

1.1 소프트웨어와 자료구조

1)소프트웨어

- 소프트웨어(software) : 특정 기능을 담당하는 단일 혹은 복수의 프로그램

- 프로그램 : 처리할 대상인 자료(데이터)와 처리 절차인 알고리즘(algorithm)으로 구성된다.

- 프로그래밍(programming) 혹은 코딩(coding) : 프로그램을 설계하는 작업

- 알고리즘 : 주어진 문제 해결에 필요한 절차(procedure)를 체계적으로 구성해 놓은 것 

- 데이터(data) : 일상생활에서관찰된 정보를 수치 또는 문자로 기록해놓은 것

- 정보(information) : 수집된 데이터를 분석하여 새롭게 알아낸 사실

- 지식(knowledge) : 연관된 정보들의 모임

 

2) 자료구조

- 자료구조(data structure)

• 프로그램을 통해 대량의 데이터를 효과적으로 저장하고 처리하기 위한 방법론(methodolgy)
• 자료구조 그 자체

- 자료구조는 구현 방법에 따라 배열 방식과 연결리스트 방식으로 구분할 수 있다.

- 자료구조 구분( 형태 ) 

• 선형 자료구조 (linear data structure)
  • 배열(array), 스택(stack), 큐(queue), 리스트(list)
• 비선형 자료구조 (non-linear data structure)
  • 트리(tree), 그래프(graph)

 

 

1.2 소프트웨어 개발 주기 (software life cycle)

1) 요구 사항 (requirement)

- 개발하려는 소프트웨어의 목표 정의

-소프트웨어의 목표 사용 환경(platform), 기능(function), 입출력, 사용자 인터페이스(interface) 등의 정보를 요구사항 명세서에 기록한다.

 

2) 문제 분석 (analysis)

- 소프트웨어 요구사항을 세부적인 문제로 분할

- 대표적인 문제 분석 기법 : 상향식 방법, 하향식 방법

- 상향식 방법 (bottom-up)

• 기본 모듈을 조합하여 중간 단위의 서브 시스템을 완성
• 서브 시스템을 결합하여 최종적인 목표 시스템 구축

- 하향식 방법 (top-down)

• 프로젝트의 최상위 목표에서 하위 단계로 세부 모듈들을 분리
• 전체 모듈의 계층도(hierarchy)를 생성한다.

 

3) 설계 (design)

- 전 단계에서 생성된 모듈에서 필요한 객체(object)와 연산(operation)들을 정의한다.

- 객체는 속성(attribute)과 메소드(method)로 이루어진다.

 

4) 구현 (implementation)

- 각 모듈에서 사용하는 객체와 메소드 함수를 실행 가능한 코드로 작성하는 과정 

 

5) 검증 (verification)

- 구현된 프로그램이 프로젝트의 목표 기능들을 정확히 수행하고 오류가 없는지 확인하는 과정

- 데이터셋을 이용한 시험(testing) 방법을 사용함.

• 블랙 박스 시험 (black box test) : 입력 데이터와 출력 결과만으로 판단.
• 화이트 박스 시험 (white box test) : 입력과 출력 정보외에 프로그램 내부 루틴까지 포함하여 오류 검사

- 평가 결과에서오류가 발생하면 오류의 원인에 해당하는 단계로 돌아가서 개선 절차(improvement)를 수행한다.

 

 

1.3 알고리즘의 정의

- 알고리즘(algorithm) : 주어진 문제 해결(program solving)에 필요한 유한한 명령어(instruction)들의 집합

- 알고리즘의 조건

• 입력(input) : 0개 이상의 입력이 있어야 함.
• 출력(output) : 1개 이상의 출력이 있어야 함.
• 명확성(definiteness) : 모호하지 않은 명령어로 표현되어야 함. 
• 유한성(finiteness) : 유한한 수의 명령어로 이루어져야 함.
• 유효성(effectiveness) : 중복되고 불필요한 명령문 없이 효율적으로 작성되어야 함.

 

1.4 추상 자료형

- 추상자료형(ADT; abstrac data type) : 클래스

- 객체 지향 프로그래밍 (object oriented programmig) 

- ex) 분수 자료형

class Fraction:
    def __init__(self, up, down):
        self.num = up
        self.den = down

    def __str__(self):
        return str(self.num) + "/" + str(self.den)

    def __add__(self, other):
        new_num = self.num * other.den + self.den*other.num
        new_den = self.den*other.den
        common = self.gcd(new_num,new_den)
        return Fraction(new_num//common, new_den//common)

    def __mul__(self, other):
        new_num = self.num*other.num
        new_den = self.den*other.den
        common = self.gcd(new_num, new_den)
        return Fraction(new_num//common, new_den//common)

    def __sub__(self, other):
        new_num = self.num*other.den - self.den*other.num
        new_den = self.den*other.den
        common = self.gcd(new_num, new_den)
        return Fraction(new_num//common, new_den//common)

    def gcd(self, a, b):
        while a % b != 0:
            a, b = b, a % b
        return b

 

 

1.5 프로그램 성능 평가

1) 성능평가

- 성능평가 : 개발된 프로그램을 평가

- 정량적 성능 평가 기준

• 시간 복잡도(time complexity) : 프로그램 수행이 완료되는 데 걸리는 시간(computation time)
• 공간 복잡도(space complexity) : 프로그램 수행을 완료하는 데 필요한 메모리의 양(memory space)

 

2) 공간 복잡도

- 알고리즘 실행에 필요한 메모리의 양

- 알고리즘이 사용하는 메모리 공간

• 고정 요구 공간 (fixed memory space)
  • 프로그램이 샐행하는 중에 크기의 변동이 없는 메모리 공간
  • ex) 프로그램 명령어, 고정 크기 변수, 상수 등
• 가변 요구 공간 (variable memory space)
  • 프로그램 실행 중에 요청되어 그 크기를 예측하기 어려운 경우
  • ex) 함수에 배열 전달(array passing), 재귀호출(recursion)
  • 공간 복잡도 평가에서 더욱 중요함.

 

3) 시간 복잡도

- 프로그램이 실행을 완료하는 데 필요한 시간

• 컴파일 시간 (complie time) : 예측 가능한 고정 시간
• 실행 시간 (execution time) : 가변적이므로 시간 복잡도 평가에서 중요함.

- 실제 실행 시간보다는 명령문의 수를 세어 시간복잡도로 사용함.

• 명령문 측정표
  1. 한 문장에 포함된 명령문의 수(steps/execution)를 결정함.
  2. 이 문장의 실행 횟수를 명령문 수 * 반복 횟수 로 계산함.
  3. 전체 문장의 실행 횟수를 모두 합산함.

 

4) 점근적 표기법

- 점근적 표기법 (asymptotic notation)

• 입력의 수(n)가 증가할 때 알고리즘의 시간 복잡도의 변화 패턴을 표기하는 방법
• 알고리즘 성능에 영향을 크게 미치는 부분만을 취하여 근사적으로 표기한다.
• 점근적 표기법은 시간 복잡도의 상한선(upper bound) 또는 하한선(lower bound)의 유무에 따라 O, Ω ,θ 기호를 사용하여 표현한다.

- 빅 오 시간 복잡도

• n₀ 이상인 모든 n에 대해서, 시간 복잡도 함수 f(n) ≤ c*g(n)을 만족하는 양의 상수 c와 n₀가 존재한다면, f(n) = O(g(n))이라 표기 가능
• n₀보다 큰 모든 n에 대해서 f(n)의 수행 시간은 상한선 c*g(n)을 넘지 않는다.

 

- 빅오메가 시간 복잡도

• n₀ 이상인 모든 n에 대해서, 시간 복잡도 함수 f(n) ≥ c*g(n)을 만족하는 양의 상수 c와 n₀가 존재한다면, f(n) = Ω (g(n))이라 표기 가능
• n₀보다 큰 모든 n에 대해서 f(n)의 수행 시간은 하한선 c*g(n)보다 항상 많이 걸린다.

 

- 빅 세타 시간 복잡도

• n₀ 이상인 모든 n에 대해서, 시간 복잡도 함수 c₁*g(n) ≤ f(n) ≤ c₂*g(n)을 만족하는 양의 상수 c₁, c₂와 n₀가 존재한다면, f(n) = θ(g(n))이라 표기 가능
• n₀보다 큰 모든 n에 대해서 f(n)의 수행 시간은 하한선( c₁*g(n))과 상한선(c₂*g(n)) 범위 사이에 존재한다.

 

- 시간 복잡도 함수의 종류

시간 복잡도	이름
O(1)	상수형 (constant)
O(log2n)	로그형 (logarithm)
O(n)	1차형 (linear)
O(nlog2n)	n로그형(n-logarithm)
O(n2)	2차형(quadratic)
O(n3)	3차형(cubic)
O(2n)	지수형(exponentila)
O(n!)	팩토리얼(factoriial)