알고리즘 2

single linked list에서 루프를 찾는 방법

- 오늘의 퀴즈입니다. 1) single linked list에서 루프가 존재하는지를 구하는 방법 hint) 거북이와 토끼의 경주에서 산꼭대기를 향해서 뛰어가지 않고, 트랙을 돌고 있다면? 답) 거북이와 토끼는 처음 만나서 경주를 하게 됩니다. 토끼는 육상 선수여서 그런지 엄청빠른 속도로 달릴 수가 있지요. 그에 비해 거북이는 엉그적 엉그적 느리게 걸어갑니다. 출발 소리를 들리고 토끼가 잽싸게 뛰쳐 나가죠. 이 놈의 속도를 측정하니 거북이의 두배나 빨랍답니다. 이에 비해서 거북이는 세월아 내월아 천천히 걸어가고 있었어요. 그런데 사실 토끼와 거북이의 경주는 산을 향해서 달리고 있었던게 아니었어요. 산꼭대기로 난 길이라고 생각했지만 산 주위를 계속 돌고 있는 길이었죠. 기억력이 나쁜 토끼는 자신이 산 주위..

Passion/Algorithm 2006.11.22

Merge sort

머지 소트의 기본 개념은 Divide and Quanqer 알고리즘이다. 리스트를 소트된 순서대로 쪼개가면서(1개의 엘리멘트가 나올때까지) 짜른 다음 두개의 리스트를 하나로 순서대로 합해가면서 소팅을 한다. * 간단하게 파이슨으로 머지소트를 구현해 보면 다음과 같다. 1 def mergesoft(list): 2 if len(list) 0 and len(right) > 0: 24 if left[0] 0: 29 for item in left: 30 result.append(item) 31 if len(right) > 0: 32 for item in right: 33 result.append(item) 34 return result

Passion/Programming 2006.11.21