알고리즘

- 컴퓨터로 문제를 풀기 위한 단계적 절차

    ex) 학생들의 평균점수를 구하는 일련의 과정

- 조건

 1. 입력: 0개 이상의 입력이 존재해야 한다. 입력이 없을 수도 있다.

 2. 출력: 1개 이상의 출력이 존재해야 한다.

 3. 명백성: 각 명령어의 의미는 명확해야한다. 모호하지 X. but, 인공지능은 모호한 정보도 모두 흡수하게 해서 다 이해한다

 4. 유한성: 한정된 수의 단계 후에는 반드시 종료되어야 함.

 5. 유효성: 각 명령어들은 실행 가능한 연산이어야 한다. 

 

- 기술방법

자연어, 흐름도(flow chart), 유사 코드(pseudo-code), 특정 프로그래밍 언어( C++, java, python 등)

1) 자연어

 ˙ 인간이 쓰는 언어.

 ˙ 단어들을 정확하게 정리하지 않으면 의미 전달이 모호해질 우려가 있다. 

2) 흐름도(flow chart)

 ˙ 직관적, 이해 쉬움.

 ˙ 그러나 복잡한 알고리즘의 경우, 너무 복잡해짐.

 ˙ 그림 상으로 표기하기 때문에, 언어가 달라도 서로 이해할 수 있다.

 ˙ 기호마다 약속된 의미가 있다.

3) 유사코드

 ˙ 자연어보다 더 구조적.

 ˙ 프로그래밍 언어보다 덜 구체적.

 ˙ 알고리즘 기술에 가장 많이 사용.

 ˙ 프로그램 구현할 때 여러가지 문제는 감출 수 있음.

 ˙ 핵심적인 내용만 검증할 수 있음.

4) 특정언어(programming language)

 ˙ 가장 정확한 기술.

 ˙ 많이 구체적으로 기술시 알고리즘의 핵심적인 내용들의 이해를 방해할 수 있음.

 ˙ ex) C언어로 표기된 알고리즘.

 

- 추상자료형(Abstract Data Type)

 ˙ 데이터 + 연산

 ˙ 추상화: 시스템의 핵심적인 내용(구조나 동작)만 추려내는 것.

 ˙ 자료형: 데이터 집합, 연산 집합.

 ˙ 데이터 타입을 추상적으로 정의한 것.

 ˙ 이 데이터(연산)는 무엇인가(what)는 정의 하나, 그것을 어떻게(how) 구현할 것인지는 정의하지 않음.

 ˙ 자연수 ADT

    데이터: 1에서 시작하여 INT_MAX까지의 순서화된 정수의 부분 범위

    연산: · add(x,y): x+y가 INT_MAX보다 작으면 x+y를 반환

           · distance(x,y): x가 y보다 크면 x-y를 반환하고 작으면 y-x를 반환

           · equal(x,y): x와 y가 같은 값이면 TRUE, 아니면 FALSE를 반환

           · successor(x): x가 INT_MAX보다 작으면 x+1을 반환한다.

 

- 추상 자료형과 자료구조

 ˙  자료구조: 추상 자료형을 프로그래밍 언어로 구현한 것.

 ˙  추상 자료형의 구현 데이터는 구조체 사용, 연산은 함수 사용.

 ˙ 다른 방법: 객체지향언어(C++, Java 등) 

 

- 알고리즘의 성능분석

 1) 실행 시간 측정

   ˙ 두 개의 알고리즘의 실제 실행 측정. 실제로 구현. 동일한 하드웨어, 소프트웨어 사용.

   ˙ clock 함수 사용: clock_t clock(void); 호출되었을 때 시스템 시각 반환. CLOCKS_PER_SEC 단위. 

 2) 알고리즘의 복잡도를 분석하는 방법

   ˙ 직접 구현하지 않고서도 수행 시간을 분석하는 것.

   ˙ 알고리즘이 수행하는 연산의 횟수 = n의 함수 측정하여 비교. 

   ˙ 시간 복잡도 분석: 수행 시간 분석.  ☆ 대표적으로 많이 사용!

      - 기본 연산(산술, 대입, 비교, 이동) 고려 

      - 알고리즘 수행에 필요한 연산의 개수 계산.

      - 입력한 개수 n에 대한 함수  → 시간복잡도 함수, T(n)

 

   ☆- 빅오 표기법: 가장 많이 사용됨!!!

        ▷ 최악의 성능을 측정할 수 있다.

        ▷ 차수가 가장 큰 항이 가장 영향을 크게 미치고, 다른 항들은 상대적으로 무시될 수 있음.

         ex) n = 100일 때, T(n) = n의 제곱 + 𝑛 + 1 에서 첫번째 항의 값이 크면 클수록 뒤의 항들은 영향을 거의 미치지              않는다.  → 가장 큰 항만 가지고 비교한다. 

        ▷ 빅오 표기법의 종류: 아래로 갈수록 점점 커진다.

          - O(1) : 상수형 

          - O(log n) : 로그형 

          - O(n) : 선형 

          - O(n* log n): 로그 선형 

          - O(n^2): 2차형

          - O(n^3): 3차형

          - O(n^k): k차형

          - O(2^n): 지수형

          - O(n!): 팩토리얼형

 

   ˙ 공간 복잡도 분석: 수행 시 필요로 하는 메모리 공간 분석