[๊นƒ] ์ฒด๋ฆฌํ”ฝ (Cherry-pick) ๐Ÿ’

์ฒด๋ฆฌํ”ฝ

์ฒด๋ฆฌํ”ฝ์ด๋ž€ ํ•˜๋‚˜ ์ด์ƒ์˜ ๊ธฐ์กด์˜ ์ปค๋ฐ‹์˜ ๋ณ€๊ฒฝ ์‚ฌํ•ญ์„ ์ ์šฉํ•˜์—ฌ ์ƒˆ ์ปค๋ฐ‹์œผ๋กœ ๊ธฐ๋กํ•˜๋Š” ๊ฒƒ์ด๋‹ค. ๋ธŒ๋žœ์น˜์—์„œ ์ปค๋ฐ‹์„ ์„ ํƒํ•˜๊ณ  ๋‹ค๋ฅธ ๋ธŒ๋žœ์น˜์— ์ ์šฉํ•˜๋Š” ๊ฒƒ์ด๋‹ค.

์ฒด๋ฆฌํ”ฝ ์‚ฌ์šฉ์˜ ์˜ˆ

์ปค๋ฐ‹์„ ์ž˜๋ชป๋œ ๋ธŒ๋žœ์น˜์— ํ•œ ๊ฒฝ์šฐ ํ•ด๋‹น ์ปค๋ฐ‹์„ ์ฒด๋ฆฌํ”ฝํ•˜์—ฌ ์›ํ•˜๋Š” ๋ธŒ๋žœ์น˜์— ์ ์šฉ์‹œํ‚ฌ ์ˆ˜ ์žˆ๋‹ค. ๋‹ค๋ฅธ ๋ ˆํฌ์ง€ํ† ๋ฆฌ์˜ ๋ธŒ๋žœ์น˜์— ์ ์šฉ๋œ ๋ณ€๊ฒฝ ์‚ฌํ•ญ๋“ค์„ ํ˜„์žฌ ๋ ˆํฌ์ง€ํ† ๋ฆฌ์˜ ์›ํ•˜๋Š” ๋ธŒ๋žœ์น˜์— ์ ์šฉ์‹œํ‚ฌ ์ˆ˜ ์žˆ๋‹ค.

์ƒˆ๋กœ์šด ๊ธฐ๋Šฅ ๊ฐœ๋ฐœ ๋„์ค‘ ๋ฒ„๊ทธ๋ฅผ ๋ฐœ๊ฒฌํ•œ ๊ฒฝ์šฐ ํ•ซํ”ฝ์Šค๋ฅผ ์œ„ํ•ด ํ•ด๋‹น ๋ฒ„๊ทธ๋ฅผ ์ˆ˜์ •ํ•œ ๋ณ€๊ฒฝ ์‚ฌํ•ญ์„ ์ปค๋ฐ‹์œผ๋กœ ์ƒ์„ฑํ•˜๋ฉด ๋ฉ”์ธ ๋ธŒ๋žœ์น˜์—์„œ ํ•ด๋‹น ํ•ซํ”ฝ์Šค ์ปค๋ฐ‹์„ ์ฒด๋ฆฌํ”ฝํ•˜์—ฌ ๋ฒ„๊ทธ๋ฅผ ๋น ๋ฅด๊ฒŒ ์ˆ˜์ •ํ•  ์ˆ˜ ์žˆ๋‹ค.

์ฒด๋ฆฌํ”ฝ ์‚ฌ์šฉ ์‹œ ์ฃผ์˜์‚ฌํ•ญ

์ฒด๋ฆฌํ”ฝ์„ ์œ„ํ•ด์„œ๋Š” HEAD ์ปค๋ฐ‹ ์ดํ›„์— ๋ณ€๊ฒฝ ์‚ฌํ•ญ์ด ์—†์–ด์•ผ ํ•œ๋‹ค. ๋˜ํ•œ ๋ณ‘ํ•ฉ๊ณผ ๋ฆฌ๋ฒ ์ด์Šค๋ฅผ ๋Œ€์ฒดํ•˜๊ธฐ ์œ„ํ•ด ์‚ฌ์šฉํ•˜๋Š” ๊ฒƒ์„ ๊ถŒ์žฅํ•˜์ง€ ์•Š๋Š”๋‹ค.

