[Chapter 1] 쉽게 배우는 알고리즘[알고리즘이란?]

• 알고리즘이란 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것.
• 알고리즘을 설계하기 위해서는 우선 해야 할 작업을 명확하게 명시해야 한다.
• 설계하려는 알고리즘이 "무엇을"하는지 입력과 출력으로 명시할 수 있다.

ex) 학생 100명의 시험 점소를 입력으로 받아 최고점을 출력하는 작업을 할 때 입출력 표현

• 입력 : 100개의 점수
• 출력 : 입력된 100개의 점수 중 최댓값

입출력의 구체화된 표현

• 입력 : 100개의 변수 x[1], ... x[100]의 값
• 출력 : x[1], ..., x[100] 중 최댓값

이 입출력을 요구하는 알고리즘의 대략 형태

maxScore(x[], n)
{
x[1...n]의 값을 차례대로 보면서 최댓값을 계산한다. 	//1
return 찾은 최대값;
}

위에 작성한 서술적 표현 1을 필요한 수준까지 더 구체화할 수 있다. 실제 알고리즘을 만들 때는 점진적으로 구체화하는 과정을 거쳐 모호함이 없는 수준에서 마무리한다. 함수나 서브루틴도 구체화 과정에서 도입되는 것이다.

 

초보적인 알고리즘을 사용해 해결할 수 있는 예시

• 입력 : 서울시 지하철 노선도, 출발역, 도착역
• 출력 : 출발역에서 도착역까지 가는 최단 경로

더 수준 높은 알고리즘으로 해결할 수 있는 예시

• 입력 : n개의 행렬과 각 행렬의 차원
• 출력 : 이 행렬들을 모두 곱하기 위해 가장 빨리 끝나는 곱셈 순서

현존하는 어떤 알고리즘으로도 현실적인 시간 내에 최적의 해를 보장할 수 없는 예시

• 입력 : 어떤 영업사원이 방문해야 할 고객 n명의 위치
• 출력 : 이 고객들을 모두 방문하고 돌아오는 가장 짧은 경로

알고리즘이 다루는 문제는 난이도의 폭이 넓다.

이런 문제들에 대한 해결 과정을 모호하지 않게 묘사하는 것이 알고리즘이다.

 

• 알고리즘은 명확하고 효율적으로 설계해야 한다.
• 알고리즘이 명확하다는 것은 모호하지 않고 이해하기 쉽다는 뜻이다.
• 특정 프로그래밍 언어로 변환하는데 어렵지 않을 정도가 되어야 한다. (특정한 프로그래밍 언어 문법에 맞추라는 것은 아니다.) - >명확성을 해칠 수 있다.(명확하다는 것과 자세하다는 것을 혼동하면 안된다.)
• 명확하게 표현한다고 지나친 세부 사항을 기호로 구구절절 기술하는 것은 오히려 알고리즘의 명확성을 떨어뜨린다. 이 명확성이라는 것은 알고리즘을 읽는 사람의 수준도 고려해야 한다. ("모호하지 않다"는 것은 알고리즘을 읽는 독자의 수준에 따라 상대적이다.)
• 알고리즘은 가능하면 효율적이어야 한다. 알고리즘은 궁극적으로 컴퓨터로 구현되므로, 컴퓨터의 빠른 처리 능력을 감안하면 아무리 복잡한 알고리즘도 입력의 크기가 작으면 금방 끝나버린다. 그러므로 관심의 대상이 되는 것은 입력의 크기가 충분히 클 때다. 충분히 큰 입력에서는 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있다. 같은 문제를 해결하는데 100년이 걸리는 알고리즘도 있고 1분이 걸리는 알고리즘도 있을 수 있다.
• 입력이 충분히 큰 경우에 대한 분석을 점근적 분석(Asymptotic Analysis)이라고 하는데, 고등학교 수학의  와 비슷하다.

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

• 어떤 문제를 해결하기 위해 중요한 것과 중요하지 않은 것을 구분할 수 있고, 문제도 단순화 해서 볼 수 있다. 다른 사람의 아이디어 효율성을 판단할 수 있게 되고, 자신의 알고리즘이 최악의 경우나 평균적인 경우에 수행 시간이 얼마나 소요되는지 판단할 수 있다.
• 어떤 문제에 대한 알고리즘 자체는 하나의 문제에 대한 해결책을 주지만, 그 속에 들어있는 생각의 방법은 미래에 다른 문제를 해결할 때 사용하는 사고의 기본적인 빌딩블록을 제공한다.

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

• 알고리즘의 선수 과목은 자료구조이다. 적어도 한 개 이상의 프로그래밍 언어로 초급 수준 이상의 프로그래밍을 해본 경험이 필요하다.
• 자료구조는 생각의 전개를 위해 필요한 기본적인 도구다.
• 건물을 지을 때 사용하는 기본적인 건축 재료나 모듈 같은 것과 유사하고, 자동차 제작에 사용되는 기본 부품 같은 것이다.
• 자료구조를 모르면 자동차를 만들 때 헤드라이트 모듈이 있는 것을 몰라 선으로 어딘가 조잡하게 전등을 부착하는 것과 같은 일이 벌어질 수 있다. 
• 빌딩을 지을 때 철골이라는 재료가 있다는 것을 모르면 벽돌로 쌓거나 콘크리트를 부어 만들 수 밖에 없다. 심지어 벽돌과 콘크리트라는 재료를 모르면 더 유치한 건물이 될 것이다. 따라서 알고리즘이라는 과목을 공부할 때는 기본적인 자료구조 이해는 갖추었다는 가정하에 시작한다. 

---

Reference

쉽게 배우는 알고리즘