๐Ÿ–ฅ Computer Science/Algorithm

[Algorithm] Floyd's Cycle Detection์ด๋ž€? (feat. Linked List)

Fomagran ๐Ÿ’ป 2022. 9. 18. 11:31
728x90
๋ฐ˜์‘ํ˜•

์•ˆ๋…•ํ•˜์„ธ์š” Foma ์ž…๋‹ˆ๋‹ค!

 

์š”์ƒˆ LeetCode์—์„œ Linked List์˜ ์‚ฌ์ดํด์— ๊ด€๋ จ๋œ ๋ฌธ์ œ๋ฅผ ํ‘ธ๋Š”๋ฐ slow, fast ํฌ์ธํ„ฐ๋ฅผ ๋งŽ์ด ์ด์šฉํ•˜๋”๋ผ๊ตฌ์š”.

 

ํ•ด๋‹น ํ’€์ด๊ฐ€ ์ดํ•ด๊ฐ€ ์•ˆ๋ผ์„œ ์ฐพ์•„ ๋ณด๋‹ˆ ๊ด€๋ จ๋œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์žˆ์—ˆ๊ณ , ๊ทธ๊ฒƒ์ด Floyd's Cycle Detection ์ด์—ˆ์Šต๋‹ˆ๋‹ค.

 

๊ทธ๋ž˜์„œ ์˜ค๋Š˜์€ ๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ์—์„œ ์‚ฌ์ดํด์ด ์žˆ๋Š”์ง€ ์—†๋Š”์ง€๋ฅผ ํ™•์ธํ•  ์ˆ˜ ์žˆ๊ณ , ํ•ด๋‹น ์‚ฌ์ดํด์˜ ์‹œ์ž‘์ ์ด ์–ด๋””์ธ์ง€ ์•Œ์•„๋‚ผ ์ˆ˜ ์žˆ๋Š” Floyd's Cycle Detection ์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

 

๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~


Floyd's Cycle Detection ์ด๋ž€? ๐Ÿ”

 

Robert W. Floyd๊ฐ€ ๊ณ ์•ˆํ•œ ๋ฆฌ์ŠคํŠธ์˜ ์‚ฌ์ดํด์„ ๋น ๋ฅด๊ณ  ์ ์€ ๋ฉ”๋ชจ๋ฆฌ๋กœ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค.

 

(Robert W. Floyd๋Š” ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋งŒ๋“ค์–ด๋‚ธ ์‚ฌ๋žŒ๊ณผ ๋™์ผ ์ธ๋ฌผ์ž…๋‹ˆ๋‹ค.)

 

 

๊ฑฐ๋ถ์ด์™€ ํ† ๋ผ (Tortoise and Hare) ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ๋„ ๋งŽ์ด ์•Œ๋ ค์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.

 

์™œ ๊ฑฐ๋ถ์ด์™€ ํ† ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ผ๊นŒ? ๐Ÿค”

 

๋ฐ”๋กœ ๊ฑฐ๋ถ์ด์ฒ˜๋Ÿผ ๋Š๋ฆฌ๊ฒŒ ์›€์ง์ด๋Š” ํฌ์ธํ„ฐ์™€ ํ† ๋ผ์ฒ˜๋Ÿผ ๋น ๋ฅด๊ฒŒ ์›€์ง์ด๋Š” ํฌ์ธํ„ฐ ์ด๋ ‡๊ฒŒ ์ด ๋‘ ํฌ์ธํ„ฐ๊ฐ€ ํ•„์š”ํ•˜๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.


Example

 

์•„๋ž˜์™€ ๊ฐ™์ด ์‚ฌ์ดํด์ด ์žˆ๋Š” ๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ๊ฐ€ ์žˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

 

๊ทธ ๋‹ค์Œ ์‚ฌ์ดํด์ด ์‹œ์ž‘๋˜๋Š” ์ง€์ ์„ ์ฐพ์•„ ๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.

 

 

0 1 2 3 4 5 6 7 8 3 4 5 6 7 8 ... ์œผ๋กœ 3๋ถ€ํ„ฐ 8๊นŒ์ง€ ์‚ฌ์ดํด์ด ์กด์žฌํ•˜๋Š” ๋ฆฌ์ŠคํŠธ์ž…๋‹ˆ๋‹ค.

 

