[열혈강의] 01. 자료구조의 시작

1. 자료구조의 정의

• 자료구조

  • 컴퓨터 프로그램을 구현하기 위해 연구된 것
  • 컴퓨터에 자료를 효율적으로 저장하는 방식

• 자료구조의 장점

  • 메모리 절약
    • 프로그램을 실행하는데 필요한 메모리가 적다
  • 프로그램 수행 시간을 최소화
    • 프로그램의 특정 기능을 실행하는데 걸리는 시간이 짧아진다

• 컴퓨터 프로그램의 공통점

  • 컴퓨터에 의해서 실행되는 명령어들의 집합
  • 명령을 수행하기 위해 내부적으로 여러 자료(Data, 데이터)를 저장

2. 자료구조의 분류

• 프로그램에서 저장하는 자료
  • 단순 구조 (Primitive Data Structure)
  • 선형 구조 (Linear Data Structure)
  • 비선형 구조 (Non-linear Data Structure)
  • 파일 구조 (File Organization)

분류	자료의 형태(Type)
단순 구조	정수(int), 실수(float, double), 문자 문자열(char)
선형 구조	리스트(list), 스택(stack), 큐(queue), 덱(deque)
비선형 구조	트리(tree), 그래프(graph)
파일 구조	-

• 단순 구조

  • 정수, 실수, 문자와 문자열 등의 프로그래밍 언어에서 제공하는 기본적인 데이터 타입

• 선형 구조

  • 각각의 자료들 사이의 앞뒤 관계가 일대일(1:1)인 경우

• 비선형 구조

  • 각각의 자료들 사이의 앞뒤 관계가 일대일(1:1)이 아닌 계층 구조(Hierarchical Structer)
    혹은 망 구조(Network Structure)인 경우

• 파일 구조

  • 보조기억장치에 저장되는 파일에 대한 자료구조

3. 추상 자료형

• 추상자료형이 필요한 이유
  • 정보 은닉
    • 컴퓨터 프로그래밍에서 중요하게 사용되는 개념 중 한가지
    • 중요한 정보만을 나타내고, 중요하지 않은 정보는 숨기는 것
    • 필요한 것 : 자료구조의 인터페이스 / 필요하지 않은 것 : 내부 구현 로직
    • 즉, 사용자의 관점에서 불필요한 정보를 제거하고, 사용자에게 반드시 필요한 것만을 심플하게 제공

3.1 자료, 자료형

• 자료형 = 자료 + 연산

• 예시

  • 정수 자료형
    • 자료 = 실수, 정수 ···
    • 연산(명령) = 더하기, 빼기, 곱하기, 나누기, 나머지 연산

3.2 추상화와 추상 자료형

• 추상 자료형

  • 추상적으로 정의된 자료형
  • 이름, 입력, 출력으로 구성

• 추상화

  • 세부적이고 복잡한 것을 생략하고 대표적인 것, 중요한 것만을 나타낸 것

4. 알고리즘

• 정의

  • 어떠한 문제를 해결하기 위한 방법
  • 컴퓨터 명령 자체의 효율성을 증가시키기 위한 방법

• 예시] 1부터 1씩 차례대로 증가시켜 100까지 모든 정수를 하나씩 더하는 경우

  CaclSum(n) {
    sum <- 0
    for (i <- 1; i <= n; i + 1) {
      sum <- sum + i;
    }
    return sum;
  }

• 문제 해결 필수 특성

  • 입력 : 외부에서 제공되는 자료가 0개 이상 존재해야 한다
  • 출력 : 적어도 1개 이상의 결과를 만들어야 한다
  • 명백성 : 각 명령어는 의미가 모호하지 않고 명확해야 한다
  • 유한성 : 한정된 수의 단계 뒤에는 반드시 종료된다. 무한히 동작해서는 안 된다.
  • 유효성 : 모든 명령은 실행 가능한 연산이어야 한다. 예를 들어 0으로 나누는 연산과 같이 실행할 수 없는 연산을 포함해서는 안 된다.

4.1 알고리즘의 표현

• 알고리즘을 표현하는 방법

종류	내용	특성
자연어	사람이 사용하는 일반적인 언어로 표현	기술하는 사람에 따라 일관성과 명확성이 달라지기 때문에 알고리즘 표현으로 부적절하다.
순서도	알고리즘을 그림으로 도식화해서 표현	알고리즘 각 단계를 직관적으로 표현할 수 있는 장점이 있으나, 복잡한 알고리즘을 나타내기에는 비효율적이다.
의사 코드	특정 프로그래밍 언어가 아닌 가상의(유사한) 언어로 표현	프로그래밍 언어보다는 덜 엄격한 문법이나, 자연어보다는 더 체계적으로 기술이 가능하다. 자료구조 / 알고리즘 책마다 약간씩 구문에 차이가 있다. 책에 다라 가상 코드, 유사 코드 혹은 슈도 코드라 불린다.
프로그래밍 언어	C와 같은 프로그래밍 언어로 표현	알고리즘을 구체적인 구현 소스를 통해 나타내기 때문에 추가 구현 단계가 필요 없다는 장점이 있으나, 너무 엄격하게 기술하여 비효율적인 경우가 있다.

4.2 순서도와 의사 코드

• 순서도 기호
  

  

4.3 알고리즘의 성능 분석

• 1 ~ 100 까지의 합

  • 차례대로 더하기

    • +1, +2 ····        // 100번의 연산

  • 공식 사용

    • 100 * (1 + 100) / 2     // 3번의 연산

• 알고리즘 분석 기준

  • 공간 복잡도
    • 알고리즘 실행에 필요한 저장공간이 얼마만큼 필요한지를 나타낸 것
  • 시간 복잡도
    • 알고리즘 실행에 시간이 얼마만큼 걸리는지를 나타낸 것
  • 대부분의 프로그램 환경에서 공간에 대한 비용보다 시간에 대한 비용이 더 크기 때문에 시간복잡도가 더 중요한 평가기준이 된다.

• 시간 복잡도

  • 입력 값에 다른 실행 연산의 빈도수
    • 차례대로 더하기 : 2 + n * 3;
    • 공식 사용 : 5
  • 빅-오(O) 표기법 : 최고 차항만 선택 (계수도 제외)
    • O(1) : 상수
    • O(logN) : 로그
    • O(n) : 1차, 선형
    • O(NlogN) : 선형로그
    • O(N^2) : 2차
    • O(N^3) : 3차
    • O(2^N) : 지수
    • O(N!) : 계승
    • O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(N^3) < 0(2^N) < O(N!)