Chapter 01. 자료구조와 알고리듬

 

1.1 자료구조와 알고리듬

  1.1-1 자료구조란,

      Def) 자료구조(Data Structure)

        자료(data)를 저장할 수 있는 공간을 의미함.

        각 자료구조마다 특징이 있어서, 

        때에 따라 잘 골라서 자료를 저장해야 빠르게 접근할 수 있음.

 

      Note) 자료구조의 종류

        크게 선형 자료구조와 비 선형 자료구조로 나뉨.

        선형 자료구조: 배열/가변 배열/스택/큐/해쉬 테이블

        비선형 자료구조: 링크드 리스트/트리/그래프/힙

 

  1.1-2 알고리듬이란,

    Def) 알고리듬(Algorithm)

      알고리듬이란, 어떤 문제를 해결하는 명백한 방법

      "어떤 문제"란 문제가 특정되어 있다는 것.

      임의의 문제를 풀 수 있는 것이 아님.

      "명백한 방법"이란, 방법이 모호해서는 안된단 것.

 

    Note) 알고리듬의 예

      - 마치 라면 끓이기와 같음.

        라면 뒷 면에는 라면회사 연구원들이 심혈을 기울여서

        "어떤 라면"을 가장 맛있게 끓이는 "명백한 방법"에 대해 적어두었음.

        즉, 해당 라면에 국한된 라면 끓이기 방법이란 것과

        그 방법이 모호하지 않음. 자세히 설명되어 있음.

      - 화장실 타일 깔기

        균일한 크기의 정사각형 타일 깔기

        이때 타일은 최대한 큰 크기로 해야 원가 절감이 가능하다면?

        이 문제는 사실 최대 공약수를 구하는 문제.

        여기서 필요한 알고리듬은 유클리드의 호제법

        기록으로 남아 있는 알고리듬 중 가장 오래된 알고리듬.

 

    Note) 이런 알고리듬을 본인이 직접 고안할 자신이 있을까?

      학계라면 직접 고안해야하겠지만, 우리는 실무가 목표.

      따라서 알고리듬의 고안보다는, 기존 것의 사용/확장/응용이 중요

      또한 알고리듬의 성능 및 올바른 측정이 중요함.

    

    Note) 즉, 어떤 문제를 풀 수 있는 명백한 방법이 있는데

      굳이 헤집어가지고 다른걸로 만들진 말자.

      나중에 코더를 벗어나, 프로그래머 수준이 되었을때

      그때 알고리듬을 천천히 변형 시켜서 

      다른 문제에도 적용시켜보자.

 

  1.1-3 자료구조와 알고리듬을 배우는 이유

    Note) 요즘엔 많은 알고리듬을 언어 자체에서 지원함.

      그러나 스스로 구현하지 못하는 프로그래머는 명백한 한계가 있음.

      - 각 알고리듬의 장단점 및 성능에 대한 이해 부족.

      - 어디에 어떤 알고리듬을 사용해야 하는지 모름.

      - 기존 알고리듬을 제대로 응용하지 못함.

      즉, 알고리듬을 제대로 사용하고, 더 나아가 응용과 발전을 하기 위함.

      면접에서도 기초 알고리듬 질문은 필수 절차

      기초 문제 해결 능력을 평가하기 위해서임.

      또한, 응용이 가능할 정도로 기초가 잘 잡혀있는지 평가하기 위함.

      새로운 문제들을 해결할 능력이 있는지 판단하는 척도.

      정리하자면, 기초 알고리듬을 깊이 이해하고 있는 것이 중요.

 

    Note) 아래에 해당하는 사람들은 기초 문법을 다시 배우고오자.

      - 하드웨어가 어떤 연산을 지원하는지,

        어떤 연산이 비효율적이며,

        어떤 연산이 더 빠른지 전혀 관심없다.

      - 이미 존재하는 마법 같은 함수만 호출해 봤고,

        그 함수가 어떻게 도는지 궁금하지 않다.

      - 자신이 짠 코드에서 툭하면 언어 문법이 틀림.

        게다가 컴파일 에러를 봐도 그 문제를 못찾음.

      - 컴퓨터에 데이터가 어떻게 저장되는지 모르겠다.

        ex. char는 정수 자료형일까? 문자 자료형일까? 

          이에대한 명확한 대답을 못함.

      - 스택 메모리와 힙 메모리 차이에 대해 모름.  

      위 사항들의 중요성을 알아야 알고리듬을 더 잘 이해할 수 있음.

 

  1.1-4 알고리듬의 비교

    Note) 좋은 알고리듬이란,

      - 입력과 출력이 명확히 정의되어 있어야 함.

        다만, 입력은 시작 시 비어 있을 수도 있음.

      - 알고리듬의 각 단계가 명확하며 모호하지 않아야  함.

      - 유한 시간 내에 결과(출력)가 나와야 함.

      - 포팅이 어려운 컴퓨터 코드를 포함하면 안됨.

        특정 언어에만 있는 기능을 사용하면 안됨.

        거의 모든 언어에 공통되는 연산만 사용해야 함.

        결국 하드웨어와 기계어/어셈블리어 수준에서 지원하는 것들.

        고수준 언어에서는 C언어가 대표적. 단, 포인터 연산 제외.

      - 같은 문제를 푸는 다양한 알고리듬 중에 가장 효율적임.

      - 우리가 작성해야 할 알고리듬의 지향점

 

    Note) 알고리듬의 비교

      자원의 효율적인 사용을 기준으로 비교함.

      컴퓨터에서 자원이란 아래 두 가지를 의미함.

      시간(time): CPU 속도 등

      공간/용량(space): 메모리 공간 혹은 디스크 공간

                             주로 메모리 사용량을 뜻함.

 

    Note) 시간과 공간은 종종 상반 관계임.

      내가 사용하는 기계 기준으로,

      CPU 속도가 막강하냐 Vs. 메모리 공간이 막강하냐

      위에 따라서 알고리듬 선택함.

 

    Def) 복잡도(Complexity)

      정확한 정의는 아니지만, 자원을 많이 사용할 수록

      그 알고리듬이 복잡하다고 말함. 복잡도의 종류로는

      시간 복잡도와 공간 복잡도가 있음.

      복잡도를 표기하는 방법에는 대표적인 점근 표기법인

      빅오 표기법이 있음.

 

    Def) 점근 표기법(Asymptotic Notation)

      정수론과 해석학의 방법

      어떤 함수가 증가하는 모습을 다른 함수와 비교

      알고리듬의 복잡도를 논하거나 단순화 시킬 때 사용

 

    Note) 대표적인 점근 표기법

      - 대문자 O 표기법(Big-O Notation)

        컴퓨터 공학에서는 주로 이 표기법을 사용함.

      - 소문자 o 표기법

      - 대문자 오메가 표기법

      - 소문자 오메가 표기법

      - 대문자 세타 표기법

 

    Note) 컴퓨터 공학에서의 빅오 표기법

      이름에서 알 수 있듯이 대문자 O를 이용해 표기

      주로 알고리듬을 분류하기 위해 사용함.

      최선 <-----------------------------------------------------> 최악
      O(1) / O(logN) / O(N) / O(NlogN) / O(N^2) / O(2^N) / O(N!)

      보통 N^2까진 괜찮다함. N^3부터는 최적화 들어감.

 

    Note) O의 의미는 "대략 그 정도, order of the function"

      ex. She makes in other order of $90,000 a year.

        그녀의 연봉은 9만 달러대이다.

 

    Def) Big-O Notation

      입력 개수 N에 따라 작업 완료에 필요한 연산의 횟수.

      정확한 연산의 횟수가 아닌, 비례적인 횟수를 나타냄.

      1. 영향력이 가장 큰 대표 최고차항만 남김.

        실행 시간 증가에 가장 큰 영향을 미치는 항만 사용해 일반화함.

      2. 계수는 무시.

        N이 충분히 크면 계수의 영향보다는 지수의 영향이 훨씬 크기 때문.

      3. O는 Oder of라고 읽음.

        1번과 2번을 보면 왜 "대략 이정도"의 의미인지 알 수 있음.

 

    Note) 결국 빅오 표기법은 입력 데이터가 많아짐에 따라

      실행 시간과 필요한 공간이 얼마나 늘어나는지 측정

      최근에는 알고리듬에서 주로 신경 쓰는 부분은 실행 시간

      즉, 입력이 증가함에 따른 시간 및 공간의 증가량을 의미

 

    Ex12000201) BigONotation1.c

      아래 예제에서 func()의 시간 복잡도를 빅오 표기법으로 표현해보자.

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int res[3] = {0,};