1. ๊ฐ€์žฅ ์ฒ˜์Œ ๊ฑฐ๋ถ์ด์™€ ํ† ๋ผ๊ฐ€ ๋งŒ๋‚˜๋Š” ์ง€์ ์„ ๊ตฌํ•œ๋‹ค.

 

๋จผ์ € ๊ฑฐ๋ถ์ด(๋Š๋ฆฌ๊ฒŒ ์ด๋™ํ•˜๋Š” ํฌ์ธํ„ฐ)์™€ ํ† ๋ผ(๋น ๋ฅด๊ฒŒ ์ด๋™ํ•˜๋Š” ํฌ์ธํ„ฐ)๋ฅผ ๊ฐ€์žฅ ์ฒซ ๋ฒˆ์งธ(head)์— ์œ„์น˜ํ•ฉ๋‹ˆ๋‹ค.

 

 

 

๊ฑฐ๋ถ์ด๋Š” ํ•œ ์นธ์”ฉ ํ† ๋ผ๋Š” ๋‘ ์นธ์”ฉ ์ด๋™ํ•˜๋ฉด ์•„๋ž˜์™€ ๊ฐ™์ด ์ง„ํ–‰๋ฉ๋‹ˆ๋‹ค.

 

๊ทธ๋ฆฌ๊ณ  ์„œ๋กœ ๋งŒ๋‚˜๊ฒŒ ๋˜๋Š” ์ง€์ ์€ 6์ด ๋˜์ฃ .

 

(๋งŒ์•ฝ ํ† ๋ผ์™€ ๊ฑฐ๋ถ์ด๊ฐ€ ๋งŒ๋‚˜๋Š” ์ง€์ ์ด ์—†๋‹ค๋ฉด ์‚ฌ์ดํด์ด ์—†๋‹ค๋Š” ์˜๋ฏธ์ž…๋‹ˆ๋‹ค.)

 

 

2. ๊ฑฐ๋ถ์ด๋ฅผ ์ฒซ ๋ฒˆ์งธ ์ง€์ ์œผ๋กœ ๋˜๋Œ๋ฆฌ๊ณ , ํ† ๋ผ์™€ ๊ฑฐ๋ถ์ด ๋‘˜ ๋‹ค ํ•œ ์นธ์”ฉ ์ด๋™ํ•˜๋ฉฐ ๋‹ค์‹œ ๋งŒ๋‚˜๋Š” ์ง€์ ์„ ๊ตฌํ•œ๋‹ค.

 

์ด์ œ ๊ฑฐ๋ถ์ด๋ฅผ ๊ฐ€์žฅ ์ฒซ ๋ฒˆ์งธ๋กœ ๋‹ค์‹œ ๋˜๋Œ๋ฆฝ๋‹ˆ๋‹ค.

 

๊ทธ ๋‹ค์Œ๋ถ€ํ„ฐ๋Š” ํ† ๋ผ๋„ ๊ฑฐ๋ถ์ด์™€ ๊ฐ™์ด ํ•œ ์นธ์”ฉ๋งŒ ์ด๋™ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

์ด๋Ÿฐ ์‹์œผ๋กœ ์ด๋™ํ•˜๋ฉด ํ† ๋ผ์™€ ๊ฑฐ๋ถ์ด ์„œ๋กœ ๋งŒ๋‚˜๋Š” ์ง€์ ์€ 3์ด ๋ฉ๋‹ˆ๋‹ค.

 

์ด๊ฒƒ์€ ์‚ฌ์ดํด์ด ์‹œ์ž‘๋˜๋Š” ์ง€์ ์ด ๋˜๋Š” ๊ฒƒ์ด์ฃ .

 


Proof

 

X: ์‹œ์ž‘์ ๋ถ€ํ„ฐ ์‚ฌ์ดํด์ด ๋ฐœ์ƒํ•˜๊ธฐ ์ „๊นŒ์ง€ ๊ธธ์ด

Y: ์‚ฌ์ดํด ์‹œ์ž‘์ ๋ถ€ํ„ฐ ์ฒซ ๋ฒˆ์งธ ๋งŒ๋‚˜๋Š” ์ง€์  ์ „๊นŒ์ง€ ๊ธธ์ด

