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

1. 알고리즘은 문제 해결 과정을 묘사하는 것

- 알고리즘이란 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것.

- 알고리즘을 설계하기 위해서는 우선 해야 할 작업을 명확하게 명시해야 함.

- 설계하려는 알고리즘이 "무엇을" 하는지는 입력과 출력으로 명시할 수 있음.

 

ex) 학생 100명의 시험 점수를 입력으로 받아 최고점을 출력하는 작업을 함.

입력 : 학생 100명의 시험 점수 ( x[0],x[1], ~ x[98],x[99]의 값 )

출력 : 입력된 100개의 점수 중 최댓값 ( x[0],x[1], ~ x[98],x[99]의 값 중 최댓값 )

알고리즘의 대략적인 형태

maxScore(x[],n)
{
    ①x[0~n]의 값을 차례대로 보면서 최댓값을 계산함;
    return 최댓값;
}

- 이런 쉬운 문제도 있지만 어려운 문제뿐만아니라 현존하는 어떤 알고리즘으로도 현실적인 시간 내에 최적의 해를 보장할 수 없는 문제도 있음.

ex)

입력 : 어떤 영업사원이 방문해야 할 고객 n명의 위치

출력 : 이 고객들을 모두 방문하고 돌아오는 가장 짧은 경로

- 이렇게 알고리즘이 다루는 문제는 다양하고 난이도의 폭이 넓음. 이런 문제들에 대한 해결 과정을 모호하지 않게 묘사하는 것이 알고리즘임.

 

- 알고리즘은 명확하고 효율적으로 설계해야 함.

- 명확하다는 것 : 모호하지 않고 이해하기 쉽다는 뜻.

- 특정 프로그래밍 언어로 변환하는 데 어렵지 않을 정도가 되어야 함.

- 하지만 특정한 프로그래밍 언어 문법에 맞추라는 것은 아님. 이는 오히려 명황성을 해칠 수 있음.

- 충분히 큰 입력에서는 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있음.

 

2. 알고리즘은 생각하는 방법을 훈련하는 것

- 어떤 문제를 해결하기 위해 중요한 것과 중요하지 않은 것을 구분할 수 있고, 문제도 단순화해서 볼 수 있음.

- 다른 사람의 아이디어 효율성을 판단할 수 있게 되고, 자신의 알고리즘이 최악의 경우나 평균적인 경우에 수행시간이 얼마나 소요되는지 판단할 수 있음.

 

3. 알고리즘은 자료구조의 확장

- 알고리즘의 선수 과목은 자료구조.

- 자료구조는 알고리즘을 위한 기본적인 도구임.