알고리즘 학습을 위한 준비

* 컴퓨터 프로그램

- 사람들의 문제를 해결하고 돕기 위한 도구로서의 프로그램

- 컴퓨터는 S/W와 H/W의 두  요소로 구성됨

- S/W는 응용프로그램과 운영체제로 분류됨

- 프로그램은 명령어와 데이터의 집합(0,1)임

* 알고리즘

- 프로그램의 핵심은 문제 해결임

- 알고리즘은 문제를 해결하는 방법의 절차

- Data(자료) - 자료구조

- Instruction(명령어) - 알고리즘

- 서로 종속적

* 알고리즘과 자료구조

- 자료구조는 자료의 구성, 조직임

- 알고리즘은 문제를 해결하는 방법의 절차

- 알고리즘이 프로그래밍 코드로 표현되면 문제를 해결하기 위한 명령어들의 절차로 표현

* 프로그램의 핵심요소

- 자료구조

- 알고리즘

- 프로그램 구조(설계)

* 좋은 프로그램이란?

- 생산성이 높음

- 유지보수성

- 수정

- 확장성

* 알고리즘의 만족 조건

- 0개 이상의 입력

- 1개 이상의 출력

- 명확성 : 실행 명령어의 의미가 모호하지 않게 명확해야함

- 유효성 : 정확하게 실행 가능한 명령과 연산

- 유한성 : 반드시 종료되어야 함

* 알고리즘의 기술 방법

- 사람의 언어로 표현

- 플로우 차트로 표현 (Flow Chart)

- 의사 코드로 표현 (Pseudo Code)

- 프로그래밍 언어 (실무)

* 알고리즘 계산 복잡도 (실행 시간을 나타내는 빅오 표기법)

- 시간 복잡도 (Time Complexity) : 얼마나 오래 걸리는지 분석

- 공간 복잡도 (Space Complexity) : 얼마나 기억공간이 필요한지 분석

* 빅오(Big-oh) 표기법

- 연산 횟수로 측정하는 빅오 표기법

- 빅오 : 입력 크기 n에 대해 계산 횟수가 어느 정도 인지를 표현

- 점근 표기법으로 알고리즘의 수행 시간을 대략적으로 나타냄

- O(1) : 입력 크기 n에 대해 n과 무관하게 계산횟수가 일정

- O(n): : 입력 크기 n에 대해 n과 계산횟수 비례

- O(n^2) : 입력 크기 n에 대해 계산 횟수가 거듭제곱(지수)로 증가

- 데이터 입력 크기 n에 대해 점근 표기법인 빅오에서는 최대 차항을 제외한 나머지는 입력크기 n이 커질수록 수행시간에 영향을 주지 않음

- 최대차 항을 제외한 모든 항과 모든 계수를 제거

* 빅오(Big-oh) 시간 복잡도

- O(1) : 해시 테이블 (입력 크기와 상관없이 일정한 시간)

- O(log2n) : 이진 탐색 (로그시간 수행시간 증가)

- O(n) : 순차 탐색 (입력크기와 비례적인 수행시간 증가)

- O(n log2n) : 퀵 정렬(O(n) 보다는 훨씬 수행시간이 길지만 O(n^2)보다는 훨씬 작음)

- O(n^2) : 선택정렬 (두 for가 중첩되어 구현

- O(n^3) : n의 3제곱으로 수행시간 증가