Maintenance script: Repair batch-0002 pages from live compare

2026-03-27T00:16:04Z

Repair batch-0002 pages from live compare

← Older revision		Revision as of 00:16, 27 March 2026
Line 2:		Line 2:
	input space 로 볼때 최악의 경우가 1~10^100 일 수 있겠다는 생각을 하면서 뭔가 다른 공식이 있겠다 생각, 피보나치의 closed-form 을 근거로 해결할 방법에 대해 궁리해보다. a,b 구간에 가장 가까울 f(x),f(y)를 각각 구하고, y-x 를 구하면 되리라고 생각. 하지만 3시간동안 고민했는데 잘 안되어서, 그냥 노가다 스러운 방법으로 풀기 시작.		input space 로 볼때 최악의 경우가 1~10^100 일 수 있겠다는 생각을 하면서 뭔가 다른 공식이 있겠다 생각, 피보나치의 closed-form 을 근거로 해결할 방법에 대해 궁리해보다. a,b 구간에 가장 가까울 f(x),f(y)를 각각 구하고, y-x 를 구하면 되리라고 생각. 하지만 3시간동안 고민했는데 잘 안되어서, 그냥 노가다 스러운 방법으로 풀기 시작.
	def fibo(n):		def fibo(n):
	s=[1,2]		s=[1,2]
	if n in [1,2]: return s[n-1]		if n in [1,2]: return s[n-1]

	i=2		i=2
	while True:		while True:
	i+=1		i+=1
	fiboI=s[0]+s[1]		fiboI=s[0]+s[1]
	if n==i: return fiboI		if n==i: return fiboI
	s[0],s[1] = s[1], fiboI		s[0],s[1] = s[1], fiboI

	def howmany(a,b):		def howmany(a,b):
Line 90:		Line 90:
	* 구간 계산과 관련, 'a 와 가장 가까운 fibonacci 값을 구하기' 는 반복문 돌리기 & if 로 비교 말고 다른 방법이 없을까?		* 구간 계산과 관련, 'a 와 가장 가까운 fibonacci 값을 구하기' 는 반복문 돌리기 & if 로 비교 말고 다른 방법이 없을까?
	* bigint 를 지원하는 python 이나 matlab 같은 언어에서는 더 할일이 없는 문제. 내가 공식 궁리하는 동안 옆의 분이 matlab 으로 10분만에 풀어버리다. 흑.		* bigint 를 지원하는 python 이나 matlab 같은 언어에서는 더 할일이 없는 문제. 내가 공식 궁리하는 동안 옆의 분이 matlab 으로 10분만에 풀어버리다. 흑.

imported>Unknown at 05:23, 7 February 2021

2021-02-07T05:23:25Z

New page

== approach ==
input space 로 볼때 최악의 경우가 1~10^100 일 수 있겠다는 생각을 하면서 뭔가 다른 공식이 있겠다 생각, 피보나치의 closed-form 을 근거로 해결할 방법에 대해 궁리해보다. a,b 구간에 가장 가까울 f(x),f(y)를 각각 구하고, y-x 를 구하면 되리라고 생각. 하지만 3시간동안 고민했는데 잘 안되어서, 그냥 노가다 스러운 방법으로 풀기 시작.
def fibo(n):
s=[1,2]
if n in [1,2]: return s[n-1]

i=2
while True:
i+=1
fiboI=s[0]+s[1]
if n==i: return fiboI
s[0],s[1] = s[1], fiboI

def howmany(a,b):
i,count=1,0
while True:
fiboI = fibo(i)
if a < fiboI < b: count+=1
if fiboI > b: return count
i+=1

print howmany(10,100)
print howmany(1234567890,9876543210)
print howmany(1,10**100)

근데, a,b=(1,10^100) 로 해도 1초도 안걸린다. 처음에는 'big integer 를 만들어라!' 라는 문제가 아니라고 생각했는데, 풀고 나니 뭔가 허탈함. 글쌔. 출제자가 원한 답은 big integer emulation 이였을까. 흑..

덤 : 피보나치 closed form
def fiboClosedForm(n):
return int(((1+sqrt(5))**n - (1-sqrt(5))**n) / (2**n * sqrt(5)))

