자료구조와 알고리즘

1. 프로그램이란 컴퓨터에서 특정작업을 하는 명령어들의 집합

2. 소프트웨어란 목적을 수행하기 위한 하나 혹은 다수의 컴퓨터 프로그램으로 구성.

3. 소프트웨어 개발과정 : 요구분석 -> 설계 -> 구현 -> 통합/테스트 -> 유지보수

4. 자료구조와 알고리즘 : 어떻게 프로그램을 개발할 것인가..에 대한 주제

  - 자료구조 : 데이터값을 효율적으로 접근하여 처리하도록 표현하는것

  - 알고리즘 : 문제를 해결하기 위한 자료처리 과정

 

5. 자료구조의 종류

  5-1. 협의의 자료구조 :

    - 단순 자료 구조 : String, Array(배열), Record (DBMS에서 튜플의 개념)

    - 선형 자료 구조 : Stack, Queue, List

    - 비선형 자료 구조 : 트리(일반, 2진, 특수), 그래프

  5-2. 기본 데이터 타입 : 정수형, 실수형, 문자형, 논리형 등

  5-3. 파일 구조 : 직접파일, 순차파일, 색인순차파일

 

6. 추상자료형 (Abstract Data Type)

  6-1. 추상화란 : 공통적, 필수적 속성을 골라 단순화시킴

  6-2. 프로그램(소프트웨어)의 추상화 : 모듈 사용방법과 세부적인 구현사항을 분리

  6-3. 자료 추상화 :

    자료 (프로그램 처리대상, 혹은 값 그자체)

    + 연산 (어떤 일을 처리하는 과정)

    + 추상자료형 (자료 집합과 연산자의 집합)

 즉, 추상자료형이란 자료집합과 연산자들의 집합을 말한다.

  6-4. 인터페이스 : 프로그램에서 연산(Operation)을 분리시킴. 

  예시) C언어 : 인터페이스 -> *.h의 헤더파일에 저장하나,

                   독자적인 명칭의 추상자료형(Class)는 지원하지 않음

  예시) 객체지향언어 (C++/Java) : 추상데이터타입을 지원함.

 

7. 알고리즘

  7-1. 알고리즘이란 : 특정문제를 해결하기 위해 기술한 일련의 명령문

  7-2. 좋은 알고리즘의 요건 :

      - 완전성과 명확성 : 의도한 결과가 나와야 함

      - 입력과 출력 : 제공되는 데이터는 있을수도 있고 없을수도 있지만, 처리하여 얻은 결과가 있어야 함

      - 유한성 : 무한루프를 돌면 안 됨

      - 효과성 : 수행 가능한 것이어야 함

  7-3. 알고리즘 표현

      - 자연어 (서술적 표현) : 

      - 순서도 (도식화 표현) : 순차(명령어 다음에 명령어가 나옴) + 반복(명령어의 반복) + 조건(명령 수행 조건)

      - 프로그래밍언어 (구체화 표현) :

      - 유사코드 (추상화 표현) :

  7-4. 복잡도 이론

    7-4-1. 알고리즘 성능 평가 : 성능 분석(복잡도 분석방법) or 성능 측정(수행시간 측정)

        7-4-1-1. 성능 분석

           - 공간 복잡도 (Space Complexity) : 저장공간의 사용량을 측정

              고정공간(명령어공간, 변수, 상수 등) + 가변공간(크기가 변하는 데이터구조, 런타임스택)

           - 시간 복잡도 (Time Complexity) :  문장이 몇번 수행되는지 측정

     7-4-2. 알고리즘 분석 표현법

           - 빅오 표기법 : Big-Oh, Big-Omega, Big-Theta 등

           - Big-Oh 표기법

              3n+2 -> f(n) = O(n)

              1000n^2 + 100n + 6 -> f(n) = O(n^2)

              6*2n + n^2 -> f(n) = O(n^2)

              100 -> f(n) = O(1)

 

<출처>

1. C로 쉽게 풀어쓴 자료구조(2019), 천인국, 생능출판사

2. C언어를 이용한 체험!자료구조(2018), 정기철, 연두에디션

3. C로 배우는 쉬운 자료구조(2013), 이지영, 한빛아카데미