[알고리즘] 알고리즘이란?

"알고리즘은 문제를 해결하는 단계적 절차 or 방법이다."

 

 

---

 

알고리즘의 특성

정확성	주어진 입력에 대한 올바른 해를 반환해야한다.
수행성	컴퓨터가 수행이 가능한 알고리즘이어야 한다.
유한성	일정한 시간 내에 종료되어야한다.
효율성	효율적일수록 그 가치가 높다.

 

 

 

---

 

알고리즘 표현

1. 의사 코드 (Pseudo Code)

• 의사코드는 긴 코드를 간략하게 표현한 프로그래밍 언어와 유사한 언어이다.

2. 플로우 차트 (Flow Chart)

• 의사 코드로도 표현하기 힘든 복잡하고 긴 알고리즘이 있다면 플로우 차트 형태로 표현하기도 한다. 

 

 

 

---

 

알고리즘의 분류

1. 분할 정복 (Divide-and-Conquer)
2. 그리디 (Greedy)
3. 동적 계획 (Dynamic Programming)
4. 근사 (Approximation)
5. 백트래킹 (Backtracking)
6. 분기 한정 (Branch-and-Bound)

 

---

 

알고리즘의 효율성

시간복잡도 (Time complexity)

• 알고리즘이 컴퓨터에 실행되는 수행 시간을 측정하는 것
• 알고리즘은 작성자나 여러 변수로 인해 객관적 시간 측정이 애매하다. 그래서 수행하는 기본적 연산 횟수를 입력 크기에 대한 함수로 표현한다.

공간복잡도 (Space complexity)

• 알고리즘이 필요로한 메모리 용량의 크기
• 컴퓨터가 발전되며 많이 사용되지는 않는다.

 

복잡도 표현

1. 최악 경우 분석 (Worst case analysis)
2. 평균 경우 분석 (Average case analysis)
3. 최선 경우 분석 (Best case analysis)

- 일반적으로 최악 경우를 복잡도로 사용한다. '어떤 값을 주더라도 이 이상 넘지 않는다'라는 이유이다.

- 평균 경우는 입력 값의 균등한 분포를 가정할때의 성능을 분석하는데 사용된다.

- 최선 경우 분석은 최적 알고리즘을 고안하는데 참고 되기는 하지만 자주 사용되지 않는다.

 

 

알고리즘 복잡도는 더 복잡하기 때문에 다음 챕터에서 더 구체적으로 알아보자.