기타 덤 : fibonacci 의 수열 당 자릿수 값.
1:1 2:1 3:1 4:1 5:1 6:2 7:2 8:2 9:2 10:2
11:3 12:3 13:3 14:3 15:3 16:4 17:4 18:4 19:4 20:5
21:5 22:5 23:5 24:5 25:6 26:6 27:6 28:6 29:6 30:7
31:7 32:7 33:7 34:7 35:8 36:8 37:8 38:8 39:9 40:9
41:9 42:9 43:9 44:10 45:10 46:10 47:10 48:10 49:11 50:11
51:11 52:11 53:11 54:12 55:12 56:12 57:12 58:12 59:13 60:13
61:13 62:13 63:14 64:14 65:14 66:14 67:14 68:15 69:15 70:15
71:15 72:15 73:16 74:16 75:16 76:16 77:16 78:17 79:17 80:17
81:17 82:17 83:18 84:18 85:18 86:18 87:19 88:19 89:19 90:19
91:19 92:20 93:20 94:20 95:20 96:20 97:21 98:21 99:21 100:21
101:21 102:22 103:22 104:22 105:22 106:23 107:23 108:23 109:23 110:23
111:24 112:24 113:24 114:24 115:24 116:25 117:25 118:25 119:25 120:25
121:26 122:26 123:26 124:26 125:26 126:27 127:27 128:27 129:27 130:28
131:28 132:28 133:28 134:28 135:29 136:29 137:29 138:29 139:29 140:30
141:30 142:30 143:30 144:30 145:31 146:31 147:31 148:31 149:31 150:32
151:32 152:32 153:32 154:33 155:33 156:33 157:33 158:33 159:34 160:34
161:34 162:34 163:34 164:35 165:35 166:35 167:35 168:35 169:36 170:36
171:36 172:36 173:37 174:37 175:37 176:37 177:37 178:38 179:38 180:38
181:38 182:38 183:39 184:39 185:39 186:39 187:39 188:40 189:40 190:40
191:40 192:40 193:41 194:41 195:41 196:41 197:42 198:42 199:42 200:42
201:42 202:43 203:43 204:43 205:43 206:43 207:44 208:44 209:44 210:44
211:44 212:45 213:45 214:45 215:45 216:46 217:46 218:46 219:46 220:46
221:47 222:47 223:47 224:47 225:47 226:48 227:48 228:48 229:48 230:48
231:49 232:49 233:49 234:49 235:49 236:50 237:50 238:50 239:50 240:51
241:51 242:51 243:51 244:51 245:52 246:52 247:52 248:52 249:52 250:53
251:53 252:53 253:53 254:53 255:54 256:54 257:54 258:54 259:54 260:55
261:55 262:55 263:55 264:56 265:56 266:56 267:56 268:56 269:57 270:57
271:57 272:57 273:57 274:58 275:58 276:58 277:58 278:58 279:59 280:59
281:59 282:59 283:60 284:60 285:60 286:60 287:60 288:61 289:61 290:61
291:61 292:61 293:62 294:62 295:62 296:62 297:62 298:63 299:63 300:63
301:63 302:63 303:64 304:64 305:64 306:64 307:65 308:65 309:65 310:65
311:65 312:66 313:66 314:66 315:66 316:66 317:67 318:67 319:67 320:67
321:67 322:68 323:68 324:68 325:68 326:68 327:69 328:69 329:69 330:69
331:70 332:70 333:70 334:70 335:70 336:71 337:71 338:71 339:71 340:71
341:72 342:72 343:72 344:72 345:72 346:73 347:73 348:73 349:73 350:74
351:74 352:74 353:74 354:74 355:75 356:75 357:75 358:75 359:75 360:76
361:76 362:76 363:76 364:76 365:77 366:77 367:77 368:77 369:77 370:78
371:78 372:78 373:78 374:79 375:79 376:79 377:79 378:79 379:80 380:80
381:80 382:80 383:80 384:81 385:81 386:81 387:81 388:81 389:82 390:82
391:82 392:82 393:82 394:83 395:83 396:83 397:83 398:84 399:84 400:84
401:84 402:84 403:85 404:85 405:85 406:85 407:85 408:86 409:86 410:86
411:86 412:86 413:87 414:87 415:87 416:87 417:88 418:88 419:88 420:88
421:88 422:89 423:89 424:89 425:89 426:89 427:90 428:90 429:90 430:90
431:90 432:91 433:91 434:91 435:91 436:91 437:92 438:92 439:92 440:92
441:93 442:93 443:93 444:93 445:93 446:94 447:94 448:94 449:94 450:94
451:95 452:95 453:95 454:95 455:95 456:96 457:96 458:96 459:96 460:96
461:97 462:97 463:97 464:97 465:98 466:98 467:98 468:98 469:98 470:99
471:99 472:99 473:99 474:99 475:100 476:100 477:100 478:100 479:100 480:101
481:101 482:101 483:101 484:102 485:102 486:102 487:102 488:102 489:103 490:103
491:103 492:103 493:103 494:104 495:104 496:104 497:104 498:104 499:105

피보나치 수가 굉장히 크게 늘어나는 수라는 점을 생각했더라면, input space 가 크더라도 fibo(n) 의 n 값이 커지지 않을 것이라는 것을 미리 알고 있었더라면 저런 고민을 안했을 것 같긴 하다. 하지만, 이러한 사전지식이 없는 가운데, 문제를 풀라고 한다면 어떻게 접근하는게 가장 좋았었을까. 고민된다.

== 느낌 ==
* 컴퓨터의 속도를 무시하지 말자.;
* 그럼에도 불구하고.. '정말 big integer 만들기' 문제였을까? 다시금 고민하게 되다.
* closed form 과 관련하여 Generating Function 이 아직도 익숙치 않아서 mathworld 의 힘을 빌리다. GF 를 공부해야겠다.
* 구간 계산과 관련, 'a 와 가장 가까운 fibonacci 값을 구하기' 는 반복문 돌리기 & if 로 비교 말고 다른 방법이 없을까?
* bigint 를 지원하는 python 이나 matlab 같은 언어에서는 더 할일이 없는 문제. 내가 공식 궁리하는 동안 옆의 분이 matlab 으로 10분만에 풀어버리다. 흑.

HowManyFibs？/1002 - Revision history

Maintenance script: Repair batch-0002 pages from live compare

imported>Unknown at 05:23, 7 February 2021