์ฒด๋ฆฌํ”ฝ ์‹œ ๋ณ‘ํ•ฉ ์ถฉ๋Œ์ด ๋ฐœ์ƒํ•˜๋Š” ์ด์œ ๋Š” ์ฒด๋ฆฌํ”ฝ ๋Œ€์ƒ ๋ธŒ๋žœ์น˜์™€ ํ˜„์žฌ ๋ธŒ๋žœ์น˜๊ฐ€ ๋ถ„๊ธฐ๋œ ์ดํ›„ ๋™์ผํ•œ ํŒŒ์ผ์— ๋Œ€ํ•œ ์ˆ˜์ •์ด ๋ฐœ์ƒํ–ˆ๊ธฐ ๋•Œ๋ฌธ์ด๋ฉฐ ์ด ๊ฒฝ์šฐ ํ•ด๋‹น ์ฒด๋ฆฌํ”ฝ ๋Œ€์ƒ ์ปค๋ฐ‹์ด ํ˜„์žฌ ๋ธŒ๋žœ์น˜์— ํ˜•์ƒ์ด ๋‹ค๋ฅผ ๊ฒƒ์ด๋‹ค.

์—ฌ๋Ÿฌ ์ปค๋ฐ‹๋“ค์„ ์ฒด๋ฆฌํ”ฝํ•˜๋Š” ๋„์ค‘ ํŠน์ • ์ฒด๋ฆฌํ”ฝ์—์„œ ๋ณ‘ํ•ฉ ์ถฉ๋Œ์ด ๋ฐœ์ƒํ•˜๋Š” ๊ฒฝ์šฐ๋Š” ํ˜„์žฌ๊นŒ์ง€ ์ฒด๋ฆฌํ”ฝํ•˜์—ฌ ์ปค๋ฐ‹์„ ๋ฐ˜์˜ํ•œ ์Šค๋ƒ…์ƒท(ํŠน์ • ์ฒด๋ฆฌํ”ฝ ์ด์ „ ์Šค๋ƒ…์ƒท)์„ ๊ธฐ์ค€์œผ๋กœ ํ•ด๋‹น ํŒŒ์ผ์„ ๋ณ€๊ฒฝํ•ด ๊ฐ€๊ณ  ์žˆ๊ธฐ ๋•Œ๋ฌธ์ด๊ณ  ํ•ด๋‹น ํŒŒ์ผ์ด ํŠน์ • ์ฒด๋ฆฌํ”ฝ ๋Œ€์ƒ ์ปค๋ฐ‹์—์„œ ์ˆ˜์ •ํ•œ ํŒŒ์ผ๊ณผ ๋™์ผํ•œ ํŒŒ์ผ์ด๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ์ตœ์‹ ํ™”๋œ A ๋ธŒ๋žœ์น˜์— B ๋ธŒ๋žœ์น˜์˜ ์ปค๋ฐ‹์„ ์ฒด๋ฆฌํ”ฝ ์ค‘์ด๊ณ , ์ฒด๋ฆฌํ”ฝ ๋„์ค‘ ๋ณ‘ํ•ฉ ์ถฉ๋Œ์ด ๋ฐœ์ƒํ•˜๋ฉด A ๋ธŒ๋žœ์น˜์— ์ตœ์‹ ํ™”๋œ ์†Œ์Šค๋ฅผ ์„ ํƒํ•˜๊ณ , A ๋ธŒ๋žœ์น˜์— ์•„์ง ๋ฐ˜์˜๋˜์ง€ ์•Š์€ ์†Œ์Šค๋Š” B ๋ธŒ๋žœ์น˜์˜ ์†Œ์Šค๋ฅผ ์„ ํƒํ•œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์ฒด๋ฆฌํ”ฝ ๋Œ€์ƒ ์ปค๋ฐ‹์ด ์ด์ „์— ๊ณผ๊ฑฐ ์‹œ์ ์˜ A ๋ธŒ๋žœ์น˜๋ฅผ B ๋ธŒ๋žœ์น˜์— ๋ณ‘ํ•ฉํ•œ ๋ณ‘ํ•ฉ ์ปค๋ฐ‹์ด๋ผ๋ฉด ํ•ด๋‹น ๋ณ‘ํ•ฉ ์ปค๋ฐ‹์€ ์ฒด๋ฆฌํ”ฝ์—์„œ ์ œ์™ธํ•œ๋‹ค.

