드럼치는 프로그래머

1의 횟수 양수 n에 대해서 1과 n 사이에 1이 나오는 횟수를 나타내는 함수를 f(n)이라고 한다. 예를 들어 f(13)=6이다. f(n)=n이 되는 첫번째 양수는 1이다. ex) 13 > 1, 10, 11, 12, 13 두번째 양수는 무엇인가? 출처 : http://kaisyu.blogspot.com/2007/02/google_14.html 날짜를 보니 작년 문제인듯 싶다. 1의 횟수 1에서 부터 n까지 모든 숫자를 각 자릿수 숫자를 한자리 숫자들의 리스트로 나누어서 1의 갯수를 구한뒤 이를 모두 합치면 간단히 풀 수 있다. 간단히 풀수 있는 문제 이지만 풀다보니 n의 복잡도가 아닌 상수 복잡도로 0에서 양의 정수 n까지의 1의 갯수를 발견할 수 있음을 깨달았다. 알고리즘을 간단히 설명하자면 각 자릿..

이 문제는 마이크로소프트 사의 입사 문제라고 하더군요. 언제적 문제 인지는 모르겠지만, 인터넷에 돌아다녀도 안나오길래 가물가물한 기억으로 작성합니다. (혹시 이 문제를 아시는 분이 보셨다면, 그래서 틀린 부분이 있다면 알려주시면 감사하겠습니다) *참고로 이 문제를 풀었다고 해서 마이크로소프트 사에 입사 할 수 있는 것이 아니고, 이 문제를 풀고 프로그램으로 작성해야 한다고 들었습니다(들은거라 정확하지는 않아요). 그럼, 문제 입니다. 어떤 저주받은 섬이 하나 있습니다. 이 섬 안에는 20명의 사람이 있고 이들은 평소엔 모두 멀쩡합니다. 그러나 어느날 눈이 빨갛게 변한다면, 그리고 그것을 본인이 알게 된다면(보든 듣든) 그날 밤 12시가 됐을때 사망하게 됩니다. 이 섬안에는 거울이든 뭐든, 비추는 물건은 ..