[알고리즘]알고리즘(Algorithm)이란?

알고리즘(Algorithm)이란?

 

알고리즘은 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법을 말한다.

1. 주로 컴퓨터 용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법
2. 어떠한 문제를 해결하기 위한 절차

 

알고리즘 표현법

 

• 슈도 코드

 

슈도 코드는 특정 프로그래밍 언어의 문법을 따라 쓰인 것이 아니라, 일반적인 언어로 코드를 흉내 내어 알고리즘을 써 놓은 코드이다.

의사 코드로 흉내만 내는 코드이기 때문에 실제적은 프로그래밍 언어로 작성된 코드처럼 컴퓨터에서 실행할 수 없다.

특정 언어로 프로그램을 작성하기 전에 알고리즘의 모델을 대략적으로 모델링하는 데에 쓰인다.

 

• 순서도

 

 

순서도는 프로그램이나 작업의 진행 흐름을 순서에 따라 여러 가지 기호나 문자로 나타낸 도표이다.

흐름도, 프로그램의 논리적인 흐름, 데이터의 처리 과정을 표현하는 데 사용한다.

프로그램을 작성하기 전에 프로그램의 전체적인 흐름과 과정 파악을 위해 필수적으로 거쳐야 되는 작업이다.

 

 

 

 

알고리즘의 성능 분석

 

무엇이 좋은 알고리즘인가?

1. 정확성 : 얼마나 정확하게 동작하는가?
2. 작업량 : 얼마나 적은 연산으로 원하는 결과를 얻어내는가?
3. 메모리 사용량 : 얼마나 적은 메모리를 사용하는가?
4. 단순성 : 얼마나 단순한가?
5. 최적성 : 더 이상 개선할 여지 없이 최적화되었는가?

 

알고리즘의 성능 분석 필요성

- 많은 문제에서 성능 분석의 기준으로 알고리즘의 작업량을 비교한다.

예시) 1부터 100까지의 합을 구하는 알고리즘 비교

 

시간 복잡도(Time Complexity)

- 실제 걸리는 시간을 측정 (프로그램 실행 환경에 따라 달라질 수 있음)

- 실행되는 명령문의 개수를 계산

 

빅-오(O) 표기법

- 시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시

- 계수(confficient)는 생략하여 표시

빅-오 표기법 예

요소 수가 증가함에 따라 알고리즘의 시간복잡도는 각기 달라진다.

프로그램을 실제로 실행시키기 전에 시간 복잡도의 개념을 통해 예측, 비교가 가능하다.