Z: ์ฒซ ๋ฒˆ์งธ ๋งŒ๋‚˜๋Š” ์ง€์ ๋ถ€ํ„ฐ ์‚ฌ์ดํด ์‹œ์ž‘์  ์ „๊นŒ์ง€ ๊ธธ์ด

C: ์‚ฌ์ดํด์˜ ๊ธธ์ด

M: ๋งŒ๋‚˜๋Š” ์ง€์ 

 

๋‘ ์นธ์”ฉ ์ด๋™ํ•  ๊ฒฝ์šฐ ์ฒซ ๋ฒˆ์งธ ๋งŒ๋‚˜๋Š” ์ง€์ ๊นŒ์ง€ ์ด๋™ํ•  ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ„์‚ฐํ•˜๋ฉด ์•„๋ž˜์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.

 

์‚ฌ์ดํด์ด ์‹œ์ž‘๋˜๊ธฐ ์ „ X๋งŒํผ ์ด๋™ํ•˜๊ณ  ์‚ฌ์ดํด์„ rโ‚๋ฐ”ํ€ด ๋Œ๊ณ  Y๋งŒํผ ์ด๋™ํ•ด M์ง€์ ์—์„œ ๊ฑฐ๋ถ์ด๋ฅผ ๋งŒ๋‚˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

 

h = x + rโ‚c + y

 

ํ•œ ์นธ์”ฉ ์ด๋™ํ•  ๊ฒฝ์šฐ ์ฒซ ๋ฒˆ์งธ ๋งŒ๋‚˜๋Š” ์ง€์ ๊นŒ์ง€ ์ด๋™ํ•  ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ„์‚ฐํ•˜๋ฉด ์•„๋ž˜์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.

 

์‚ฌ์ดํด์ด ์‹œ์ž‘๋˜๊ธฐ ์ „ X๋งŒํผ ์ด๋™ํ•˜๊ณ  ์‚ฌ์ดํด์„ rโ‚‚๋ฐ”ํ€ด ๋Œ๊ณ  Y๋งŒํผ ์ด๋™ํ•ด M์ง€์ ์—์„œ ํ† ๋ผ๋ฅผ ๋งŒ๋‚˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

 

t = x + rโ‚‚c + y

 

ํ† ๋ผ๋Š” ๋‘ ์นธ์”ฉ, ๊ฑฐ๋ถ์ด๋Š” ํ•œ ์นธ์”ฉ ์›€์ง์ด๋ฏ€๋กœ ๋‹ค๋ฅธ ์‹์œผ๋ก  ์•„๋ž˜์™€ ๊ฐ™์ด ์“ธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

2T = H

 

์ฆ‰, ์•„๋ž˜์™€ ๊ฐ™์ด ํ’€์–ด ์“ธ ์ˆ˜ ์žˆ์ฃ .

 

2(x + rโ‚‚c + y) = x + rโ‚c + y 
-> 2x + 2rโ‚‚c + 2y = x + rโ‚c + y
-> 2x + 2y - x - y = rโ‚c - 2rโ‚‚c
-> x + y =  (rโ‚ - 2rโ‚‚)c
-> x = (rโ‚ - 2rโ‚‚)c - Y
-> x = (rโ‚ - 2rโ‚‚ - 1)c + c -y

 

์ด ๋•Œ rโ‚ - 2rโ‚‚ - 1์€ ์ƒ์ˆ˜์ด๋ฏ€๋กœ rโ‚ƒ๋ผ๋Š” ์ƒˆ๋กœ์šด ์ƒ์ˆ˜๋ฅผ ๋งŒ๋“ค์–ด ๋Œ€์ฒด์‹œ์ผœ ์ค๋‹ˆ๋‹ค.

 

x = rโ‚ƒc + c - y

 

c๋Š” ์‚ฌ์ดํด์ด๋ฏ€๋กœ ๋‹ค๋ฅธ ๋ง๋กœ y + z๊ฐ€ ๋  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

x = rโ‚ƒc  + y + z - y
-> x = rโ‚ƒc  + z

 

