책읽기003)프로그래밍 면접 이렇게 준비한다 - 3

2015. 2. 26. 00:30엘키스공간/독서

728x90
728x90

1. 순환형 연결리스트 여부알아보기

순환형인지 아닌지 판단하는 알고리즘을 찾는것.

일단 먼저 떠오르는 방법은 노드에 한번 지나간 자리인지 확인하는

변수를 선언하고 변수를 체크해 순환형을 가려낼 수 있다.

하지만 이렇게 푸는건 적절한 문제 풀이가 아니다! 적어도 면접관에겐!

- 노드에 변수를 넣는것은 노드를 수정한다는 의미. 최대한 노드 수정 없이!


2. 해결방법

토끼와 거북이 알고리즘! Tortoise and Hare 알고리즘이다.

2개의 포인터의 증감률을 다르게 하여 탐색한다.

이 알고리즘의 장점은 특히 비순환일때 탐색 속도가 n/2로 줄어든다.

빠르게 뛰는 토끼포인터가 거북이 포인터와 같아지거나 앞지르게 되면 이것은 순환형!

빠르게 뛰는 토끼포인터가 널 포인터를 만난다면 이것은 비순환형이 되는것이다.


위키에서 퍼온 것! http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare

Tortoise and hare[edit]

Floyd's "tortoise and hare" cycle detection algorithm, applied to the sequence 2, 0, 6, 3, 1, 6, 3, 1, ...

Floyd's cycle-finding algorithm, also called the "tortoise and the hare algorithm", alluding to Aesop's fable of The Tortoise and the Hare, is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds.

The algorithm is named for Robert W. Floyd, who was credited with its invention by Donald Knuth.[1][2] However, the algorithm does not appear in Floyd's published work, and this may be a misattribution: Floyd describes algorithms for listing all simple cycles in a directed graph in a 1967 paper,[3] but this paper does not describe the cycle-finding problem in functional graphs that is the subject of this article. In fact, Knuth's statement (in 1969), attributing it to Floyd, without citation, is the first known appearance in print, and it thus may be a folk theorem, not attributable to a single individual.[4]

The key insight in the algorithm is that, for any integers i ≥ μ and k ≥ 0xi = xi + kλ, where λ is the length of the loop to be found and μ is the index of the first element of the cycle. In particular, whenever i = kλ ≥ μ, it follows that xi = x2i. Thus, the algorithm only needs to check for repeated values of this special form, one twice as far from the start of the sequence as the other, to find a period ν of a repetition that is a multiple of λ. Once ν is found, the algorithm retraces the sequence from its start to find the first repeated value xμ in the sequence, using the fact that λ divides ν and therefore that xμ = xμ + v. Finally, once the value of μ is known it is trivial to find the length λ of the shortest repeating cycle, by searching for the first position μ + λ for which xμ + λ = xμ.

The algorithm thus maintains two pointers into the given sequence, one (the tortoise) at xi, and the other (the hare) at x2i. At each step of the algorithm, it increases i by one, moving the tortoise one step forward and the hare two steps forward in the sequence, and then compares the sequence values at these two pointers. The smallest value of i > 0 for which the tortoise and hare point to equal values is the desired value ν.




728x90
반응형