모두의 알고리즘 : MISSION 1(머신러닝/영지식증명/유전알고리즘)

모두의 알고리즘 with 자바스크립트에 담긴 내용을 기초로 하여 적는 글.

<모두의 알고리즘  with 자바스크립트 : MISSION 1>

 

 '알고리즘' : 문제를 풀기 위한 절차 자체, 실제로 기원전 3세기경에 쓰인 자료가 있을 정도로 오래된 정의다. 어원은 8-9세기에 활약한 알 콰리즘이라는 수학자의 이름에서 따왔다고 한다. 세계는 21세기인 지금도 여전히 알고리즘에 미쳐있는데,, 참으로 신기한 현상이다. 그런 의미로 현대의 요리 레시피도 알고리즘의 하나이지만, 정확하게는 또 알고리즘이 아니다(추후 설명).

 

 우선 기본적인 정의를 정리하면 알고리즘은 '절차'고, 절차를 실행할 수 있는 형태로 구현한 걸 '프로그램'이라고 한다. 요즘 핫한 '프로그래밍'도 이러한 알고리즘을 실행할 수 있는 형태로 만드는 행위를 통칭하는 의미다. 책은 컴퓨터 등장 이전의 알고리즘도 설명해주는데 솔직히 글쎄... 큰 의미 있나 싶어서 포스팅에서는 스킵한다. 흘러 흘러 최초의 컴퓨터인 에니악 등장 이후 기존 계산기 대비 연산 속도가 1,000배 빨라졌다는 사실만 알아둬도 될 것 같다.

 

좌측 이미지는 드라마 <응답하라 1997>에서 보라에게 과외받는 동생 덕선의 모습이다. 보라는 수학이 어려운 덕선에게 깊은 빡침이 느껴지는 목소리로 '걍 이해하려 하지 말고 외워'라고 한다.

알고리즘도 그렇다. 검증된 거니 이해하려하지 말고 외우면 된다. 1+1=2를 의심해본 적이 있는가? 의미를 몰라도 배운 대로 하면 언젠가는 정답에 도달하는 것, 줄곧 설명하고 있는 알고리즘이다.

 

 하지만 21세기에 들어서면서 알고리즘의 사용 형태도 달라진다. 이전보다 더 높은 수준의 알고리즘이 필요하게 된 것이다. 사용 형태는 대표적으로 '머신러닝'과 '영지식 증명', '유전 알고리즘'이 있다. 처음 들었을 때는 저게 무슨 외계어냐 할 정도로 어려운 단어인데 알고 보면 우리가 다 알고 있는 것들이다.

 먼저 비교적 친숙한 개념인 머신러닝은 3차 인공지능 붐에서 주류를 이루고 있는 알고리즘 형태이다. 컴퓨터한테 자료를 주고 학습시키는 방법이다. 너무 유명하니까 이상은 생략.

 영지식 증명은 비트코인에서 사용되는 것이 대표적인 알고리즘 형태로 상대에게 자신의 정보를 넘기지 않고도 내가 그 정보를 알고 있다는 사실을 전달할 수 있다. 내가 코인을 안 하니까 책에 쓰인 개념이 좀 모호하게 이해돼서 추가로 검색해본 결과 영지식 증명의 찰떡 비유라고 불리는 장 자크 키스케다의 <어린이를 위한 영지식 증명>을 찾았다. 이래 봬도 나는 🌈알고리즘 어린이🌈니까 포스팅에도 설명해본다.

1. 철수(분홍)와 영희(파랑), 그리고 끝이 문으로 막힌 동굴이 있다.

2. 둘은 동굴 끝이 문으로 막혀있다는 사실을 알고 있다.

3. 철수는 영희가 못 보게 동굴의 A와 B 통로중 하나를 선택해 들어간다.

4. 영희는 철수가 들어간 통로를 모르는 상태로 철수에게 자신이 말하는 통로로 나오라고 한다. 그리고 해당 과정을 반복한다.

5. 철수가 매번 나오면 영희는 철수에게 동굴 끝 문을 여는 열쇠가 있다고 생각하게 된다.

6. 철수가 굳이 '내안에 열쇠있다' 말하지 않아도 확률적으로 그렇게 판단한다는 것이다.

 

 유전 알고리즘은 생물의 진화과정을 모델로 이상적인 답을 발견하는 알고리즘이다. 부모가 자식에게 유전자를 물려줄 때 60개 이상의 오류가 발생하기 때문에 유전 알고리즘으로는 완벽한 답이 도출되지 않는 경우도 있다. 하지만 최단시간 해결을 돕는 알고리즘이라 유효하다.