Part 1. 기초 [35 ~ 180]
Chater 1. 알고리즘의 역할 [35 ~ 46]
1.1. 알고리즘 [35 ~ 41]
· 알고리즘
어떤 값이나 값의 집합을 입력(input)받아 또 다른 값이나 값의 집합을 출력(output)하는 잘 정의된 계산 과정
· 계산 문제(computational problem) 정의
입력과 출력의 관계를 구현할 수 있는 계산 과정을 서술 by알고리즘
· "타당한" 알고리즘
알고리즘이 모든 입력 사례에 대해 항상 올바른 출력을 내고 종료할 경우 이 알고리즘은 타당하다고 하며, 이 알고리즘이 "주어진 계산 문제를 푼다"고 말함
▷ 어떤 문제를 알고리즘으로 푸는가?
겁나 많음. 책에서 나열한 예시조차 극히 일부에 불과함.
현실에서 대량의 데이터를 관리하고 가공해야하는 문제, 희소 자원을 가장 효과적으로 할당하는 문제 등의 현실적인 문제 해결을 위해 기본적인 문제(최단 경로 문제, 위상 정렬 문제, 클러스터링 알고리즘, 허프만 코딩 등)를 책에서 다룰 것이라고 함.
▷ 자료구조(data structure)
자료를 편리하게 접근하고 변경하기 위해 자료를 저장하거나 조직하는 방법을 말함.
▷ 알고리즘 기법
알고리즘을 스스로 개발하고 그것이 타당한 해를 제시하는지 증명하며 효율성(알고리즘의 문제해결 속도 = 알고리즘이 결과를 내는데 걸리는 시간이 빠를수록 효율성이 높음)을 이해할 수 있도록 알고리즘을 설계하고 분석하는 기법들을 이 책에서 앞으로 배울 것이다란 내용
▷ 어려운 문제들
NP-완비로 알려진 문제는 최적해를 찾는 효율적인 알고리즘도 안 밝혀졌지만 그런 알고리즘이 존재할 수 없음도 증명되지 않아서 NP-완비 문제가 증명됐을 때 효율적인 알고리즘 개발에 엄청난 변화가 생길 수 있음
▷ 병렬성
컴퓨터 칩은 시간당 계산 성능을 늘리기 위해 단 하나가 아닌 여러 계산을 처리할 수 있도록 여러 코어(core)를 가지도록 설계되어, 여러 컴퓨터가 나란히 놓인 것처럼 작동할 수 있는 병렬성을 가져서 알고리즘 설계 시에도 이 병렬성을 염두에 두어야 한다.
1.2 기술로서의 알고리즘[41 ~ 46]
컴퓨터가 무한히 빠르고 메모리 비용이 들지 않는다고 생각해도 알고리즘을 연구할 필요가 있다.
∵ 알고리즘이 타당한 답을 출력하면서 종료된다는 것을 확신하고 싶어서라도 알고리즘을 학습할 필요 있음
심지어, (최소한 아직까지는) 현실적으로 컴퓨터가 무한히 빠를 수 없다.
계산 시간은 한정되었고, 메모리 공간도 마찬가지다.
자원을 효율적을 사용하기 위해 시간 및 공간 측면에서 효율적인 알고리즘이 필요함.
▷ 효율성
동일한 문제를 해결하기 위한 서로 다른 두 알고리즘은 효율성 면에서 극적으로 다를 수 있다.
ex) 극적으로 다름을 보여주기 위한 극적인 예시
빠른 하드웨어 컴퓨터로 뛰어난 프로그래머가 삽입 정렬로 1000만개의 숫자를 정렬하는데 걸리는 시간 : 5.5시간
느린 하드웨어 컴퓨터로 평범한 프로그래머가 병합 정렬로 1000만개의 숫자를 정렬하는데 걸리는 시간 : 20분이하
▷ 알고리즘과 다른 기술들
알고리즘도 하드웨어, 네트워킹, GUI(Graphic User Interface) 등, 시스템의 영향을 주는 하나의 기술이다.