[개념] 알고리즘이란?

 

01. 알고리즘의 정의

• 문제를 해결하기 위하여 수행해야 할 기능의 집합이다.
• 알고리즘과 데이터 구조를 결합하여 프로그램이 완성된다.
• 순서도, 의사코드 등을 통해 알고리즘을 표현할 수 있다. 

02. 알고리즘의 특성

• 입력은 존재하지 않을 수 있다.
• 출력은 반드시 1개 이상 존재한다.
• 모든 기능은 명확한 의미와 완벽한 구성을 갖춰야 한다.
• 모든 기능은 지정한 횟수만큼 반복된 후 종료되어야 한다.
• 모든 기능은 실제로 연산 가능한 것들이어야 한다.

03. 알고리즘 성능 판단의 기준

• 특정 입력에 대해 기대 출력값이 동일한지 판단한다.
• 알고리즘 표현이 간단하고 이해가 용이한지 판단한다.
• 입력 데이터에 비례하여 몇 번의 명령을 실행하여 결과를 출력하는 지 분석한다.
• 평균적인 명령 수행시간과 최악의 명령 수행시간의 차이를 분석한다.

04. 순서도와 의사코드

• 순서도 : Flow Chart
  • 약속된 도형과 기호를 사용하여 알고리즘을 표현한 양식이다.
  • 쉽고, 공통된 형식으로 표현하기 때문에 서로 다른 프로그래밍 언어로 변환이 쉽다.
• 의사코드 : Pseudo Code
  • 일반적인 언어로 코드를 흉내내어 알고리즘을 표현한 코드이다.
  • 특정 프로그래밍 언어의 문법을 따른것이 아니라 실행은 불가능하다
  • 특정 언어로 프로그래밍하기 전에 알고리즘의 모델을 대략적으로 모델링 하는 경우 사용한다.

 

05. 알고리즘 설계기법

1) 동적 계획법(Dynamic Programming)

• 어떤 문제를 해결하기 위해 그 문제를 더 작은 문제의 연장선으로 생각하는 방식 (Bottom-up)
• 작은 문제의 풀이를 활용하여 더 큰 문제의 해를 찾는다

2) 탐욕적 알고리즘(Greedy Algorithm)

• 분기마다 가장 최적의 해를 선택하여 결과를 도출하는 방식이다.
• 반드시 종합적인 최적 해를 보장하진 않는다.

3) 재귀적 알고리즘(Recursive Algorithm)

• 풀이 도중 같은 풀이를 다시 불러오는 과정을 반복하는 방식이다.
• 호출의 역순으로 결과가 도출된다. 

4) 근사 알고리즘(Approximation Algorithm)

• 최적화되는 답을 구할 수는 없어도 비교적 빠른 시간에 계산이 가능하도록 근사해법을 수행하는 알고리즘이다

5) 분할 정복법(Divide and Conquer)

• 크고 방대한 문제를 효율적으로 풀 수 있는 단위로 작게 나누는 방식이다. (Top-down) 
• 계산된 결과를 다시 합쳐서 큰 문제의 결과를 구한다.

6) 퇴각 검색법 (Backtracking)

• 분기구조 탐색에서 탐색을 실패하는 경우, 탐색이 성공했던 이전 분기로 되돌아가는 방식이다.
• 새로운 탐색이 가능한 분기까지 과정을 되돌려 진행하는 알고리즘이다.
• 대표적으로 깊이우선탐색 알고리즘(DFS)이 있다.