오늘을 Halting Problem 이라는 유명한 판정 문제를 소개해 보겠습니다. Alan Turing의 증명과 내 나름의 이해한 것을 바탕으로 풀이를 써보았습니다. The Halting Problem - 프로그램 M 과 입력 X 가 있을 때 M에 입력 X를 주고 수행시키면 M은 종료할 것인가? 이 프로그램 M이 계산을 끝나고 멈출지, 아니면 영원히 멈추지 않을지 판정하라. Halting Problem 이라는 유명한 문제인데 이 문제를 처음 봤을 때는 이게 뭐지...? 싶었다. 프로그램 M이 멈추냐, 안 멈추냐 뭐 이런 뜻 같은데.... 상황에 따라 멈출 수도 있고 안 멈출수도 있지 않나? 라고 생각했다. "상황에 따라서" 말이다. 당연한 얘기일 것이다. 프로그램을 어떻게 짜느냐에 따라 멈출 수도 있..

시간복잡도 시간복잡도란 어떤 알고리즘을 수행하는데 걸리는 시간을 설명하는 계산적인 복잡도를 의미합니다. 컴퓨터 공학에서 시간복잡도를 나타낼 때 빅 오 표기법을 사용하는데, 입력값 N이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기방법입니다. 빅오 표기법의 종류 1. O(1): 입력값의 크기와 상관없이 일정한 실행시간을 보장. 최고의 알고리즘이라 할 수 있다. 2. O(log n) : 로그 함수를 생각해보자. n이 무한히 커져도 값의 차이는 매우 작다고 볼 수 있다. 아주 효율적인 알고리즘. 이진 탐색(Binary-Search)의 경우가 이에 해당한다. 이진탐색 알고리즘은 정렬된 배열 또는 리스트에서 고속으로 탐색할 때 사용된다. 3. O(n): 알고리즘을 수행하는데 걸리는 시간이 입력값에 비례하는..