Index . 블로그창고 . Any comments?

구글 입사문제라고 하는데...

1과 양의 정수 n 사이의 모든 정수에 대해 1이 나타나는 빈도함수를 f(n)이라고 하자. 예를 들어 f(13)=6이 된다 (<1>, <1>0, <1><1>, <1>2, <1>3). f(n)=n을 만족하는 첫번째 n은 1이다. 그러면 이 조건을 만족하는 두번째 n의 값은?

프로그램을 짜서 문제를 풀라는 건지 생각만으로 풀라는 건지 모르겠지만 요즘 유행하는 파이썬으로 한 번 짜보자면 다음과 같다.

#!/usr/bin/env python
import math

num_matches = 0
f = 0
n = 1
while num_matches <= 10:
	num_digits = int(math.log10(n)) + 1
	m = n
	for i in range(num_digits):
		a = m % 10
		if a == 1:
			f += 1
		m = (m - a) / 10
	if f == n:
		print "f(%d) = %d" % (n, f)
		num_matches += 1
	n += 1

그 결과는 아래와 같다.

f(1) = 1
f(199981) = 199981
f(199982) = 199982
f(199983) = 199983
f(199984) = 199984
f(199985) = 199985
f(199986) = 199986
f(199987) = 199987
f(199988) = 199988
f(199989) = 199989

정답은 199981이 되겠다.

blog_2007-11-09/fn.png

역시 칠판에다 푸는 문제였다.

  1. x자리수까지 답이 없었다.
  2. x+1자리인 n=1999...999에 대해 f(n) < n이면
    1. x자리까지 답이 없었고 n=1999...999까지 f(n) < n이면 1000...000부터 1999...998까지는 f(n) >= n인 수가 있을 수 없다. 맨 첫숫자가 1이기 때문에 n의 증가분보다 f(n)의 증가분이 더 크고 만약 f(n)=n인 숫자가 그 사이에 있었다면 1999...999에서는 이미 f(n) >= n이 되어 있어야 한다.
    2. 1에 의해 x자리수인 m=999...999에 대해서는 f(m) < m이다.
    3. x+1자리인 y000...000부터 y999...999까지 (y는 2부터 9까지) 1의 개수는 y가 1이 아니기 때문에 f(m)과 동일하다.
    4. 따라서 x+1자리 마지막수인 9999...999까지 1의 수는 f(n)+8*f(m) < n+8*m = 9999...991이므로 f(9999...999) < 9999...999이다.
  3. f(19) = 10+1*2 < 19
  4. f(199) = 100+20*2 < 199
  5. f(1999) = 1000+300*2 < 1999
  6. f(19999) = 10000+4000*2 < 19999
  7. f(199999) = 100000+50000*2 = 200000 > 199999
  8. f(199991) = 200000-8 = 199992
  9. f(199990) = 199990
  10. f(199981) = 199990-9 = 199981 정답!
  11. f(199980) = 199979
tag: , , ,
Sun Nov 11 01:28:04 2007 by bs

와! 역시 희대님은 대단하세요. 저는 하나도 모르겟어요 ㅋㅋ. 어느새 파이썬도 쓰고 계시네요.

Wed Nov 14 11:50:24 2007 by Huidae Cho

좀 대중적인 언어를 배워보려고 파이썬을 쓰기 시작했습니다. 위키북을 항상 펼쳐놓고 (screenshots) 되도록이면 파이썬을 써서 일처리를 하려고 노력하고 있습니다. 그런데 range() 함수가 좀 직관적이지 않은 것 같습니다. 헷갈리네요. 사실은 VB를 해야하는데 노트북에 슬랙웨어만 깔려 있어서 여의치 않습니다. 리눅스는 계속 쓰고 계신가요?

Thu Nov 15 20:36:13 2007 by bs

