MCP๋กœ ์—ฐ๊ฒฐ โ†’

๊ณ„์‚ฐ ์ž…๋ ฅ

ํ•œ ์ค„์— ํ•œ ํ–‰์”ฉ ์ž…๋ ฅํ•˜์„ธ์š”. ์—ด์€ ์‰ผํ‘œ ๋˜๋Š” ํƒญ์œผ๋กœ ๊ตฌ๋ถ„ํ•ฉ๋‹ˆ๋‹ค. ์…€์—๋Š” ์ˆซ์ž๋‚˜ ํ…์ŠคํŠธ๋ฅผ ๋„ฃ์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

1๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜๋Š” ์—ด ๋ฒˆํ˜ธ์ž…๋‹ˆ๋‹ค. 0์„ ์ž…๋ ฅํ•˜๋ฉด ์ •๋ ฌํ•˜์ง€ ์•Š๊ณ  ํ–‰ ํ•ฉ๊ณ„ ์—ด์„ ์ถ”๊ฐ€ํ•ฉ๋‹ˆ๋‹ค.

๊ณต์‹

๊ด‘๊ณ 

๊ฒฐ๊ณผ

์ •๋ ฌ๋œ ํ‘œ
Alice, 80, 30 Bob, 95, 22 Carol, 88, 41
ํ–‰ 3
์—ด 3
๋ชจ๋“œ sorted

์ด ๋„๊ตฌ์˜ ๊ธฐ๋Šฅ

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

์„ ํƒํ•œ ์—ด์„ ๊ธฐ์ค€์œผ๋กœ ์žฌ์ •๋ ฌ๋˜๋Š” ํ‘œ
์„ ํƒํ•œ ํ•œ ์—ด์„ ์ •๋ ฌ ํ‚ค๋กœ ์‚ฌ์šฉํ•ด ํ–‰์„ ๋‹ค์‹œ ์ •๋ ฌํ•ฉ๋‹ˆ๋‹ค.

์‚ฌ์šฉ ๋ฐฉ๋ฒ•

ํ…์ŠคํŠธ ์ƒ์ž์— ํ‘œ๋ฅผ ํ•œ ์ค„์— ํ•œ ํ–‰์”ฉ ์ž…๋ ฅํ•˜์„ธ์š”. ์ •๋ ฌ ๊ธฐ์ค€ ์—ด ๋ฒˆํ˜ธ์—๋Š” ์ •๋ ฌํ•˜๊ณ  ์‹ถ์€ ์—ด์˜ ๋ฒˆํ˜ธ๋ฅผ 1๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜๋Š” ๊ธฐ์ค€์œผ๋กœ ๋„ฃ์œผ๋ฉด ๋ฉ๋‹ˆ๋‹ค(์ฒซ ๋ฒˆ์งธ ์—ด์ด 1๋ฒˆ). ๊ทธ๋ฆฌ๊ณ  ์ž‘์€ ๊ฐ’ โ†’ ํฐ ๊ฐ’(์˜ค๋ฆ„์ฐจ์ˆœ) ๋˜๋Š” ํฐ ๊ฐ’ โ†’ ์ž‘์€ ๊ฐ’(๋‚ด๋ฆผ์ฐจ์ˆœ) ์ค‘ ํ•˜๋‚˜๋ฅผ ์„ ํƒํ•˜์„ธ์š”. ์—ด ๋ฒˆํ˜ธ์— 0์„ ์ž…๋ ฅํ•˜๋ฉด ์ •๋ ฌ์€ ํ•˜์ง€ ์•Š๋Š” ๋Œ€์‹ , ๊ฐ ํ–‰์˜ ์ˆซ์ž ์…€์„ ๋ชจ๋‘ ๋”ํ•œ ๊ฐ’์„ ๋‹ด์€ ํ–‰ ํ•ฉ๊ณ„ ์—ด์„ ๋งจ ๋์— ์ถ”๊ฐ€ํ•ฉ๋‹ˆ๋‹ค.

$$\text{SortedTable} = \operatorname{sort}_{\;\uparrow}\Big(\text{Rows},\; \text{col} = \text{Column No.}\Big)$$

$$\text{SortedTable} = \operatorname{sort}_{\;\downarrow}\Big(\text{Rows},\; \text{col} = \text{Column No.}\Big)$$

$$\text{Total}_{\text{row }i} = \sum_{j} \text{numeric cells}_{ij}\qquad(\text{Column No.} = 0)$$

๊ณ„์‚ฐ ์›๋ฆฌ