์ฆ‰, ์‹œ์ž‘์ ๋ถ€ํ„ฐ ์‚ฌ์ดํด์ด ์‹œ์ž‘๋˜๊ธฐ ์ „๊นŒ์ง€์˜ ๊ธธ์ด๋Š”(x) ์‚ฌ์ดํด์„ rโ‚ƒ๋งŒํผ ๋Œ๊ณ  ๋งŒ๋‚œ ์ง€์ ๋ถ€ํ„ฐ ์‚ฌ์ดํด์ด ์‹œ์ž‘์ ๊นŒ์ง€์˜ ๊ธธ์ด(z)์™€ ๊ฐ™๋‹ค๊ฐ€ ์„ฑ๋ฆฝ๋ฉ๋‹ˆ๋‹ค.

 

๊ณ ๋กœ ์ฒซ ๋ฒˆ์งธ๋กœ ๋งŒ๋‚œ ์ง€์ ๋ถ€ํ„ฐ ์‹œ์ž‘์ ๊นŒ์ง€ ์ฐจ๋ก€๋กœ ํ•œ ์นธ์”ฉ ์ด๋™ํ•˜๋ฉด ์‚ฌ์ดํด์˜ ์‹œ์ž‘์ ์„ ์•Œ ์ˆ˜ ์žˆ๊ฒŒ ๋˜๋Š” ๊ฒƒ์ด์ฃ .


Code

 

์•„๋ž˜์™€ ๊ฐ™์ด ํŒŒ๋ผ๋ฏธํ„ฐ๋กœ ListNode๋ฅผ ๋ฐ›๊ณ , ์‚ฌ์ดํด์˜ ์‹œ์ž‘์ธ ListNode๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋Š” ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ•ด ๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.

 

func floydCycleDetection(_ head:ListNode?) -> ListNode? {

 

๋จผ์ € ํ•œ ์นธ์”ฉ ์›€์ง์ผ ๊ฑฐ๋ถ์ด(tortoise)์™€ ๋‘ ์นธ์”ฉ ์›€์ง์ผ ํ† ๋ผ(hare)๋ฅผ ๊ฐ€์žฅ ์ฒ˜์Œ ๋…ธ๋“œ์ธ head๋กœ ์„ค์ •ํ•ด ์ค๋‹ˆ๋‹ค.

 

    var tortoise = head
    var hare = head

 

while๋ฌธ์„ ์ด์šฉํ•ด tortoise๋Š” next๋กœ ํ•œ ์นธ์”ฉ, hare๋Š” next?.next๋กœ ๋‘ ์นธ์”ฉ ์ด๋™ํ•ด ์ค๋‹ˆ๋‹ค.

 

๋งŒ์•ฝ tortorise์™€ hare๊ฐ€ ๊ฐ™๋‹ค๋ฉด while๋ฌธ์„ ๋ฉˆ์ถฐ ์ค๋‹ˆ๋‹ค.

 

    while true {
        tortoise = tortoise?.next
        hare = hare?.next?.next
        if tortoise === hare {
            break
        }
    }

 

๊ฑฐ๋ถ์ด๋ฅผ ๋‹ค์‹œ ์ฒ˜์Œ์œผ๋กœ ๋˜๋Œ๋ ค ์ค๋‹ˆ๋‹ค.

 

    tortoise = head

 

์ด๋ฒˆ์—” tortoise์™€ hare ๋‘˜ ๋‹ค ๋˜‘๊ฐ™์ด next๋กœ ํ•œ ์นธ์”ฉ๋งŒ ์ด๋™์‹œ์ผœ ์ค๋‹ˆ๋‹ค.

 

๋งŒ์•ฝ tortorise์™€ hare๊ฐ€ ๊ฐ™๋‹ค๋ฉด while๋ฌธ์„ ๋ฉˆ์ถฐ ์ค๋‹ˆ๋‹ค.

 

    while true {
        tortoise = tortoise?.next
        hare = hare?.next
        if tortoise === hare {
            break
        }
    }

 

 

tortoise ๋˜๋Š” hare๋ฅผ ๋ฐ˜ํ™˜ํ•ด ์ฃผ๋ฉด ์‚ฌ์ดํด์˜ ์‹œ์ž‘์ (3)์ด ๋ฐ˜ํ™˜๋ฉ๋‹ˆ๋‹ค.

 

 

    return tortoise //value: 3

Reference

 

 

728x90
๋ฐ˜์‘ํ˜•