Tags:
두가지 문제를 풀어보세요. 단 답알던 사람은 답달지 마세요~~.
(특히 나랑 스터디 했던 친구들이 답하면 무효!)
이 문제를 잘 모르는 사람이 있어서 올려봅니다.
제가 그보다 크다, 그보다 작다, 맞췄다 세가지의 답만 한다고 할 때 다음 두 문제를 풀어보세요. (예: 제가 생각한 수가 7인데 당신이 8 이라고 말하면 나는 그보다 작다고 답합니다. 당신이 3이라고 했다면 그보다 크다고 답합니다. 당신이 7이라고 했다면 맞췄다라고 답합니다.)
1. 제가 1~100까지의 수를 생각했습니다. 가장 효율적으로 맞출 수 있는 방법은?
2. 제가 1~무한대까지의 수를 생각했습니다. 가장 효율적으로 맞출 수 있는 방법은?
1번답: 50-> 크다고하면 75, 작다고 하면 25. 이런식으로 절반씩 나눠가며 찾음.
2번답: 1,2,4,8,16,32,64,128,256,… 이런식으로 2의 n승으로 답을 부름.
(This is the reason why log functions are so widely used in computer science.)
2번답의 다른해: 1, 2^1, 2^2^1, 2^2^2^1, 2^2^2^2^1 이런식으로 계속 An=2^An-1 식으로 수를 부름. (애커만 함수)
하지만, 실생활에서 1~무한대보다는 1~그냥 큰 수사이의 값을 맞추는 경우가 더 많으므로 이처럼 너무 급속하게 커지는 함수는 불필요함. (이라는게 저의 생각임..)
왜 2인가: bit가 0과 1만 가능하므로.
그래도 3이라고 하면 3^n 이 2^n보다 더 빨리커지지않을까: Big-oh 에서보면 똑같다. (결국은 커지는 속도의 비율에 대해서 관심이 있을 뿐.)
난데없이 왜 이런 문제를 내었나: 누군가 내게 어째서 컴퓨터에서는 log 함수가 그렇게 많이 쓰이냐고 물어봐서.
Leave a Reply