알고리즘, 들어가기 앞서

알고리즘 들어가기전,

문제를 해결하기 위한 단계적 절차를 갖는 여러 동작들의 모임

→ 문제 해결 과정을 묘사하는 것

일을 처리하기 위한 일련의 과정을 기술하는 방법(단계적인절차에 따라 주어진 문제의 답을 찾아가는 과정)

해결하고자 하는 문제에 항상 보다 효율적인(적합한)알고리즘을 사용하는것이 매우 중요 → 생각하는 방법을 훈련하는것

알고리즘의 특성 [ 정확성 / 수행성 / 유한성 / 효율성 ]

정확성: 알고리즘은 주어진 입력에 대해 올바른 결과를 출력

수행성: 알고리즘의 각 단계는 컴퓨터에서 수행 가능하여야 함

유한성: 알고리즘은 일정한 시간 내에 종료되어야 함

효율성: 알고리즘은 효율적일수록 그 가치가 상승

의사코드

1. 일종의 프로그래밍 코드와 유사한 방식으로 작성된 코드
2. 설계자가 알고리즘의 로직에 집중할 수 있도록 알고리즘을 묘사하는 정형화 된 언어
3. 각 모듈이 동작하는 논리를 표현하기 위해 사용
4. 단, 의사코드 만으로는 컴퓨터에서 수행되지 않는다.

흐름도

사전에 정의된 기호화 기호들의 연결선으로 구성된 도형의 집합으로 기술

입력,출력,처리,연산 등의 절차를 사용자가 쉽게 인지하기 위한 표현

알고리즘의 분류

1. 분할 정복 알고리즘
2. 탐욕 알고리즘
3. 동적 계획 알고리즘
4. 근사 알고리즘
5. 백트래킹 기법
6. 분기 한정 기법

문제에 기반한 분류

1. 정렬 알고리즘
2. 그래프 알고리즘

3. 기하 알고리즘

   특정 환경에 따른 분류

   1. 병렬 알고리즘
   2. 분산 알고리즘
   3. 양자 알고리즘

알고리즘의 효율성

→ 알고리즘 수행시간의 크기 또는 알고리즘이 수행하는 동안 사용되는 메모리 공간의 크기로 표현 가능

이를 시간복잡도 , 공간복잡도로 표현

공간 복잡도 : 문제를 해결하는데 사용된 메모리의 사용량

(최근엔 많이 사용하지 않는 추세, WHY? 메모리의 양은 점점 커지기 때문에 굳이 고려하는 추세는 아님)

시간 복잡도 : 문제를 해결하는데 걸리는 시간의 크기

시간복잡도의 사용량이 점점 증가하는 추세다.

시간 복잡도는 알고리즘이 수행하는 기본적인 단위 연산의 횟수를 입력 크기에 대한 함수로 표현

→ 기본 연산(Elementary Operation)이란 데이터 간 크기 비교, 데이터읽기, 갱신, 숫자 계산 등과 같은 단순한 연산을 의미

알고리즘의 복잡도를 표현하는 방법

→ 최악 경우 분석 : 어떤 입력이 주어지더라도 수행시간이 얼마 이상은 넘지 않는다를 의미

→ 평균 경우 분석 : 입력의 확률 분포를 가정하여 분석하는데, 일반적으로 균등 분포를 가정

→ **최선 경우 분석 **: 가장 빠른 수행 시간을 분석, 거의 사용하지 않으나, 최적 알고리즘을 찾는것에 활용

worst case 분석으로 알고리즘의 복잡도를 표현 ( 최악 경우 분석 )

복잡도의 점근적 표기

복잡도는 입력 크기에 대한 함수로 표기

→여러 개의 항을 가지는 다항식으로 나타낼 수 있다.

입력크기가 매우 작다면 알고리즘의 효율성과 상관 없지만, 입력의 크기가 충분히 큰 경우 알고리즘의 효율성이 매우 중요

입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법

점근적 표기 → 입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법 → 함수의 다항식에서 복잡도에 가장 큰 영향을 미치는 최고차항만을 계수 없이 취하여 단순한 형태로 표기하는 방법 Ex) 3𝑛^3 − 15𝑛^2 + 10n − 18 의 점근적 표기 : 𝑛^3 → 4n+6 의 점근적 표기 : n

단순화된 식에 상한, 하한, 동일한 증가율의 개념을 적용하여 표기→ O(Big-Oh)-표기 → Ω(Big-Omega)-표기 → 𝜃(Theta)-표기

<참고 표=""> $$ 모든 𝑛 ≥ 𝑛଴에 대해서 𝑓 𝑛 ≤ 𝑐𝑔(𝑛)이 성립하는 양의 상수𝑐와𝑛଴가 존재하면, 𝑓 𝑛 = 𝑂(𝑔 𝑛 )이다.  $$ ## BIG - OH 표기법 →의미 : N이 증가함에 따라 O(N)이 점근적 상향이라는것을 의미함 → 즉, g(n)이 n_0보다 큰 모든 n에 대해서 항상 f(n)보다 크다는것 **다항식에서 최고 차수 항만을 취한뒤, 그 항의 계수를 제거하여 g(n)을 정한다.** ## Ω-표기법(BIG-Omega notation) **Ω-표기의 정의** $$ 모든 𝑛 ≥ 𝑛_0에 대해서 𝑓 𝑛 ≥ 𝑐𝑔(𝑛) 이 성립하는 양의 상수𝑐와𝑛_0가 존재하면, 𝑓 𝑛 = Ω(𝑔 𝑛 )이다. $$ **Ω-표기의 의미** 𝑛_0 보다 큰 모든 𝑛 대해서 𝑓 𝑛 이 c𝑔 𝑛 보다 작지 않다는 것 𝑓 𝑛 = Ω(𝑔 𝑛 ) 은 양의 상수를 곱한 𝑔 𝑛 이𝑓 𝑛 에미치지 못한다는 뜻, 즉 **𝑔 𝑛 을 𝑓 𝑛 의 하한(Lower Bound)이라고 한다.** ## 𝜃-표기법(Theta notation) **𝜃-표기의 정의** $$ 모든 𝑛 ≥ 𝑛଴에 대해서 0 ≤ 𝑐ଵ𝑔 𝑛 ≤ 𝑓 𝑛 ≤ 𝑐ଶ𝑔(𝑛)이 성립하는 양의상수 𝑐ଵ, 𝑐ଶ, 𝑛଴가 존재하면, 𝑓 𝑛 = Θ(𝑔 𝑛 )이다. $$ **𝜃-표기의 의미** 1. 수행시간의 **O-표기와 Ω-표기**가 동일한 경우에 사용 2. 즉 동일한 증가율을 의미 → $$ 2𝑛^2 + 3𝑛 + 5 = 𝑂(𝑛ଶ )과 동시에 2𝑛^2 + 3𝑛 + 5 = Ω(𝑛^2 ) 이므로, 2𝑛^2 + 3𝑛 + 5 = Θ(𝑛^2 ) $$ $$ Θ(𝑛^2 )은 𝑛^2과 2n^2 + 3𝑛 + 5가 유사한 증가율을 가지고 있다는 뜻 $$ 𝑛_0보다 큰 모든 𝑛에 대해서 Θ-표기가 상한과 하한을 동시에만족한다는 것을 보여준다