๊ฐ ํ–‰์˜ ์ •๋ ฌ ํ‚ค๋Š” \(c - 1\) ์œ„์น˜์˜ ์…€์ž…๋‹ˆ๋‹ค(\(c\)๊ฐ€ 1๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜๋Š” ๋ฒˆํ˜ธ์ด๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค). ์…€ ๊ฐ’์ด ์ˆซ์ž๋กœ ํ•ด์„๋˜๋ฉด ์ˆซ์ž๋กœ ๋น„๊ตํ•˜๊ณ , ๊ทธ๋ ‡์ง€ ์•Š์œผ๋ฉด ํ…์ŠคํŠธ๋กœ ๋น„๊ตํ•ฉ๋‹ˆ๋‹ค. ์ˆซ์ž์™€ ํ…์ŠคํŠธ๊ฐ€ ์„ž์ธ ์—ด์—์„œ๋Š” ์ˆซ์ž๊ฐ€ ํ…์ŠคํŠธ๋ณด๋‹ค ์•ž์— ์˜ต๋‹ˆ๋‹ค. ์•ˆ์ • ์ •๋ ฌ(stable sort)์„ ์‚ฌ์šฉํ•˜๋ฏ€๋กœ, ํ‚ค๊ฐ€ ๊ฐ™์€ ํ–‰๋“ค์€ ์›๋ž˜์˜ ์ˆœ์„œ๋ฅผ ๊ทธ๋Œ€๋กœ ์œ ์ง€ํ•ฉ๋‹ˆ๋‹ค. ๋นˆ ์…€์€ ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์œผ๋กœ ์ทจ๊ธ‰๋˜์–ด ์˜ค๋ฆ„์ฐจ์ˆœ์ผ ๋•Œ ๋งจ ์œ„๋กœ ์˜ฌ๋ผ์˜ต๋‹ˆ๋‹ค.

๊ฐ™์€ ํ‚ค์˜ ์›๋ž˜ ์ˆœ์„œ๋ฅผ ์œ ์ง€ํ•˜๋Š” ์•ˆ์ • ์ •๋ ฌ
์•ˆ์ • ์ •๋ ฌ์€ ๊ฐ™์€ ํ‚ค ๊ฐ’์„ ๊ฐ€์ง„ ํ–‰์˜ ์›๋ž˜ ์ˆœ์„œ๋ฅผ ์œ ์ง€ํ•ฉ๋‹ˆ๋‹ค.

์˜ˆ์‹œ๋กœ ๋ณด๊ธฐ

์ด๋ฆ„, ์ ์ˆ˜, ๋‚˜์ด ์„ธ ์—ด๋กœ ์ด๋ฃจ์–ด์ง„ ๋‹ค์Œ ์„ธ ํ–‰์ด ์žˆ๋‹ค๊ณ  ํ•ด ๋ด…์‹œ๋‹ค:
Alice, 80, 30
Bob, 95, 22
Carol, 88, 41
2๋ฒˆ ์—ด(์ ์ˆ˜)์„ ๊ธฐ์ค€์œผ๋กœ ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌํ•˜๋ฉด ํ‚ค ๊ฐ’์ด \(80, 88, 95\) ์ˆœ์„œ๊ฐ€ ๋˜์–ด ๊ฒฐ๊ณผ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค:
Alice, 80, 30
Carol, 88, 41
Bob, 95, 22
๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ๋ฐ”๊พธ๋ฉด ์ˆœ์„œ๊ฐ€ ๋’ค์ง‘ํ˜€ Bob, Carol, Alice๊ฐ€ ๋ฉ๋‹ˆ๋‹ค.

์ž์ฃผ ๋ฌป๋Š” ์งˆ๋ฌธ

ํ•œ ์—ด์— ์ˆซ์ž์™€ ํ…์ŠคํŠธ๊ฐ€ ์„ž์—ฌ ์žˆ์œผ๋ฉด ์–ด๋–ป๊ฒŒ ๋˜๋‚˜์š”? ์ˆซ์ž ์…€์€ ์ˆซ์ž๋กœ ์ •๋ ฌ๋˜์–ด ์•ž์ชฝ์— ๋†“์ด๊ณ , ๊ทธ ๋’ค์— ํ…์ŠคํŠธ ์…€์ด ์•ŒํŒŒ๋ฒณ ์ˆœ์œผ๋กœ ์ •๋ ฌ๋ฉ๋‹ˆ๋‹ค.

๋ฒ”์œ„๋ฅผ ๋ฒ—์–ด๋‚œ ์—ด ๋ฒˆํ˜ธ๋ฅผ ์ž…๋ ฅํ•˜๋ฉด ์–ด๋–ป๊ฒŒ ๋˜๋‚˜์š”? ์—ด ๋ฒˆํ˜ธ๊ฐ€ ์‹ค์ œ ์—ด ๊ฐœ์ˆ˜๋ณด๋‹ค ํฌ๋ฉด, ํ‘œ๋Š” ๋ณ€๊ฒฝ ์—†์ด ๊ทธ๋Œ€๋กœ ๋ฐ˜ํ™˜๋ฉ๋‹ˆ๋‹ค.

์ค‘๋ณต๋œ ๊ฐ’๋„ ์•ˆ์ „ํ•˜๊ฒŒ ์ฒ˜๋ฆฌ๋˜๋‚˜์š”? ๋„ค. ์•ˆ์ • ์ •๋ ฌ์„ ์‚ฌ์šฉํ•˜๋ฏ€๋กœ ๊ฐ™์€ ํ‚ค๋ฅผ ๊ฐ€์ง„ ํ–‰๋“ค์˜ ์›๋ž˜ ์ƒ๋Œ€ ์ˆœ์„œ๊ฐ€ ๊ทธ๋Œ€๋กœ ์œ ์ง€๋ฉ๋‹ˆ๋‹ค.

์ตœ์ข… ์—…๋ฐ์ดํŠธ: