<p style="text-align: left;"><img src="https://t1.daumcdn.net/cfile/cafe/999923415CF4D72231" class="txc-image" actualwidth="870" hspace="1" vspace="1" border="0" width="870" exif="{}" data-filename="K-197.png" style="clear:none;float:none;" id="A_999923415CF4D72231526E"/></p><p><br></p><p>문제 풀다가 컴퓨터 없이 암산으로 풀 수 있는 문제를 찾아서 함 가져와 봤습니다! 트릭을 알면 컴퓨터 없이 풀 수 있습니다.</p><p><br></p><p><br></p><p style="text-align: left;"><img src="https://t1.daumcdn.net/cfile/cafe/9909C5335CF4D7972D" class="txc-image" actualwidth="870" hspace="1" vspace="1" border="0" width="870" exif="{}" data-filename="K-195.png" style="clear:none;float:none;" id="A_9909C5335CF4D7972D3E65"/></p><p style="text-align: left;">이건 트릭 알아도 컴 없으면 못 푸는 문제.</p>
<!-- -->
@띵하오윗쪽 정답은 452, 아랫쪽 정답은 936입니다. 계산하는 법은 쉬워요. 공이 노드를 지나갈 때, 짝수번째로 지나가는 공이면 오른쪽으로, 홀수번째로 지나가는 공이면 왼쪽으로 갑니다. 1번째 공은 첫번째 노드에서 왼쪽으로, 2번쨰 공은 첫번째 노드에서 오른쪽으로, 3번째는 다시 왼쪽으로. 이것이 재귀적으로 반복된다는 점을 활용하시면 됩니다!
@메가스콤네노스452요? 완전 근처에도 안갔네.. 제가 컴싸문제를 안풀어봐서 그런데, 그냥 풀어서 물어볼께요. 처음 노드는 2번째가 지나가면 오른쪽으로 가면서 다시 왼쪽으로 바뀌어요. 두번째 노드는 첫번째가 두번에 한번 오는 것과 같으니 4번째까지 지나면 돌아와요. 이렇게 보면 다섯번째 노드까지는 32번째까지 가면 원래 모양으로 돌아와요. 그러니까 이 모형은 돌아오는 횟수의 절반이 지나면 전부 다음번엔 R로 가도록 바뀌어요. 그래서 32번째까지 갔을때 모양은 L-L-L-L-L이고, 뒤의 여섯번째 노드는 R, 뒤의 일곱,여덟번째 노드는 아직 R로도 다 안바뀌었으니 L-L이예요.
@띵하오여기에 3번을 다시 더하면, 36번째 시도에서 처음 두 노드는 2+1이니까 R-R이예요. 나머지는 그대로이니 L-L-L-R-L-L-이예요. 여기서 굴릴 경우, 갈 수 있는 범위는 각자 가지고 있는 영역에서 절반씩 줄어들거든요. R이면 왼쪽에서 줄어들고, L이면 오른쪽에서 줄어들고요. 그러면 제가 세번째 댓글에 달았던 대로 393이 나오거든요? 어디서 틀린건지 모르겠는데, 저와 푸는 방식이 다르신건가요?
@띵하오가만 생각해보니 제가 잘못 생각한 부분이 있네요. 2^8-1이 8층 마지막 수니까 시작을 [256,511]에서 시작해야 했네요. [256,511]-R[384,511]-R[448,511]-L[448,479]-L[448.463]-L[448,455]-R[452,455]-L[452,]-L[452,] 452 맞네요. 이거 멋쩍습니다 ㅎ
이게 동작을 보시면 msb부터 뒤집히는 카운터거든요~ lsb부터 뒤집히는 원래 카운터는 height 3이라고 하면 000 001 010 011 100 101 110 111이죠? msb부터 뒤집어보면 000 100 010 110 001 101 011 111이 나와요 카운터인걸 알 수 있는 이유는 각 비트가 공 한개씩 지날때마다 스위치를 건드리는걸로 아실 수 있어요~ 1번째 height는 매 공마다 바뀌고 2번째 height는 2^1공마다 바뀌고... 이러면 모든 자리수를 순서대로 건드리는 카운터가 된다는걸 귀납적으로 알 수 있습니다.
첫댓글 그래서 재미는 어디서 찾으면 되는거죠!
컴싸는 컴퓨터용 싸인펜 아닌가요? 하와와
분하지만 같은 생각하고 들아왔습니다 하와와와..
내일 6평인데 컴싸 까먹고있다가 이글보고 생각났습니다 ㅋㅋㅋ
저도 내일 6평봐요!
-수시러-
@Perfect Immortal Machine 좋은 결과가 있으시길!
-정시러-
@오스만kimjs 수학 가형빼고 다 조짐 ...흙
@Perfect Immortal Machine 세계사 18번문제 수특에도 안나오는 농업조정법이...
@오스만kimjs 히익
@Perfect Immortal Machine 유로파 짬밥(?)으로 맞추긴했습니다ㅋㅋ 소거법으로
@오스만kimjs 저도 세계지리 시간에 유롭과 호이가 도움되었습니다. (잠만 나 이관데?!)
@Perfect Immortal Machine ㅋㅋ
자료구조에서 재미를 찾는자 DB자라 -)-...
컴공인데 컴싸가뭐죠?
컴퓨터 사이코요.. 소근소근..
재미는 미국에 있단 얘기니, 재미가 미국 가버린 겁니까?
@오스트리아 황제 프란츠 1세 재미교포는 죽은 사람을 달리 이르는 말로 알고있습니다만
이걸 아주 잘 표현한 작품이 바로 <검정고무신>입니다
@오스트리아 황제 프란츠 1세 Deus vult!
1. 2-4-8-16-32로 원상복귀 되므로, 다섯번째 줄까지는 4번째와 같음 / r-r-l-l-l / 6은 반을 돌았으므로 l/7,8,9는 아직 반을 못돌았으므로 r-r-r / r-r-l-l-l-l-r-r-r / 2-4-7-13-25-49-98-196-392 입니까? 사실 내가 쓰면서도 뭔가 생각이 맞는지 모르겠는데.
2. 2-4-8-16-.....-2^11까지 한바퀴. 3366-2048=1318. 2^10까지 한바퀴. 1318-1024=294. 2^8까지 한바퀴. 294-256=38. 2^5까지 한바퀴. 38-32=6, 6-4=2. / 13부터 101까지 l, 12 r, 11 l, 10과 9 r, 8부터 6 l, 5부터 3 r, 2 l, 1 r /
r-l-r-r-r-l-l-l-r-r-l-r-l-(...)-l/
2-3-6-12-24-47-97-193-286-572-1041-2082-4161-(..)-1.287e+30이 나오지만 잘푼건지 헛짓거리 한건지
알수가 없습니다. 사실 답을 알고 싶어서 적은 거임.
아니네요. 1. 틀렸네. r-r-l-l-l 에 6번째는 반을 돌았으니 r, 7,8은 아직 도착하지 않았으므로 l-l / r-r-l-l-l-r-l-l / (1,511) - (257,511) - (385,511) - (385,447) - (385,415) - (385,399) - (393,399) - (393,395) - (393,393) / 393 인것 같네요. 왜 값이 비슷한지는 의문인데..
@띵하오 윗쪽 정답은 452, 아랫쪽 정답은 936입니다. 계산하는 법은 쉬워요. 공이 노드를 지나갈 때, 짝수번째로 지나가는 공이면 오른쪽으로, 홀수번째로 지나가는 공이면 왼쪽으로 갑니다. 1번째 공은 첫번째 노드에서 왼쪽으로, 2번쨰 공은 첫번째 노드에서 오른쪽으로, 3번째는 다시 왼쪽으로. 이것이 재귀적으로 반복된다는 점을 활용하시면 됩니다!
2. 13부터 100까지 l, 12는 반바퀴이므로 r, 11은 반바퀴이므로 r, 10은 한바퀴이므로 l, 9는 8에서 한바퀴 도므로 r, 8과 7은 l, 6은 r, 5와 4는 l, 3은 r, 2는 l, 1은 r / r-r-r-l-l-r-l-l-r-l-r-r-(나머지 l) / 복잡하니까 2^100을 X로 두면 (1,X)-((1/2)*X+1,X)-((2^2-1)/(2^2)*X+1,2^100)-((2^3-1)/(2^3)*X+1,X)-2^4 도입-2^5 도입-(((2^3-1)/(2^3)+(2^6-1)/(2^6))*X+1,~)-2^7-2^8-(((2^3-1)/(2^3)+(2^6-1)/(2^6)+(2^9-1)/(2^9))*X+1,~)-2^10 도입 - (((2^3-1)/(2^3)+(2^6-1)/(2^6)+(2^9-1)/(2^9)+(2^11-1)/(2^11))*X+1,~) -(((2^3-1)/(2^3)+(2^6-1)/(2^6)+(2^9-1)/(2^9)+(2^11-1)/(2^11) + (2^12-1)/(2^12))*X+1,~)인듯요.
@메가스콤네노스 452요? 완전 근처에도 안갔네.. 제가 컴싸문제를 안풀어봐서 그런데, 그냥 풀어서 물어볼께요. 처음 노드는 2번째가 지나가면 오른쪽으로 가면서 다시 왼쪽으로 바뀌어요. 두번째 노드는 첫번째가 두번에 한번 오는 것과 같으니 4번째까지 지나면 돌아와요. 이렇게 보면 다섯번째 노드까지는 32번째까지 가면 원래 모양으로 돌아와요. 그러니까 이 모형은 돌아오는 횟수의 절반이 지나면 전부 다음번엔 R로 가도록 바뀌어요. 그래서 32번째까지 갔을때 모양은 L-L-L-L-L이고, 뒤의 여섯번째 노드는 R, 뒤의 일곱,여덟번째 노드는 아직 R로도 다 안바뀌었으니 L-L이예요.
@띵하오 여기에 3번을 다시 더하면, 36번째 시도에서 처음 두 노드는 2+1이니까 R-R이예요. 나머지는 그대로이니 L-L-L-R-L-L-이예요. 여기서 굴릴 경우, 갈 수 있는 범위는 각자 가지고 있는 영역에서 절반씩 줄어들거든요. R이면 왼쪽에서 줄어들고, L이면 오른쪽에서 줄어들고요. 그러면 제가 세번째 댓글에 달았던 대로 393이 나오거든요? 어디서 틀린건지 모르겠는데, 저와 푸는 방식이 다르신건가요?
@띵하오 가만 생각해보니 제가 잘못 생각한 부분이 있네요. 2^8-1이 8층 마지막 수니까 시작을 [256,511]에서 시작해야 했네요. [256,511]-R[384,511]-R[448,511]-L[448,479]-L[448.463]-L[448,455]-R[452,455]-L[452,]-L[452,]
452 맞네요. 이거 멋쩍습니다 ㅎ
학부시절 생각나네.. 어언 20년전...
삭제된 댓글 입니다.
윗쪽 정답은 452, 아랫쪽 정답은 936입니다.
삭제된 댓글 입니다.
윗쪽 정답은 452, 아랫쪽 정답은 936입니다.
풀이법: height k인 tree에서 n번째 공의 위치를 구하려면 n-1을 k bit 2진수로 바꾸고, 앞뒤를 한번 뒤집은 다음에 2^k를 더하면 됩니다.
1번: 36 => 35 => 00100011 => 11000100 => 196 => 2^8 + 196 => 452
2번: 3366 => 3365 => 000...110100100101 => 101001001011.....000 => 2^100 + 101001001011...000 mod 1000
어..? 계산이 안되네요 이거 어떻게하죠
파이썬을 쓰시면 됩니다! 64bit 이상의 수를 다루려면 라이브러리 사용해야하는 c++과는 달리 파이썬은 자체적으로 그 기능을 지원해주죠!
아 근데 저 문제 해답에도 님이 사용하신 방식이 나와있던데, 혹시 왜 그런지 좀 더 자세히 설명해주실 수 있나요?
이게 동작을 보시면 msb부터 뒤집히는 카운터거든요~ lsb부터 뒤집히는 원래 카운터는 height 3이라고 하면 000 001 010 011 100 101 110 111이죠? msb부터 뒤집어보면 000 100 010 110 001 101 011 111이 나와요
카운터인걸 알 수 있는 이유는 각 비트가 공 한개씩 지날때마다 스위치를 건드리는걸로 아실 수 있어요~ 1번째 height는 매 공마다 바뀌고 2번째 height는 2^1공마다 바뀌고... 이러면 모든 자리수를 순서대로 건드리는 카운터가 된다는걸 귀납적으로 알 수 있습니다.
이렇게 보시면 저 문제는 msb부터 동작하는 k bit 카운터의 n번째 entry를 찾는 문제가 되는거죠! 원래 카운터랑 msb부터 토글되는 카운터는 앞뒤를 바꾸면 되는거고요. 그러면 36번째 entry는 35를 이진수로 바꾼걸 뒤집어준 이진수랑 매칭이 되는거에요~
이해했냐고 물어보는게 먼저 아닙니까 ㅠㅠ