1.1. A Friendly Conversation ¶
๋๋ถ๋ถ์ ์ธ์ด์๋ ์ํธ๊ฐ ์ด๋ฏธ ๊ตฌํ๋์ด ์๋ค. ๊ทธ๋ฐ๋ฐ ๊ผญ ์๋ก์ด ๋๋ง์ ์ํธ๋ฅผ ๋ง๋ค์ด์ผ ๋ ๋๊ฐ ์๋ค. ๋ ์ฝ๋๊ฐ ํ ์ฒ๋ง๊ฐ์ฏค ๋๋ค๊ณ ํ์.์ด๊ฒ์ ์ฐ๋ฆฌ๊ฐ ์๊ณ ์๋ ๋ฒ๋ธ์ํธ, ํต์ํธ ๊ฐ์ ๊ฒ์ผ๋ก ํ๊ธฐ์๋ ๋ฉ๋ชจ๋ฆฌ๊ฐ ๋ง์ด ๋ ๋ค. 32bit(4byte)์ ์ ์๋ผ๊ณ ํ๋ค๋ฉด, 40๋ฉ๊ฐ๋ฐ์ดํธ๊ฐ ํ์ํ๋ค. ํ์ง๋ง ์ด๋ค ์์
์ ํ ๋์, ์ฐ๋ฆฌ๊ฐ ์ํธ์ ํ ๋นํ ์ ์๋ ๊ณต๊ฐ์ 1๋ฉ๊ฐ ๋จ์ง์ด๋ผ๊ณ ๊ฐ์ ํ์. ์๊ฐ์ด ๋ง์ด ๊ฑธ๋ ค์๋ ์๋๋ค. ์ด๋ป๊ฒ ํด์ผ ํ ๊ฒ์ธ๊ฐ? ์ด ๋ ์ฝ๋๋ค์ 7์๋ฆฌ ์ ํ๋ฒํธ์ด๊ธฐ ๋๋ฌธ์ ๊ฐ์ ๊ฒ์ด ์๋ค๊ณ ํ๋ค.
1.2. Precise Problem Statement ¶
- ์
๋ ฅ : ๋ง์ ๋ด์ผ n๊ฐ์ ์ ์. ๊ฐ๊ฐ์ n์ ์ฒ๋ง๋ณด๋ค ์๋ค. ๋๊ฐ์ ์ซ์๊ฐ ๋๋ฒ์ด์ ๋์ค๋ฉด ์๋๋ค. ๊ทธ ์ซ์๋ ๊ด๋ จ๋ ๋ฐ์ดํฐ๊ฐ ์๋ค.
- ์ถ๋ ฅ : ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋ ์ซ์๋ค
- ์ ํ : ๋ฉ๋ชจ๋ฆฌ๋ฅผ 1๋ฉ๊ฐ ์ ๋๋ฐ์ ์ฌ์ฉํ ์ ์์. ๋์คํฌ ๊ณต๊ฐ ๋๋ํจ. ์ํ์๊ฐ์ด ์๋ถ์ ๋์ผ๋ฉด ์๋จ. 10์ด ์ ๋๋ฉด ๊ด์ฐฎ์.
1.3. Program Design ¶
์ฒจ์๋ ๋จธ์ง ์ํธ๋ฅผ ํ์๋๋ฐ ๋ฒ๋ ธ๋ค. ๋ค๋ฅธ ๋ฐฉ๋ฒ์ผ๋ก๋, ๊ฐ๊ฐ์ ์ซ์๋ฅผ 4byte๋ก ํํํ๋ฉด ํ์ฌ ๋ฉ๋ชจ๋ฆฌ์ 250,000๊ฐ๋ฅผ ๋ด์ ์ ์๋ค. 250000๊ฐ๋ฅผ ์ํธํ๊ณ , ๋ 250,000๊ฐ ์ฝ๊ณ ... ์ด๊ฑธ 40๋ฒ ํ๋ ๊ฑฐ๋ค. ๋จธ์ง ์ํธ๋ ์ค๊ฐ ์์
ํ์ผ์์ ์์ธ์ค๊ฐ ์์ฃผ ์ผ์ด๋๊ณ , ๋๋ฒ์งธ ๋ฐฉ๋ฒ์ ์
๋ ฅ์ 40๋ฒ์ ๋ฐ์์ผ ํ๋ค๋๊ฒ ๋ฌธ์ ๋ค. ์ด๊ฒ ๋๊ฐ์ง์ ์ฅ์ ์ ์ ์กฐํฉํด์ ์
๋ ฅ์ ํ๋ฒ, ์ค๊ฐ ์์
ํ์ผ์ด ์๊ฒ๋ ํ ์ ์์๊น?
1.4. Implementation Sketch ¶
๋นํธ๋งต, ํน์ ๋นํธ ๋ฒกํฐ๋ผ ๋ถ๋ฆฌ์ฐ๋ ๋ฐฉ๋ฒ์ด ์ ์ฉํ ๋ฏ ์ถ๋ค. ์๋ฅผ ๋ค์ด ๋งฅ์๋ฉ 10๋ฏธ๋ง์ ์ซ์๋ผ ํ ๋์, {1,2,3,5,8}์ ํํํด ๋ณด๋ฉด, (0 1 1 1 0 1 0 0 1 1)์ด ๋๋ค. ์์ผ๋ฉด 1, ์์ผ๋ฉด 0์ธ ๊ฒ์ด๋ค. ํ ์ซ์๋น 1๋นํธ๋ง ํ ๋น์ ํด์, ๊ทธ๊ฒ์ ์ธ๋ฑ์ค๋ก ์ฒ๋ฆฌ๋ฅผ ํ๋ ๊ฒ์ด๋ค. ์์์๋ ๋งํ๋ฏ์ด, ๋ฏธ๋๋ฉ๊ณผ ๋งฅ์๋ฉ์ ๋๋น๊ฐ ์๊ณ , ๊ฐ์ ์ซ์๊ฐ ์์ผ๋ฉฐ, ๊ด๋ จ๋ ๋ฐ์ดํฐ๊ฐ ์๋ค๋ ์ธก๋ฉด์์ ์ด ๋ฐฉ๋ฒ์ ์ธ ์ ์๋ ๊ฒ์ด๋ค. ๋๊ฐ์ ์ฝ๋๋ ๋ค์๊ณผ ๊ฐ๋ค.
~cpp # ๋ฐฐ์ด๊ฐ 0์ผ๋ก ์ ํ for b in bits: b=0 # ์์ผ๋ฉด 1 for e in inputFile: bits[e]=1 # 1์ธ๊ฒ๋ง ์ถ๋ ฅ for b in bits: if b==1: print b
1.5. Principles ¶
์ด๊ฒ์ ์ํ์๊ฐ์ ฮ(n)์ด๋ค. ์ด ์ฑํฐ๋ ๋ฌธ์ ๋ฅผ ์ฃผ์ ๊น๊ฒ ๋ถ์ํ๋ค ๋ณด๋ฉด, ๊ฐ๋ ์์ฒญ๋ ์ด๋์ ๊ฐ์ ธ๋ค ์ค๋๊ฐ ์๋ค๋ ๊ตํ์ ์ฃผ๊ณ ์๋ค. ๋ฌธ์ ์ ์๋ ๋ฌธ์ ํ์ด์ 90ํ๋ก๋ค. ์ผ๋ฐ์ ์ผ๋ก ๋ง์ ๊ณต๊ฐ์ ์ฌ์ฉํ๋ฉด ์ ์ ์๊ฐ์ด ์์๋๋ค๊ณ ํ๋ค. ๊ทธ๋ฐ๋ฐ ๋นํธ๋งต ์ํธ๋ ์๊ฐ๋ ์ค๊ณ , ๊ณต๊ฐ๋ ์ค์ด๋ค์๋ฐ. ์ ์ ๋ฐ์ดํฐ๋ฅผ ๋ค๋ฃจ๋ ๊ฒ์, ๊ทธ๊ฒ์ ์ํํ๋ ๋ฐ์ ๋ ์ ์ ์๊ฐ์ด ๋ ๋ค๋ ๊ฒ์ด๋ค. ๊ทธ๋ฆฌ๊ณ ๋ฐ์ดํฐ๋ฅผ ๋์คํฌ์ ๋๊ธฐ ๋ณด๋ค๋ ๋ฉ๋ชจ๋ฆฌ ์์ ๋๋ ๊ฒ์ด ๋์คํฌ ์ก์ธ์ค ๊ฐ์ ์๊ฐ ๊ฑธ๋ฆฌ๋ ์ผ์ ์ค์ผ ์๊ฐ ์๋ ๊ฒ์ด๋ค. ํ๋ก๊ทธ๋จ์ ๊ฐ๋จํ๊ฒ ์ง์. ์ ์ง๋ณด์๋ ์ฝ๊ณ , ๊ฒฌ๊ณ ํ ๊ฒ์ด๋ค.
