이광근, <컴퓨터 과학이 여는 세계>, 인사이트, 2015-(4)

정말 오래 읽는다.

바뻐서 못 읽고 있는 것이지 책이 재미 없는 게 아니다.

 

알고리즘과 소프트웨어

 

알고리즘은 컴퓨터가 따라할 문제풀이법이다.

자동으로 돌릴 수 있는 혹은

기계적으로 자동화된 문제풀이법.

 

복잡도란 알고리즘 실행시 드는 비용. 

시간이나 메모를 말한다.

사람들은 알고리즘의 비용을 더 줄이기 위해

노력해왔다.

 

당연히 사람들은 아주 빠르고(시간)

가볍게(메모리) 일을 마치는 알고리즘을 원한다.

 

나의 생각

개발자들은 현실적으로 내가 만든 알고리즘이 더 싸고 빨라질 방안은 있는지 아니면 더 좋기는 불가능한지, 결국 컴퓨터가 현실적인 비용으로 해결할 수 있는 문제의 경계를 잘 판단해야 한다.

 

알고리즘의 예

패스워드 해킹하기. 초보 해커들의 방법은 모조리 흝기다.

십진수 4자리 수가 패스워드라고 하면 

10의 4승 만큼 시도해야 한다.

이 방법은 비현실적인 시간이 소요된다.

패스워드 자릿수가 18개만 되어도 일초에 하나씩

흝는 다면 우주의 나이만큼 걸려도 패스워드 맞추지 못한다.

 

알고리즘의 비용

알고리즘 복잡도 종류 구분하는 표기법.

big-O 표기법(오! 흥미롭군, 가끔 보던 녀석이다)

 

입력의 크기 n

계산 비용 입력이 커지면 결국

어떤 함수 f(n)의 상수곱을 넘지 않으면

O(f(n))이라고 쓴다.

 

더 자세히 살펴보니

 

입력 크기가 1 --> 10이 되면 비용이 O(n)인 경우는 10배 커지지만

비용이 O(n2)인 경우는 100배가 커진다.

O(2n)인 경우는 1000배 커진다.

실행비용에 따른 복잡도 증가

p클래스 문제 - 다항의 비용을 함수를 가지는 문제

일반적으로 알고리즘 실행비용이 입력크기(n)에 대해 

상수승 가지면 nk를 가지면 현실적이라고 본다.

 

np(non-deterministic polynomial) 문제들

우리가 관심있는 컴퓨터로 풀 수 있는 가능성이 반반인

경계 가까이에 있는 문제들

 

이 부분엥서 더욱 흥미로운 점은

np문제는 우리 주변에 흔히 나타나는 문제들이라는 것이다.

 

@ 주어진 지도 위의 모든 도시를 한 번씩만 방문하는 경로가 있을까?

해밀턴 경로이다.

 

방문할 도시 수 n. 모두 한 번씩 방문하는 경로의 후보들은

최대 n! = n * (n - 1) * .... * 1만큼이다.

다항시간에 푸는 알고리즘은 아직 없다.

 

@ 주어진 예산으로 주어진 지도의 도시들을 다 방문하고 돌아올 수 있을까?

@ 주어진 부울식이 참이 되게 할 수 있을까?

@ 주어진 자연수를 인수분해하라.

 

이 문제들은 모두 np클래스 문제다.

정확한 알고리즘이(해법)이 없고 모든 경우의 수를 살피고 그 중에서

가장 적은 비용으로 목적을 이루는 방법을 찾아야 한다.

 

알고리즘의 복잡도를 역발상으로 생각한 사람이 있다. 

마뉴엘 블럼.

암호화된 메세지를 도청한 사람이 암호를 풀려면

이런 np문제를 풀어야 하게끔 만들었다.

 

알고리즘의 요구 조건의 핵심은 '모든 입력'과 '정확한 답'이다.

 

난 컴퓨터에서 모든 입력에 대해 정확한 값만을 도출한다고 생각했는데

저자는 흥미롭게도 정답을 도출하지 말고

힘을 조금 빼고 느슨하게 하고 적당한 답으로 가는 건 어떠냐고 한다.

 

직관을 이용해서 로직을 짠다.

예를 들어 주어진 예산으로 지도 위 도시들 다 방문하는 경우.

원래는 모든 경우의 수를 다 구해서 각 경우의 수에서 가장 적은 비용의 경우를

도출해야 한다.

그러나 느슨한 출력(답)에는 가장 저렴한 여행을 위해서

현재 도시에서 다음 도시를 선택할 때 항상 가장 가까운 도시를 선택하는 것이다.

 

알고리즘도 통밥 굴린다. ㅎ