๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
728x90
๋ฐ˜์‘ํ˜•

cycle1

[Algorithm] Floyd's Cycle Detection์ด๋ž€? (feat. Linked List) ์•ˆ๋…•ํ•˜์„ธ์š” Foma ์ž…๋‹ˆ๋‹ค! ์š”์ƒˆ LeetCode์—์„œ Linked List์˜ ์‚ฌ์ดํด์— ๊ด€๋ จ๋œ ๋ฌธ์ œ๋ฅผ ํ‘ธ๋Š”๋ฐ slow, fast ํฌ์ธํ„ฐ๋ฅผ ๋งŽ์ด ์ด์šฉํ•˜๋”๋ผ๊ตฌ์š”. ํ•ด๋‹น ํ’€์ด๊ฐ€ ์ดํ•ด๊ฐ€ ์•ˆ๋ผ์„œ ์ฐพ์•„ ๋ณด๋‹ˆ ๊ด€๋ จ๋œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์žˆ์—ˆ๊ณ , ๊ทธ๊ฒƒ์ด Floyd's Cycle Detection ์ด์—ˆ์Šต๋‹ˆ๋‹ค. ๊ทธ๋ž˜์„œ ์˜ค๋Š˜์€ ๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ์—์„œ ์‚ฌ์ดํด์ด ์žˆ๋Š”์ง€ ์—†๋Š”์ง€๋ฅผ ํ™•์ธํ•  ์ˆ˜ ์žˆ๊ณ , ํ•ด๋‹น ์‚ฌ์ดํด์˜ ์‹œ์ž‘์ ์ด ์–ด๋””์ธ์ง€ ์•Œ์•„๋‚ผ ์ˆ˜ ์žˆ๋Š” Floyd's Cycle Detection ์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~ Floyd's Cycle Detection ์ด๋ž€? ๐Ÿ” Robert W. Floyd๊ฐ€ ๊ณ ์•ˆํ•œ ๋ฆฌ์ŠคํŠธ์˜ ์‚ฌ์ดํด์„ ๋น ๋ฅด๊ณ  ์ ์€ ๋ฉ”๋ชจ๋ฆฌ๋กœ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค. (Robert W. Floyd๋Š” ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋งŒ๋“ค.. 2022. 9. 18.
728x90
๋ฐ˜์‘ํ˜•

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”