๋ณ‘ํ•ฉ ์ปค๋ฐ‹

์ปค๋ฐ‹์€ ๋ถ€๋ชจ ์ปค๋ฐ‹์„ ๊ฐ€์ง€์ง€ ์•Š๊ฑฐ๋‚˜ ํ•˜๋‚˜ ์ด์ƒ์˜ ๋ถ€๋ชจ ์ปค๋ฐ‹์„ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋‹ค. ๋ณ‘ํ•ฉ ์ปค๋ฐ‹์ด ๋ฐœ์ƒํ•˜๋Š” ๊ฒฝ์šฐ ํ•ด๋‹น ์ปค๋ฐ‹์€ ๋‘ ๊ฐœ ์ด์ƒ์˜ ๋ถ€๋ชจ ์ปค๋ฐ‹์„ ๊ฐ€์ง€๊ฒŒ ๋œ๋‹ค.

ํ˜„์žฌ ์ฒดํฌ์•„์›ƒํ•œ ๋ณ‘ํ•ฉ ๊ธฐ์ค€ ๋ธŒ๋žœ์น˜์ธ A ๋ธŒ๋žœ์น˜์— ๋ณ‘ํ•ฉ ๋Œ€์ƒ ๋ธŒ๋žœ์น˜์ธ B ๋ธŒ๋žœ์น˜๋ฅผ ๋ณ‘ํ•ฉํ•˜๋ ค๊ณ  ํ•˜๋Š” ๊ฒฝ์šฐ A ๋ธŒ๋žœ์น˜์˜ ๋ณ‘ํ•ฉ ์ปค๋ฐ‹ ์ „ ๊ฐ€์žฅ ์ตœ๊ทผ ์ปค๋ฐ‹์ด ์ฒซ๋ฒˆ์งธ ๋ถ€๋ชจ(first parent) ์ปค๋ฐ‹์ด๋ฉฐ B ๋ธŒ๋žœ์น˜์˜ ๊ฐ€์žฅ ์ตœํฐ ์ปค๋ฐ‹์ด ๋‘๋ฒˆ์งธ ๋ถ€๋ชจ(second parent) ์ปค๋ฐ‹์ด๋‹ค.

A a1-a2-a3-a4
B   \b1-b2/

๋ณ‘ํ•ฉ ์ปค๋ฐ‹์ธ a4 ์ปค๋ฐ‹์˜ ์ฒซ๋ฒˆ์งธ ๋ถ€๋ชจ๋Š” a3 ์ปค๋ฐ‹์ด๋ฉฐ ๋‘๋ฒˆ์งธ ๋ถ€๋ชจ๋Š” b2 ์ปค๋ฐ‹์ด๋‹ค.

๋ณ‘ํ•ฉ์„ ๋ฐ˜๋Œ€๋กœ ํ–ˆ๋‹ค๋ฉด? ๋‹ค๋ฅธ ๋ธŒ๋žœ์น˜์˜ ๋ณ‘ํ•ฉ ์ปค๋ฐ‹์„ ์ฒด๋ฆฌํ”ฝ ํ–ˆ๋‹ค๋ฉด?

๋ธŒ๋žœ์น˜ A์— ๋ธŒ๋žœ์น˜ B๋ฅผ ๋ณ‘ํ•ฉํ•ด์•ผ ํ•˜์ง€๋งŒ ๋ฐ˜๋Œ€๋กœ ๋ธŒ๋žœ์น˜ B์— ๋ธŒ๋žœ์น˜ A๋ฅผ ๋ณ‘ํ•ฉํ•˜๋ฉด ์˜๋„์น˜ ์•Š๊ฒŒ ๋ธŒ๋žœ์น˜ B์—๋Š” ๋ธŒ๋žœ์น˜ A์˜ ์ปค๋ฐ‹๋“ค์ด ๋ฐ˜์˜๋˜๊ฒŒ ๋œ๋‹ค.

C   /c1\
A a1-a2-a3\
B   \b1-b2-b3-b4-b5
B'   b1-b2-b4-b5

