(틀린 부분이 있다면 지적 감사하겠습니다.) 우리는 알고리즘을 얼마나 제대로 이해하고 쓸까? 알고리즘을 정확히 이해하고 쓰는것과 그렇지 않은 것에는 많은 차이가 있다. 오늘은 재귀의 예를 소개하고, 그 정확성을 증명해보고자 한다. 1. 합 구하기 1부터 x 까지의 합을 구하는 프로그램을 작성해보자. unsigned int sum(unsigned int x){ int i, s; s = 0; for(i=1;i8... 이런식으로 가다가 0이 되고, 0을 리턴하면 다시 쭉~~~ 올라와 1부터 10까지 더해진다고 지금껏 이해했다. sum(3) -> sum(2) -> sum(1) -> sum(0) 6 3 1 0 리턴 물론 틀린말은 아니다! 당연한 소리이고, 이런식으로 생각하는 게 이상하지 않다. 그렇지만 이렇게 하..

오늘을 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): 알고리즘을 수행하는데 걸리는 시간이 입력값에 비례하는..