저두 파이썬 랜덤함수 공부할 때 이상했던 기억이 있어요. 그랬던 기억만 있고 다른 기억들은 없습니다. 써먹을 곳을 찾지 못하니까 안쓰게 되고 잊어버리게 되요. 허탈탈. 슬랙웨어 완전히 적응하셨나요? 사실 얼마전에 기기변경을 했습니다. 맥북을 사서 정식으로 MAC OS X를 쓰고 있습니다. 셋팅할 것도 없고 자잘한건 기본프로그램만으로 다 되니까 편하고 좋습니다. 그런데 예전 노트북에 깔아서 쓰던 해킨토시보다 덜 쾌적하게 돌아가는 느낌이 들어서 좀 분합니다. xtem도 약간 버벅거리는거 같구요. 사양도 더 나은데 왜 그런건지 모르겠습니다. 저두 c#이랑 asp때문에 맥북에 윈도우를 깔아볼까 생각중이에요. 슬렉웨어 설치 이후로는 윈도우를 쓰지않으셨나요?

Thu Nov 15 20:51:29 2007 by bs

참. 희대님은 구글 안드로이드 개발대회 참가 안하시나요? 상금이 어마어마 하던데요. mafi를 한번더 울궈먹어도 가능하지 않을까요?

Sat Nov 17 06:06:33 2007 by bs

'울궈먹어도'라는 말이 좀 그러네요. 죄송합니다. 포.팅. 으로 바꿉니다. 악의는 없어요 ㅡㅜ.

Tue Nov 20 11:22:50 2007 by Huidae Cho

사실 울궈 먹은 적이 없죠. ;) 작업을 다시 하면서 셀빅으로 포팅했을 뿐입니다. 안드로이드 깔끔한 플랫폼이네요. 아.. 이런 거에 빠지면 시간 엄청 빼앗깁니다. 유혹하지 마세요. 그런데 mafi 같은 걸로는 어림도 없는 대회 같습니다. 뭔가 유저들이 열광할 만한 어플을 찾고 있는 것 같군요. 아시다시피 저는 그런 어플을 생각할 수도 개발할 수도 없는 실력의 소유자입니다. ㅋㅋ

Tue Nov 20 11:33:36 2007 by Huidae Cho

윈도(별도의 노트북)는 워드작업과 PDA 싱크 때 빼고는 쓸 일이 없습니다. 뭐 딱히 윈도용으로 쓰고 있는 어플이 없어서 가능하겠죠. MS 워드, 엔드노트, 매쓰타입, 파워포인트 정도를 쓰고 있습니다. 제 개인적인 문서작업이나 워드포맷을 강요하지 않는 문서작업에는 LaTeX을 쓰고 있고 한번은 파워포인트조차 LaTeX 기반으로 바꾸려고 했습니다. 그런데 다이나믹한 프리젠테이션을 만드는데는 파워포인트만한 것이 없어서 그냥 쓰고 있습니다.

슬랙웨어 설치 후 잠시 동안 깔끔한 인터페이스 때문에 KDE를 사용했었는데 왠지 모를 OS 컨트롤에 대한 박탈감 때문에 다시 Fluxbox로 왔습니다. 어제는 VB.NET을 한 번 공부해 보자고 Mono에 있는 vbnc 컴파일러를 어떻게 사용하나 인터넷을 뒤져서 GUI 빌더는 없지만 "손코딩"으로 하는 방법을 알아 놨습니다. 무지하게 삽질이네요. 다시 .NET의 세계로...

블로그창고 . 댓글문법

All the works in this site except software and copyrighted materials by others (e.g., 문학) are licensed under a Creative Commons License. 소프트웨어 및 문학과 같이 다른 이에게 저작권이 있는 작품을 제외하고 모두 크리에이티브 커먼즈 라이센스를 따른다.
Fri Feb 8 09:44:38 2019 . XHTML . CSS (lightbox.css is not part of Uniqki. ;-) . Powered by Uniqki!
refresh . edit . loginout . index