왜 알고리즘을 배워야 하는가?
-입사 시험에서 코딩 테스트롤 보니까
디버깅과 코딩속도, 성능 + 정확성을 잘 알고 있고, 얼마나 최적화 및 활용하는지를 파악하기 위해서 코딩 테스트를 실행함. +지식 테스트
알고리즘을 아는 것은 yes or no가 아니며, 단계적으로 올라가는 것임.
-다른 사람이 짠 프로그램을 가져다 쓰더라도 이해하고 써야하기 때문
알고리즘을 파악하지 못하면 버그가 발생했을 때 고치지 못하며, 기능을 추가하고 싶어도 불가능함 -> 유지보수 불가. 굉장히 큰 문제이며 사실상 죽은 프로그램이나 다름 없음.
-새로운 일을 해야하기 때문
별거 아닌 일을 하더라도 흘러가는 흐름을 정확히 명시하지 않으면 생각치도 못한 문제에 직면할 수 있음
많은 이유들이 있지만...
홀팅 문제(The HALTING Problem)
문제 : 프로그램 M과 입력 X가 있을 때, M에 입력 X를 주고 수행시키면 종료할 것인가?
M(X) : 프로그램 M에 입력 X를 주고 실행시킨 상태
- M(X)는 종료하거나, 종료하지 않음.
- M(X)의 출력은 Yes거나 No임.
- M(X)의 출력은 0101010111000....
컴파일러가 에러를 찾아주듯이, 프로그램이 멈추지 않는 것을 알려주면 편하지 않을까? 이런 기능을 만들 수 있을까? -> 주화입마
문제의 재정의 : 어떤 프로그램이 종료하지 않는지를 수행시키기 "전에" 알 수 있는가?
- M(X)를 실행해서 종료되었음 -> M(X)는 종료함
- 그러나 M(X)를 실행해서 종료되지 않으면 "언젠가는" 종료된다는 것을 알 수 없음
- M(X)가 종료하는 알고리즘일때, 종료하기 전 까지는 그 상태를 알 수 없음
엥? 그냥 일정 시간이 지날 때까지 종료하지 않으면 M(X)는 종료하지 않는다고 하면 되는거 아님? "잘 따지면" 되는거잖아.
홀팅 문제의 증명
가정 : 모든 프로그램 M과 M에 대한 모든 입력 X에 대해서 M(X)를 실행하면 종료할지 영원히 계속될지 판단할 수 있는 프로그램 D가 있다고 가정함.
- D는 Yes/No만을 대답하는 프로그램
- D는 항상 종료함
- D(M,X)를 실행하면 Yes/No 중 하나를 출력하고 종료함
프로그램 D가 있으면 D를 이용해서 다음 것들을 만들 수 있음
프로그램 D'
- M(X)가 멈추면 D'(M,X)는 멈추지 않음
- M(X)가 멈추지 않으면 D'(M,X)는 멈춤
- D(M,X)가 No면, D'(M,X)는 멈춤 (M(X)가 멈추기 때문)
- D(M,X)가 Yes면, D'(M,X)는 멈추지 않음 (M(X)가 멈추지 않기 때문)
프로그램 S
- M(M)이 멈추는 경우 S(M)은 멈추지 않음
- M(M)이 멈추지 않는 경우 S(M)은 멈춤
- 자신을 수행하는 것. 다시 말하면 자신을 수행해서 멈추는지를 결과로 출력
- S가 M을 입력으로 받으면, D'(M,M)을 돌리기만 하면 됨. S(M) = D'(M,M)
- M은 프로그램이지만, 프로그램은 문자열들의 조합이므로, D'의 입력으로 줄 수 있고 또한 M의 입력으로도 줄 수 있음
만약 S(S)를 수행하면?
-S(S)가 멈추면 S(S)는 멈추지 않음
-S(S)가 멈추지 않으면 S(S)는 멈춤
????????????????????????????????
무언가 잘못되었다...
귀류법에 따라서
- 모든 프로그램 M과 M에 대한 모든 입력 X에 대해서 M(X)를 실행하면 종료할지 영원히 계속될지 판단할 수 있는 프로그램 D는 없음.
그러므로 프로그램 M과 입력 X가 있을 때, M에 입력 X를 주고 수행시키면 종료할 것인가?인 홀팅 문제는 "풀 수 없음"
우리가 알 수 있는 것
Hacking을 막아 보자
프로그램 M과 입력 X가 있을 때, M에 입력 X를 주고 수행시키면 종료할 것인가?
프로그램 M는 안 멈추는 프로그램일 때, 입력 X가 M을 종료시키는 지를 수행하기 전에 알 수 있는가? 홀팅 문제이므로 답은 "불가능하다". 이것이 해킹을 막을 수 없는 가장 큰 이유임.
그렇다고 손 놓을 수는 없다. 우리가 공부하는 이유는 예상치 못한 상황들을 조기 발견하고 유지보수하는 것.
우리가 모든 문제들을 막을 순 없지만, 알고리즘을 공부하면 문제들을 파악하고 막을 수 있으며 내가 원하는 방향으로 이끌어 갈 수 있음. 그렇기 때문에 알고리즘을 공부하는 것.
