나 바보되감.
유학간 친구놈이랑 쓸만한 신입구하는거 얘기하다가
Linked List에 Cycle 있는지 테스트 하는거 문제얘기가 나왔다.
O(n)에 메모리도 O(1)로.
MS시험문제라는 소문도 있고, 어쩌구저쩌구
멍하게 앉아서 잠깐 생각해보니, 안풀리는거다! 이런!!
바보되어간다. 쳇.
근데 친구 자러 로그오프한 직후 허무하게 답 깨달음. 바붕!
어쨌든 이문제는 앞으로 쭉 써봐야지. 크핫
Posted by kaicy on November 19th, 2004 :: Filed under 끄적끄적
You can skip to the end and leave a response. Pinging is currently not allowed.
November 20th, 2004
linked list인데 cycle이 있으면 그냥 circular list (핫 말이 이상하군..^^)이니까, 아무노드나 (머, first node 겠지만서서두) 하나 기억해놓고서, link를 따라가다가 그게 다시 나타나는지만 확인하면 되잖아.. circle 이 있던 아니던 list의 노드수 만큼만 테스트 하면 끝나는거구.. 아직 녹슬지 않았군.. 카카카.
November 20th, 2004
음.. 블로그에 올려버리다닛..
용재답이 거의 맞는데.. 꼭 cycle이 첫노드를 포함한다는 보장이 없으니까.. 포인터 두개로 리스트를 따라가는데 한놈은 하나씩, 다른놈은 두개씩 가면서 테스트.. 두놈이 만나면 cycle, 느린놈이 무사히 끝까지 가면 OK..
November 20th, 2004
아.. 느린넘이 아니라 빠른넘이 끝까지 가면 OK..
November 20th, 2004
이놈. 여기 답을 쓰면 우짜노~ ㅡ.ㅡ;
어제 바로 깨달은 답은 용재랑 똑같은거였는데,
집에가다가 종우가 말한 문제점을 깨닫고
다시 고민하다가 대략 깨달음을 겨우 얻고.ㅡ.ㅡ;;;
녹슬어가는 용재~ 크하하핫~~
November 20th, 2004
ㅎㅎ.. 주인장이니까 답을 지울수도 있잖아..
November 22nd, 2004
걍, 놔두지 머. 리플 아깝다.ㅡ.ㅡ;;;;;;