void func(int n);

int main(void)
{
    int N;
    scanf("%d", &N);
    func(N);

    return 0;
}

void func(int n)
{
    int sum = 0;

    for (size_t i = 0; i < n; ++i)
    {
        sum += (int)i;
    }

    for (size_t i = 0; i < 2 * n; ++i)
    {
        for (size_t j = 0; j < 2 * n; ++j)
        {
            sum += 1;
        }
    }
    
    sum += 123456;
    
    return sum;
}

<hide/>

O(1 + N + 4*N + 3*N^2) // 1번 규칙
O(4*N^2)               // 2번 규칙
O(N^2)

 

    Note) O(1) 알고리듬 예시

      - min / max 찾기

        배열의 첫 인자와 끝인자가 각각 min, max

      - 배열의 특정 두 원소의 합

        nums[i] + nums[j]

 

    Note) O(logN) 알고리듬 예시

      - up-down 게임

        특정 숫자를 찾기 위해서 반씩 줄여나감.

 

    Note) O(N) 알고리듬 예시

      - 총합 구하기

        모든 숫자를 접근해야만 함.

      - 두 이웃 원소 사이의 차이값 구하기

 

    Note) O(NlogN) 알고리듬 예시

      - 추후에 관련 알고리듬을 배울 때 알아보자.

 

    Note) O(N^2) 알고리듬 예시

      - 각 원소들의 곱

        마치 구구단 표와 비슷.

 

    Note) 상황에 따라 달라지는 빅오표기법

      - 데이터에 따라 실제 알고리듬의 실행 속도가 달라짐

        ex. 배열에서 7을 찾는다고 해보자.

            nums1: 7 6 5 4 3 2 1 0 -> O(1)

            nums2: 1 2 5 6 7 4 3 0 -> O(N/2)

            nums3: 0 1 2 3 4 5 6 7 -> O(N)

      - 최선 Vs. 평균 Vs. 최악

        일반적으론 평균 시간을 시간 복잡도로 사용.

        절대로 느려지면 안되는, 어떤 순간에도

        느려지는게 용납되지 않는 분야에서는 

        최악 시간도 추가적으로 표기함.

      - 조금 더 나아가자면, 적절한 자료구조와

        적절한 알고리듬을 조합하면 항상 O(1)에 준하는

        결과를 얻어올 수 있음.

 

    Note) 빅오 표기법별 데이터의 개수에 따른 연산 횟수 테이블

