이번 주는 휴가중입니다만 애기들을 보느라 방콕하고 있습니다. 정말 쌍둥이 보려니 인터넷 들어와 새글은 물론 답글 달 시간도 없네요.
얼른 휴가 끝나고 회사 나가서 좀 쉬고 싶군요. :-)
이제 7개월째 접어든 저희 집 둥이들이 궁금하신 분들은 가족 홈페이지로 놀러오세요~ ;-)
얼른 휴가 끝나고 회사 나가서 좀 쉬고 싶군요. :-)
이제 7개월째 접어든 저희 집 둥이들이 궁금하신 분들은 가족 홈페이지로 놀러오세요~ ;-)
벌써 어제 말한 내일이 되었는데 답을 주신 분이 아무도 없어서 좀 뻘쭘하네요. :-P 그리고 어제 문제에 O(1)이라고 적었는데 엄밀히 얘기하자면 O(log 10 n)이라고 적었어야 했네요. 죄송합니다. ... 문제를 잠시 생각해보면 1~n까지의 수들 중 1의 개수를 얻기 위해서는 해당 숫자 n의 각 자리의 1의 개수가 모두 몇개나 될지를 구해서 더하면 된다는 사실을 알 수 있습니다. 예를 들어 13이라는 수를 생각해 보면 1~13까지의 수에서 1의 자리에는 1이 모두 몇개나 되는지와 10의 자리에는 모두 몇개나 되는지를 구해 이 값을 더하면 됩니다. 먼저 1의 자리를 생각해 보면 1, 11의 두 개가 있으며 10의 자리의 경우, 10, 11, 12, 13의 네 개가 있습니다. 따라서 2+4=6이라는 값을 구할 수 있습니다. 이번엔 234라는 수에서 10의 자리를 예로 들어 살펴 보겠습니다. 1~234라는 수들 중 10의 자리에 1이 들어가는 수는 10, 11, ..., 19, 110, 111, ... 119, 210, 211, ..., 219들로 모두 30개가 있음을 알 수 있습니다. 이 규칙들을 보면 해당 자리수의 1의 개수를 구하는 공식을 만들 수 있습니다. 234의 10의 자리에 해당하는 1의 개수는 ((234/100)+1)*10이 됩니다. 여기서 +1은 해당 자리수의 수가 0이 아닌 경우에만 더해집니다. 예를 들어 204라면 ((204/100)+0)*10으로 30개가 아닌 20개가 됩니다. 이런 방식으로 234의 각 자리수의 1의 개수를 구하면 1의 자리에 해당하는 1의 개수는 ((234/10)+1)*1=24개가 되고 100의 자리에 해당하는 개수는 ((234/1000)+1)*100=100이 됩니다. 이들 세 수를 모두 합하면 24+30+100=154개가 됩니다. 한가지 추가로 생각해야 할 점은 제일 큰 자리의 수가 1인 경우 위의 공식이 아닌 다른 공식이 필요하다는 점입니다. 예를 들어 123에서 100의 자리에 해당하는 1의 개수는 ((123/1...
안녕하세요~. 이렇게 우연히 원구형 블로그까지 오게되다니..^^*
ReplyDelete황이구먼... 윤서도 잘 크는거 가끔 본다. 여긴 몇달전에 시작한 사이트고 가족 홈페이지는 위에 있는 링크!! ㅋㅋ
ReplyDelete윤서 동생도 부탁하마~ :-)
으악 귀여워요 T_T
ReplyDelete부럽다는... ;ㅁ;