๐ ๋ฌธ์ ์ค๋ช
์๋
์ ์ด์ด ์๋ก์ด ๋ฌธ์์ด ๊ฒ์์ด ์๋ค. ๊ฒ์์ ์งํ ๋ฐฉ์์ ์๋์ ๊ฐ๋ค.์ํ๋ฒณ ์๋ฌธ์๋ก ์ด๋ฃจ์ด์ง ๋ฌธ์์ด W๊ฐ ์ฃผ์ด์ง๋ค.์์ ์ ์ K๊ฐ ์ฃผ์ด์ง๋ค.์ด๋ค ๋ฌธ์๋ฅผ ์ ํํ K๊ฐ๋ฅผ ํฌํจํ๋ ๊ฐ์ฅ ์งง์ ์ฐ์ ๋ฌธ์์ด์ ๊ธธ์ด๋ฅผ ๊ตฌํ๋ค.์ด๋ค ๋ฌธ์๋ฅผ ์ ํํ K๊ฐ๋ฅผ ํฌํจํ๊ณ , ๋ฌธ์์ด์ ์ฒซ ๋ฒ์งธ์ ๋ง์ง๋ง ๊ธ์๊ฐ ํด๋น ๋ฌธ์๋ก ๊ฐ์ ๊ฐ์ฅ ๊ธด ์ฐ์ ๋ฌธ์์ด์ ๊ธธ์ด๋ฅผ ๊ตฌํ๋ค.์์ ๊ฐ์ ๋ฐฉ์์ผ๋ก ๊ฒ์์ Tํ ์งํํ๋ค. ๐ ์
๋ ฅ ๋ฌธ์์ด ๊ฒ์์ ์ T๊ฐ ์ฃผ์ด์ง๋ค. (1 โค T โค 100)๋ค์ ์ค๋ถํฐ 2๊ฐ์ ์ค ๋์ ๋ฌธ์์ด W์ ์ ์ K๊ฐ ์ฃผ์ด์ง๋ค. (1 โค K โค |W| โค 10,000) ๐ ์ถ๋ ฅ T๊ฐ์ ์ค ๋์ ๋ฌธ์์ด ๊ฒ์์ 3๋ฒ๊ณผ 4๋ฒ์์ ๊ตฌํ ์ฐ์ ๋ฌธ์์ด์ ๊ธธ์ด๋ฅผ ๊ณต๋ฐฑ์ ์ฌ์ด์ ๋๊ณ ์ถ๋ ฅํ๋ค.๋ง์ฝ ๋ง์กฑํ๋ ์ฐ์ ..
๐ ๋ฌธ์ ์ค๋ช
N๊ฐ์ ๋์๊ฐ ์๋ค. ๊ทธ๋ฆฌ๊ณ ํ ๋์์์ ์ถ๋ฐํ์ฌ ๋ค๋ฅธ ๋์์ ๋์ฐฉํ๋ M๊ฐ์ ๋ฒ์ค๊ฐ ์๋ค. ์ฐ๋ฆฌ๋ A๋ฒ์งธ ๋์์์ B๋ฒ์งธ ๋์๊น์ง ๊ฐ๋๋ฐ ๋๋ ๋ฒ์ค ๋น์ฉ์ ์ต์ํ ์ํค๋ ค๊ณ ํ๋ค. A๋ฒ์งธ ๋์์์ B๋ฒ์งธ ๋์๊น์ง ๊ฐ๋๋ฐ ๋๋ ์ต์๋น์ฉ์ ์ถ๋ ฅํ์ฌ๋ผ. ๋์์ ๋ฒํธ๋ 1๋ถํฐ N๊น์ง์ด๋ค. ๐ ์
๋ ฅ ์ฒซ์งธ ์ค์ ๋์์ ๊ฐ์ N(1 โค N โค 1,000)์ด ์ฃผ์ด์ง๊ณ ๋์งธ ์ค์๋ ๋ฒ์ค์ ๊ฐ์ M(1 โค M โค 100,000)์ด ์ฃผ์ด์ง๋ค. ๊ทธ๋ฆฌ๊ณ ์
์งธ ์ค๋ถํฐ M+2์ค๊น์ง ๋ค์๊ณผ ๊ฐ์ ๋ฒ์ค์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค. ๋จผ์ ์ฒ์์๋ ๊ทธ ๋ฒ์ค์ ์ถ๋ฐ ๋์์ ๋ฒํธ๊ฐ ์ฃผ์ด์ง๋ค. ๊ทธ๋ฆฌ๊ณ ๊ทธ ๋ค์์๋ ๋์ฐฉ์ง์ ๋์ ๋ฒํธ๊ฐ ์ฃผ์ด์ง๊ณ ๋ ๊ทธ ๋ฒ์ค ๋น์ฉ์ด ์ฃผ์ด์ง๋ค. ๋ฒ์ค ๋น์ฉ์ 0๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 100,000๋ณด๋ค ์์ ์ ..
๐ ๋ฌธ์ ์ค๋ช
ํ์๋ ํฌ๊ธฐ๊ฐ 2N ร 2N์ธ 2์ฐจ์ ๋ฐฐ์ด์ Z๋ชจ์์ผ๋ก ํ์ํ๋ ค๊ณ ํ๋ค. ์๋ฅผ ๋ค์ด, 2ร2๋ฐฐ์ด์ ์ผ์ชฝ ์์นธ, ์ค๋ฅธ์ชฝ ์์นธ, ์ผ์ชฝ ์๋์นธ, ์ค๋ฅธ์ชฝ ์๋์นธ ์์๋๋ก ๋ฐฉ๋ฌธํ๋ฉด Z๋ชจ์์ด๋ค. N > 1์ธ ๊ฒฝ์ฐ, ๋ฐฐ์ด์ ํฌ๊ธฐ๊ฐ 2 ^ N-1 ร 2 ^ N-1๋ก 4๋ฑ๋ถ ํ ํ์ ์ฌ๊ท์ ์ผ๋ก ์์๋๋ก ๋ฐฉ๋ฌธํ๋ค.๋ค์ ์๋ 2^2 ร 2^2 ํฌ๊ธฐ์ ๋ฐฐ์ด์ ๋ฐฉ๋ฌธํ ์์์ด๋ค. N์ด ์ฃผ์ด์ก์ ๋, rํ c์ด์ ๋ช ๋ฒ์งธ๋ก ๋ฐฉ๋ฌธํ๋์ง ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.๋ค์์ N=3์ผ ๋์ ์์ด๋ค. ๐ ์
๋ ฅ ์ฒซ์งธ ์ค์ ์ ์ N, r, c๊ฐ ์ฃผ์ด์ง๋ค. ๐ ์ถ๋ ฅ rํ c์ด์ ๋ช ๋ฒ์งธ๋ก ๋ฐฉ๋ฌธํ๋์ง ์ถ๋ ฅํ๋ค. ๐ซ ์ ํ์ฌํญ1 โค N โค 150 โค r, c ์๊ฐ์ ํ : 0.5 sโค๏ธ ๋ฌธ์ ํ์ด ๋ฐฉ๋ฒ 1๏ธโฃ while ๋ฐ..
์ค๋๋ง์ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํ์ด๋ฅผ ๋ค์ ๋ธ๋ก๊ทธ์ ์ฌ๋ฆฌ๊ฒ ๋ ์ด์ ๊ฐ ๋๊ฐ์ง ์๋ค.์ฒซ๋ฒ์งธ๋ก, ๋ฌธ์ ํ๊ณ ๋ ๋์ ์ฝ๋๋ฅผ ์ฐพ์๋ณด๊ฑฐ๋ ๊ณ ๋ฏผํ๋ ์๊ฐ์ด ๋ถ์กฑํ ๊ฒ ๊ฐ์์์ด๋ค. ๊ณจ๋ ๋ฌธ์ ๋ก ์ฌ๋ผ์ค๋๊น ํ ๋ฌธ์ ํ์ด์๋ ์ค๋ ๊ฑธ๋ ค์, ๋ฌธ์ ๋ฅผ ํ๊ณ ๋ ๋ค์ ์๊ฐ์ ๋ง์ด ์๋ค์ด๊ฒ ๋์๋ค.๊ทธ๋ฌ๋ค๋ณด๋ ๋ฌธ์ ํ์ด ๋ฐฉ์๋ ํ์ ์ ์ด๊ณ ๋ ํฐ์ด ๋์์ง๋ฉด ๋ชป ํธ๋ ๋ฌธ์ ๊ฐ ๋๋ฌด ๋ง์์ง ๊ฒ ๊ฐ์๋ค.์ฌ๋ฌ ๋ฐฉ์์ ๋ฌธ์ ํ์ด๋ฅผ ์งํํ๊ณ ๋ธ๋ก๊ทธ์ ์ฌ๋ฆฌ๋ฉด ๋๋ ์ ๋๋ก ์ดํดํ๊ณ ๋์ด๊ฐ ๊ฒ ๊ฐ๋ค๋ ๊ฒ ์ฒซ๋ฒ์งธ ์ด์ ๋ค. ๋๋ฒ์งธ๋ก, ๋ณ์๋ช
์ ์ข ๋ ์ ๊ฒฝ ์ฐ๊ณ ์ถ์ด์ก๋ค. ๋ถํธ์บ ํ ๋ค๋๋ฉด์ ๋ฌธ์ ํ ๋๋ ๊ทธ๋ ๊ณ ํ๋ก์ ํธ ํ ๋๋ ์ฌ์ค ๋ณ์๋ช
์ ํฌ๊ฒ ์ ๊ฒฝ์ ์์ผ๋ ๊ฒ ๊ฐ๋ค.ํ๋ฒ ํ๊ณ ๋ง ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ๋ ํนํ.๊ทธ๋ฆฌ๊ณ ๋ณ์๋ช
์ด ๊ธธ๋ฉด ์๋๋ค๋ ๊ฐ๋ฐ๊ฐ์ ๊ฒ ์์๋๋ฐ, ..
'๐ algorithm' ์นดํ
๊ณ ๋ฆฌ์ ๊ธ ๋ชฉ๋ก
๋จ์ถํค
๋ด ๋ธ๋ก๊ทธ
๋ด ๋ธ๋ก๊ทธ - ๊ด๋ฆฌ์ ํ ์ ํ |
Q
Q
|
์ ๊ธ ์ฐ๊ธฐ |
W
W
|
๋ธ๋ก๊ทธ ๊ฒ์๊ธ
๊ธ ์์ (๊ถํ ์๋ ๊ฒฝ์ฐ) |
E
E
|
๋๊ธ ์์ญ์ผ๋ก ์ด๋ |
C
C
|
๋ชจ๋ ์์ญ
์ด ํ์ด์ง์ URL ๋ณต์ฌ |
S
S
|
๋งจ ์๋ก ์ด๋ |
T
T
|
ํฐ์คํ ๋ฆฌ ํ ์ด๋ |
H
H
|
๋จ์ถํค ์๋ด |
Shift + /
โง + /
|
* ๋จ์ถํค๋ ํ๊ธ/์๋ฌธ ๋์๋ฌธ์๋ก ์ด์ฉ ๊ฐ๋ฅํ๋ฉฐ, ํฐ์คํ ๋ฆฌ ๊ธฐ๋ณธ ๋๋ฉ์ธ์์๋ง ๋์ํฉ๋๋ค.