์ด ๊ณ์ฐ๊ธฐ๋ ๋ฌด์์ ํด์ฃผ๋์
์น๊ตฌ๋ค๋ผ๋ฆฌ ์ฌํ์ ๊ฐ๋ฉด ํ ๋ช ์ ์์๋ฅผ ์์ฝํ๊ณ , ๋ค๋ฅธ ํ ๋ช ์ ๊ธฐ๋ฆ๊ฐ์ ๋ด๊ณ , ๋ ๋ค๋ฅธ ํ ๋ช ์ ์ ๋ ๊ฐ์ ๊ณ์ฐํ๊ธฐ ๋ง๋ จ์ ๋๋ค. ์ฌํ์ด ๋๋ ๋ฌด๋ ต์ ๊ฒฐ๊ตญ ๋๊ฐ ๋๊ตฌํํ ์ผ๋ง๋ฅผ ์ค์ผ ํ๋์ง ์๋ฌด๋ ๋ชจ๋ฅด๋ ์ํฉ์ด ๋ฒ์ด์ง์ฃ . ์ด ๋จ์ฒด ์ฌํ ๊ฒฝ๋น ๋ถ๋ฐฐ ๊ณ์ฐ๊ธฐ๋ ๋ชจ๋ ์ง์ถ์ ํฉ์ฐํด ์ธ์์๋๋ก ๋๊ฐ์ด ๋๋ ๋ค, ๋ชจ๋๊ฐ ๊ฒฐ๊ตญ ๊ฐ์ ๊ธ์ก์ ๋ถ๋ดํ๋๋ก ๊ฐ์ฅ ๊ฐ๋จํ ์ก๊ธ ๋ฐฉ๋ฒ์ ๊ณ์ฐํด ์ค๋๋ค.
์ฌ์ฉ ๋ฐฉ๋ฒ
๋จผ์ ์ผํ ์ธ์์๋ฅผ ์ ํ๊ณ , ๊ฐ์ ๊ณต๋ ๊ฒฝ๋น๋ก ์ค์ ๋ธ ๊ธ์ก์ ์ ๋ ฅํ์ธ์. ํ ํผ๋ ๋ด์ง ์์ ์ฌ๋์ 0์ผ๋ก ๋๋ฉด ๋ฉ๋๋ค. ๊ณ์ฐํ๊ธฐ๋ฅผ ๋๋ฅด๋ฉด 1์ธ๋น ๋ถ๋ดํด์ผ ํ ๊ธ์ก, ์ฌํ ์ด๋น์ฉ, ๊ทธ๋ฆฌ๊ณ "A๊ฐ B์๊ฒ X์ ์ก๊ธ" ํํ์ ์ ์ฐ ๋ชฉ๋ก์ด ๋์ต๋๋ค. ์ด ๋ชฉ๋ก์ ์ต์ํ์ ์ก๊ธ ํ์๋ก ๋ชจ๋์ ์ ์ฐ์ ๋๋ผ ์ ์๋๋ก ์ ๋ฆฌ๋ฉ๋๋ค.
๊ณ์ฐ ๊ณต์ ์ค๋ช
๋จผ์ ๊ฐ์๊ฐ ๋ถ๋ดํด์ผ ํ ๊ณต์ ํ ๋ชซ์ ๊ตฌํฉ๋๋ค: $$\text{1์ธ๋น ๋ชซ} = \frac{\text{์ด์ง์ถ}}{\text{์ธ์์}}$$. ๊ทธ๋ค์ ๊ฐ์์ ์์ก์ ๊ณ์ฐํฉ๋๋ค: $$\text{์์ก} = \text{์ค์ ๋ธ ๊ธ์ก} - \text{1์ธ๋น ๋ชซ}$$. ์์ก์ด ์์์ด๋ฉด ๋ ๋ง์ด ๋์ผ๋ ๋๋ ค๋ฐ์ ์ฌ๋์ด๊ณ , ์์์ด๋ฉด ์ ๊ฒ ๋์ผ๋ ๋ณดํ์ผ ํ ์ฌ๋์ ๋๋ค. ๊ทธ๋ฆฌ๋(greedy) ๋งค์นญ ์๊ณ ๋ฆฌ์ฆ์ด ๊ฐ์ฅ ๋ง์ด ๋ฐ์ ์ฌ๋๊ณผ ๊ฐ์ฅ ๋ง์ด ์ค์ผ ํ ์ฌ๋์ ์ฐจ๋ก๋ก ์ฐ๊ฒฐํด ๋ชจ๋ ์์ก์ด 0์ด ๋ ๋๊น์ง ์ก๊ธ์ ๋ฐฐ์ ํ๋ฏ๋ก, ์ก๊ธ ํ์๊ฐ ์์ฐ์ค๋ฝ๊ฒ ์ต์ํ๋ฉ๋๋ค.
์์๋ก ๋ณด๊ธฐ
์น๊ตฌ ์ธ ๋ช ์ด ์ฌํ์ ๊ฐ๋ค๊ณ ํด๋ด ์๋ค. 1๋ฒ์ \($120\), 2๋ฒ์ \($30\), 3๋ฒ์ \($0\)๋ฅผ ๋์ต๋๋ค. ์ดํฉ์ \($150\)์ด๋ฏ๋ก ๊ฐ์ ๋ถ๋ดํด์ผ ํ ๊ธ์ก์ $$\frac{150}{3} = 50$$ ๋ฌ๋ฌ์ ๋๋ค. ์์ก์ ๊ฐ๊ฐ \(+$70\), \(-$20\), \(-$50\)๊ฐ ๋ฉ๋๋ค. 3๋ฒ์ด 1๋ฒ์๊ฒ \($50\)์, 2๋ฒ์ด 1๋ฒ์๊ฒ \($20\)์ ๋ณด๋ด๋ฉด, ์ด์ ๋ชจ๋๊ฐ ์ฌ์ค์ \($50\)์ฉ ๋ถ๋ดํ ์ ์ด ๋ฉ๋๋ค.
์์ฃผ ๋ฌป๋ ์ง๋ฌธ
๊ฒฝ๋น๋ฅผ ์ฐจ๋ฑ ๋ถ๋ฐฐํ ์๋ ์๋์? ์๋์. ์ด ๋ฒ์ ์ ์ด๋น์ฉ์ ์ธ์์๋๋ก ๋๊ฐ์ด ๋๋๋๋ค. ๊ฒฐ๊ตญ ๋ชจ๋๊ฐ ๋์ผํ ๊ธ์ก์ ๋ถ๋ดํ๊ฒ ๋ฉ๋๋ค.
์ด๋ค ํตํ๋ฅผ ์ฌ์ฉํ๋์? ํน์ ํตํ์ ๊ตฌ์ ๋ฐ์ง ์์ต๋๋ค. ๋ชจ๋ ํญ๋ชฉ์ ๊ฐ์ ํตํ๋ง ์ผ๊ด๋๊ฒ ์ฌ์ฉํ๋ฉด ์ํ๋ ๋ฌ๋ฌ๋ ์๊ด์์ต๋๋ค.
์ ์ก๊ธ ํ์๋ฅผ ์ต์ํํ๋์? ์ก๊ธ์ด ์ ์์๋ก ๋ฒ๊ฑฐ๋ก์๋ ์ค์ด๋ค๊ธฐ ๋๋ฌธ์ ๋๋ค. ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ๊ฐ์ฅ ๋ง์ด ๋ฐ์ ์ฌ๋๊ณผ ๊ฐ์ฅ ๋ง์ด ์ค ์ฌ๋์ ์ง์ง์ด, ๋์ด ์ค๊ฐ๋ ํ์๋ฅผ ์ต๋ํ ์ค์ฌ ์ค๋๋ค.