트리 분할

N\uAC1C\uC758 \uC815\uC810\uACFC \uAC00\uC911\uCE58\uAC00 \uC788\uB294 N-1\uAC1C\uC758 \uAC04\uC120\uC73C\uB85C \uC774\uB8E8\uC5B4\uC9C4 \uD2B8\uB9AC\uAC00 \uC788\uB2E4. \uC790\uC5F0\uC218 K\uAC00 \uC8FC\uC5B4\uC9C4\uB2E4. \uB2E8, K\uB294 N\uBCF4\uB2E4 \uC791\uB2E4.

\uC815\uC810 K\uAC1C\uB97C \uACE8\uB77C \uADF8 \uC815\uC810\uB4E4 \uC0AC\uC774\uC5D0 \uC874\uC7AC\uD558\uB294 \uC6D0\uB798 \uD2B8\uB9AC\uC758 \uAC04\uC120\uB9CC\uC73C\uB85C \uCCAB \uBC88\uC9F8 \uADF8\uB798\uD504\uB97C \uB9CC\uB4E4\uACE0, \uB098\uBA38\uC9C0 N-K\uAC1C \uC815\uC810\uB4E4 \uC0AC\uC774\uC5D0 \uC874\uC7AC\uD558\uB294 \uC6D0\uB798 \uD2B8\uB9AC\uC758 \uAC04\uC120\uB9CC\uC73C\uB85C \uB450 \uBC88\uC9F8 \uADF8\uB798\uD504\uB97C \uB9CC\uB4E0\uB2E4. \uC120\uD0DD\uD55C \uC815\uC810\uACFC \uC120\uD0DD\uD558\uC9C0 \uC54A\uC740 \uC815\uC810\uC744 \uC787\uB294 \uAC04\uC120\uC740 \uC5B4\uB290 \uADF8\uB798\uD504\uC5D0\uB3C4 \uD3EC\uD568\uB418\uC9C0 \uC54A\uB294\uB2E4.

<\uADF8\uB9BC 1>

\uC608\uB97C \uB4E4\uC5B4 <\uADF8\uB9BC 1>\uACFC \uAC19\uC740 7\uAC1C \uC815\uC810\uC758 \uD2B8\uB9AC\uC5D0\uC11C 1\uBC88\uACFC 2\uBC88 \uC815\uC810\uC744 \uACE0\uB974\uBA74 <\uADF8\uB9BC 2>\uC758 (A)\uC640 \uAC19\uC740 \uADF8\uB798\uD504\uAC00 \uB9CC\uB4E4\uC5B4\uC9C0\uACE0, \uB098\uBA38\uC9C0 \uC815\uC810\uB4E4\uB85C\uB294 <\uADF8\uB9BC 2>\uC758 (B)\uC640 \uAC19\uC740 \uADF8\uB798\uD504\uAC00 \uB9CC\uB4E4\uC5B4\uC9C4\uB2E4.

<\uADF8\uB9BC 2>

\uB610 <\uADF8\uB9BC 1>\uC758 \uD2B8\uB9AC\uC5D0\uC11C 3\uBC88\uACFC 4\uBC88 \uC815\uC810\uC744 \uACE0\uB974\uBA74, \uB9C8\uCC2C\uAC00\uC9C0\uB85C <\uADF8\uB9BC 3>\uC758 (A), (B)\uC640 \uAC19\uC740 \uB450 \uADF8\uB798\uD504\uAC00 \uB9CC\uB4E4\uC5B4\uC9C4\uB2E4.

<\uADF8\uB9BC 3>

<\uADF8\uB9BC 2>\uC758 \uB450 \uADF8\uB798\uD504\uC5D0 \uD3EC\uD568\uB41C \uBAA8\uB4E0 \uAC04\uC120 \uAC00\uC911\uCE58\uC758 \uD569\uC740 10+20+10+25=65\uC774\uACE0, <\uADF8\uB9BC 3>\uC758 \uB450 \uADF8\uB798\uD504\uC5D0 \uD3EC\uD568\uB41C \uBAA8\uB4E0 \uAC04\uC120 \uAC00\uC911\uCE58\uC758 \uD569\uC740 10\uC774\uB2E4.