์ด ๊ฒฝ์šฐ ๋ณ‘ํ•ฉ ์ปค๋ฐ‹(b3)์œผ๋กœ ์ธํ•ด ๋ธŒ๋žœ์น˜ A์— ํฌํ•จ๋œ ์ปค๋ฐ‹ ์ค‘ ๋‹ค๋ฅธ ๋ธŒ๋žœ์น˜(๋ธŒ๋žœ์น˜ C)์˜ ์ปค๋ฐ‹(๋ณ‘ํ•ฉ์ด ์ด๋ฃจ์–ด์ง„ ๊ฒฝ์šฐ)์ด ๋ธŒ๋žœ์น˜ B์— ๋ฐ˜์˜๋  ์ˆ˜๋„ ์žˆ๋‹ค. ๋˜๋Š” ๋ธŒ๋žœ์น˜ A์—์„œ ์ˆ˜ํ–‰ํ•œ ๋ณ‘ํ•ฉ ์ปค๋ฐ‹(a3) ์ž์ฒด๋ฅผ ๋ธŒ๋žœ์น˜ B์—์„œ ์ฒด๋ฆฌํ”ฝํ•œ๋‹ค๋ฉด ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ ์˜๋„์น˜ ์•Š๊ฒŒ ๋ธŒ๋žœ์น˜ B์—๋Š” ๋ธŒ๋žœ์น˜ A์— ํฌํ•จ๋œ ์ปค๋ฐ‹ ์ค‘ ๋‹ค๋ฅธ ๋ธŒ๋žœ์น˜(๋ธŒ๋žœ์น˜ C)์˜ ์ปค๋ฐ‹๋“ค์ด ๋ฐ˜์˜๋  ์ˆ˜ ์žˆ๋‹ค.

์ด ๊ฒฝ์šฐ ์ž˜๋ชป ์ˆ˜ํ–‰ํ•œ ๋ณ‘ํ•ฉ ์ปค๋ฐ‹(๋˜๋Š” ์ฒด๋ฆฌํ”ฝ ์ปค๋ฐ‹) ๋ฐ”๋กœ ์ด์ „์˜ ์ปค๋ฐ‹(b2 ๋˜๋Š” a3)์œผ๋กœ ๋ฆฌ์…‹์„ ์ง„ํ–‰ํ•˜๊ณ  ์ƒˆ๋กœ์šด ๋ธŒ๋žœ์น˜๋กœ ์ฒดํฌ์•„์›ƒํ•œ ํ›„ ๋ณ‘ํ•ฉ ์ปค๋ฐ‹ ๋‹ค์Œ ์ปค๋ฐ‹๋“ค(b4, b5)์„ ์ฒด๋ฆฌํ”ฝํ•˜๋Š” ๋ฐฉ๋ฒ•์ด ์žˆ๋‹ค. ํ•˜์ง€๋งŒ ๋ณ‘ํ•ฉ ์ปค๋ฐ‹(b3)์ด c1 ์ปค๋ฐ‹๊ณผ ๋™์ผํ•œ ํŒŒ์ผ์„ ์ˆ˜์ •ํ•จ์œผ๋กœ์จ ๋ฐœ์ƒํ•˜๋Š” ๋ณ‘ํ•ฉ ์ถฉ๋Œ์„ ํ•ด๊ฒฐํ•œ ์ปค๋ฐ‹์ด๋ผ๋ฉด ์ดํ›„ ์ปค๋ฐ‹์„ ์ฒด๋ฆฌํ”ฝํ•  ๋•Œ ๋ณ‘ํ•ฉ ์ปค๋ฐ‹ ์ดํ›„ ์ปค๋ฐ‹์—๋Š” ์ด๋ฏธ ๋ธŒ๋žœ์น˜ B์— ๋ฐ˜์˜๋œ ๋ธŒ๋žœ์น˜ C์˜ ์ปค๋ฐ‹์œผ๋กœ ์ธํ•œ ์†Œ์Šค ์ฝ”๋“œ ๋ฐ˜์˜์ด ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ๋ณ‘ํ•ฉ ์ถฉ๋Œ์ด ๋ฐœ์ƒํ•  ์ˆ˜ ์žˆ์œผ๋ฉฐ ํ•ด๋‹น ์ปค๋ฐ‹(c1)์œผ๋กœ ์ธํ•œ ์†Œ์Šค ์ฝ”๋“œ ๋ฐ˜์˜์„ ์ œ๊ฑฐํ•˜๋Š” ๋ณ‘ํ•ฉ ์ถฉ๋Œ ํ•ด๊ฒฐ ๊ณผ์ •์ด ์ถ”๊ฐ€๋กœ ํ•„์š”ํ•˜๋‹ค.

Comments