출처:&nbsp;https://cooervo.github.io/Algorithms-DataStructures-BigONotation/index.html

 

    Note) 빅오 표기법별 데이터 개수와 연산 시간의 그래프

 

    Note) 대표적인 자료구조들의 시간 복잡도 테이블

출처:&nbsp;https://cooervo.github.io/Algorithms-DataStructures-BigONotation/index.html

  

  1.1-5 효율적인 알고리듬이란,

    Note) 빠른 알고리듬과 효율적인 알고리듬은 전혀 다른 이야기.

      아무리 빨라도 쓰지 못하는 알고리듬도 있음.

 

    Ex01010501) BigONotation.c   

      아래 세 가지 add() 함수는 결과적으로 같은 일을 함.

      세 함수의 시간 복잡도를 빅오 표기법으로 구해보자.

<hide/>

int Add1(int n) 
{ 
    return n * n;
}

int Add2(int n)
{
    int sum = 0;
    for (size_t i = 0; i < n; ++i)
    {
        sum += n;
    }
    return sum;
}

int Add3(int n)
{
    int sum = 0;
    for (size_t i = 0; i < n; ++i)
    {
        for (size_t j = 0; j < n; ++j)
        {
            sum += 1;
        }
    }
    return sum;
}

 

    Note) 컴퓨터에서 1씩 증가만 지원한다면?

      Add1()과 Add2()는 쓸 수 없음.

      즉 하드웨어에 따라 알고리듬은 차이가 생길 수 밖에 없음.

 

    Note) 알고리듬의 효율성 분석은 다소 추상적임

      알고리듬 공부를 할 때는 하드웨어 차이에 신경을 안씀.

      추상적인 기계에서 알고리듬을 실행한다 가정함

      알고리듬 자체에 집중하도록 도와줌.

 

    Def) 랜덤 접근 기계(Random-access machine, RAM)

      memory가 아니고, machine임에 주의.

      다양한 하드웨어를 일반적인 형태로 대표하는 가상의 기계

      레지스터를 갖춘 CPU 1개

      정수와 부동소수점 저장 가능.

      메모리 간접 참조(indirection) 지원

      캐시 메모리나 가상 메모리 등은 없음.

 

    Note) 알고리듬의 효율성과 실제 성능에 대한 주의점

      실제 코드 실행 속도는 하드웨어에 따라 매우 달라짐.

      따라서 실무에서는 효율성 낮은 알고리듬이 더 빠르기도 함.

      실무 최적화의 기초는 실제 하드웨어에서의 성능 측정.

      컴퓨터 구조를 공부해야 하는 이유

 

    Note) 알고리듬 공부를 통해 이론상의 성능에 확실히 습득해야 함.

      하드웨어에 따라 달라지는 부분은 추가 지식으로 늘려가면 됨.

 

  1.1-6 알고리듬의 올바름 검증

    Note) 알고리듬이 올바르게 작동하는지 검증하는 것도 중요.

      ex. Ex01010501에서 Add2() 함수에 음수를 넣으면?

 

    Note) 학계에서는 증명을 통해 검증을 시도하기도 함.

      컴퓨터 가격이 비쌌던 시절에는 매우 유용했던 방법

      cf. master`s theorem: 분할 정복 알고리듬에서 빅오 표기법 분석

      아직도 유용한 곳이 있으나 실무에서는 거의 사용 안함.

 

    Note) 실무에서는 버그 처리 프로세스를 따름.

      이전 기초 문법에서 테스트 및 버그를 잘 배웠다고 가정

      중요한 점은, 제대로 작동 하지 않는 알고리듬은

      효율성을 논할 가치도 없음.

 

    Ex01010502) add_algorithm.c

      이 덧셈 알고리듬은 비효율적이지만, 그래도 올바른 알고리듬.

<hide/>

#include <stdio>

int add(int num1, int num2);

int main(void)
{


    return 0;
}

int add(int num1, int num2)
{
    int sum = num1;

    for (int i = num2; i < 0; ++i) {
        --sum;
    }

    for (int i = 0; i < num2; ++i) {
        ++sum;
    }

    return sum;
}