\uD2B8\uB9AC\uC758 \uC815\uBCF4\uC640 K\uAC00 \uC8FC\uC5B4\uC9C8 \uB54C, \uC704 \uBC29\uBC95\uC73C\uB85C \uC815\uC810 K\uAC1C\uB97C \uC120\uD0DD\uD558\uC5EC \uB9CC\uB4E4\uC5B4\uC9C0\uB294 \uB450 \uADF8\uB798\uD504\uC5D0 \uD3EC\uD568\uB41C \uBAA8\uB4E0 \uAC04\uC120 \uAC00\uC911\uCE58 \uD569\uC758 \uCD5C\uC19F\uAC12\uC744 \uAD6C\uD558\uB77C.

\uCCAB\uC9F8 \uC904\uC5D0 N\uACFC K\uAC00 \uACF5\uBC31\uC744 \uC0AC\uC774\uC5D0 \uB450\uACE0 \uC8FC\uC5B4\uC9C4\uB2E4. \uD2B8\uB9AC\uC758 \uC815\uC810\uC740 1\uBC88\uBD80\uD130 N\uBC88\uAE4C\uC9C0 \uBC88\uD638\uAC00 \uB9E4\uACA8\uC838 \uC788\uB2E4.

\uC774\uC5B4\uC9C0\uB294 N-1\uAC1C \uC904\uC5D0\uB294 \uAC04\uC120 \uD558\uB098\uC758 \uC815\uBCF4\uAC00 \uC8FC\uC5B4\uC9C4\uB2E4. \uAC01 \uC904\uC5D0\uB294 \uAC04\uC120\uC758 \uC591 \uB05D \uC815\uC810 \uBC88\uD638\uC640 \uAC00\uC911\uCE58\uAC00 \uACF5\uBC31\uC744 \uC0AC\uC774\uC5D0 \uB450\uACE0 \uCC28\uB840\uB85C \uC8FC\uC5B4\uC9C4\uB2E4.

N\uC740 1,000 \uC774\uD558\uC758 \uC790\uC5F0\uC218\uC774\uACE0, K\uB294 N\uBCF4\uB2E4 \uC791\uC740 \uC790\uC5F0\uC218\uC774\uB2E4. \uAC04\uC120\uC758 \uAC00\uC911\uCE58\uB294 1,000 \uC774\uD558\uC758 \uC790\uC5F0\uC218\uC774\uB2E4.

\uCCAB\uC9F8 \uC904\uC5D0 \uC815\uC810 K\uAC1C\uB97C \uC120\uD0DD\uD558\uC5EC \uB9CC\uB4E4\uC5B4\uC9C4 \uB450 \uADF8\uB798\uD504\uC5D0 \uD3EC\uD568\uB41C \uBAA8\uB4E0 \uAC04\uC120 \uAC00\uC911\uCE58 \uD569\uC758 \uCD5C\uC19F\uAC12\uC744 \uCD9C\uB825\uD55C\uB2E4.

\uB458\uC9F8 \uC904\uC5D0\uB294 \uADF8\uB54C \uC120\uD0DD\uD55C K\uAC1C \uC815\uC810\uC758 \uBC88\uD638\uB97C \uC624\uB984\uCC28\uC21C\uC73C\uB85C \uACF5\uBC31\uC744 \uC0AC\uC774\uC5D0 \uB450\uACE0 \uCD9C\uB825\uD55C\uB2E4. \uCD5C\uC801\uC758 \uC120\uD0DD\uC774 \uB458 \uC774\uC0C1\uC774\uBA74 \uADF8\uC911 \uC544\uBB34 \uD558\uB098\uB97C \uCD9C\uB825\uD55C\uB2E4.