์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- ์ฐ์ ์์ํ
- ๋์ ๊ณํ๋ฒ
- ๊น์ด์ฐ์ ํ์
- ์๋ฃ๊ตฌ์กฐ
- ์์ํ์
- ๊ทธ๋ฆฌ๋
- ์ ๋ ฌ
- DFS
- ๊ตฌํ
- 11650
- ๋๋น์ฐ์ ํ์
- ์ํ
- SQL
- ๊ทธ๋ํํ์
- LIS
- BFS
- Side Menu
- ๊ทธ๋ํ์ํ๋ฌธ์
- ๊ทธ๋ํ
- ํ๋ก์ด๋์์ฌ
- ๋ฐ์ดํฐ๋ฒ ์ด์ค
- ๋จธ์ง์ํธ
- ์์๊ตฌํ๊ธฐ
- ๋ณํฉ์ ๋ ฌ
- db
- ์๊ณ ๋ฆฌ์ฆ
- ํ๋ก๊ทธ๋๋จธ์ค
- DP
- ๋ค์ด๋๋ฏนํ๋ก๊ทธ๋๋ฐ
- ๋ฐฑ์ค
๋ชฉ๋ก์ฝ๋ฉํ ์คํธ ์ค๋น (77)
๐๐ญ๐ฐ๐ธ ๐ฃ๐ถ๐ต ๐ด๐ต๐ฆ๐ข๐ฅ๐บ
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cs91lg/btraVFkXuhO/Ix6BgQLTOzPRRG8HWWQSX1/img.png)
๋ฌธ์ ์ค๋ฅธ์ชฝ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ์ผ๊ฐํ์ด ๋์ ๋ชจ์์ผ๋ก ๋์ฌ์ ธ ์๋ค. ์ฒซ ์ผ๊ฐํ์ ์ ์ผ๊ฐํ์ผ๋ก ๋ณ์ ๊ธธ์ด๋ 1์ด๋ค. ๊ทธ ๋ค์์๋ ๋ค์๊ณผ ๊ฐ์ ๊ณผ์ ์ผ๋ก ์ ์ผ๊ฐํ์ ๊ณ์ ์ถ๊ฐํ๋ค. ๋์ ์์ ๊ฐ์ฅ ๊ธด ๋ณ์ ๊ธธ์ด๋ฅผ k๋ผ ํ์ ๋, ๊ทธ ๋ณ์ ๊ธธ์ด๊ฐ k์ธ ์ ์ผ๊ฐํ์ ์ถ๊ฐํ๋ค. ํ๋๋ฐ ์์ด P(N)์ ๋์ ์ ์๋ ์ ์ผ๊ฐํ์ ๋ณ์ ๊ธธ์ด์ด๋ค. P(1)๋ถํฐ P(10)๊น์ง ์ฒซ 10๊ฐ ์ซ์๋ 1, 1, 1, 2, 2, 3, 4, 5, 7, 9์ด๋ค. N์ด ์ฃผ์ด์ก์ ๋, P(N)์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์ T๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ ์คํธ ์ผ์ด์ค๋ ํ ์ค๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ , N์ด ์ฃผ์ด์ง๋ค. (1 ≤ N ≤ 100) ์ถ๋ ฅ ๊ฐ ํ ์คํธ ์ผ์ด์ค๋ง๋ค P(N)์ ์ถ๋ ฅํ๋ค. DP๋ฅผ ์ด์ฉํ์ฌ ํ ์ ์๋ ๋ฌธ์ . ์๊ฐ..
๋ฌธ์ ์ด๋ค ์์ฐ์ N์ ๊ทธ๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์ ๊ณฑ์๋ค์ ํฉ์ผ๋ก ๋ํ๋ผ ์ ์๋ค. ์๋ฅผ ๋ค์ด 11=32+12+12(3๊ฐ ํญ)์ด๋ค. ์ด๋ฐ ํํ๋ฐฉ๋ฒ์ ์ฌ๋ฌ ๊ฐ์ง๊ฐ ๋ ์ ์๋๋ฐ, 11์ ๊ฒฝ์ฐ 11=22+22+12+12+12(5๊ฐ ํญ)๋ ๊ฐ๋ฅํ๋ค. ์ด ๊ฒฝ์ฐ, ์ํ์ ์ํฌ๋ผํ ์ค๋ “11์ 3๊ฐ ํญ์ ์ ๊ณฑ์ ํฉ์ผ๋ก ํํํ ์ ์๋ค.”๋ผ๊ณ ๋งํ๋ค. ๋ํ 11์ ๊ทธ๋ณด๋ค ์ ์ ํญ์ ์ ๊ณฑ์ ํฉ์ผ๋ก ํํํ ์ ์์ผ๋ฏ๋ก, 11์ ๊ทธ ํฉ์ผ๋ก์จ ํํํ ์ ์๋ ์ ๊ณฑ์ ํญ์ ์ต์ ๊ฐ์๋ 3์ด๋ค. ์ฃผ์ด์ง ์์ฐ์ N์ ์ด๋ ๊ฒ ์ ๊ณฑ์๋ค์ ํฉ์ผ๋ก ํํํ ๋์ ๊ทธ ํญ์ ์ต์๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ ์์ฐ์ N์ด ์ฃผ์ด์ง๋ค. (1 ≤ N ≤ 100,000) ์ถ๋ ฅ ์ฃผ์ด์ง ์์ฐ์๋ฅผ ์ ๊ณฑ์์ ํฉ์ผ๋ก ๋ํ๋ผ ๋์ ๊ทธ ์ ๊ณฑ์ ..
๋ฌธ์ ์์ด S๊ฐ ์ด๋ค ์ Sk๋ฅผ ๊ธฐ์ค์ผ๋ก S1 Sk+1 > ... SN-1 > SN์ ๋ง์กฑํ๋ค๋ฉด, ๊ทธ ์์ด์ ๋ฐ์ดํ ๋ ์์ด์ด๋ผ๊ณ ํ๋ค. ์๋ฅผ ๋ค์ด, {10, 20, 30, 25, 20}๊ณผ {10, 20, 30, 40}, {50, 40, 25, 10} ์ ๋ฐ์ดํ ๋ ์์ด์ด์ง๋ง, {1, 2, 3, 2, 1, 2, 3, 2, 1}๊ณผ {10, 20, 30, 40, 20, 30} ์ ๋ฐ์ดํ ๋ ์์ด์ด ์๋๋ค. ์์ด A๊ฐ ์ฃผ์ด์ก์ ๋, ๊ทธ ์์ด์ ๋ถ๋ถ ์์ด ์ค ๋ฐ์ดํ ๋ ์์ด์ด๋ฉด์ ๊ฐ์ฅ ๊ธด ์์ด์ ๊ธธ์ด๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ ์์ด A์ ํฌ๊ธฐ N์ด ์ฃผ์ด์ง๊ณ , ๋์งธ ์ค์๋ ์์ด A๋ฅผ ์ด๋ฃจ๊ณ ์๋ Ai๊ฐ ์ฃผ์ด์ง๋ค. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/b8yVj9/btrajOKQ2gn/1F1uuuZKjkaagmd0uglfM1/img.png)
๋ฌธ์ ์๊ทผ์ด์ ์ฌ๋์ ์๋ฅ์ด๋ ๋ฌธ๋ฐฉ๊ตฌ์์ ์คํฐ์ปค 2n๊ฐ๋ฅผ ๊ตฌ๋งคํ๋ค. ์คํฐ์ปค๋ ๊ทธ๋ฆผ (a)์ ๊ฐ์ด 2ํ n์ด๋ก ๋ฐฐ์น๋์ด ์๋ค. ์๋ฅ์ด๋ ์คํฐ์ปค๋ฅผ ์ด์ฉํด ์ฑ ์์ ๊พธ๋ฏธ๋ ค๊ณ ํ๋ค. ์๋ฅ์ด๊ฐ ๊ตฌ๋งคํ ์คํฐ์ปค์ ํ์ง์ ๋งค์ฐ ์ข์ง ์๋ค. ์คํฐ์ปค ํ ์ฅ์ ๋ผ๋ฉด, ๊ทธ ์คํฐ์ปค์ ๋ณ์ ๊ณต์ ํ๋ ์คํฐ์ปค๋ ๋ชจ๋ ์ฐข์ด์ ธ์ ์ฌ์ฉํ ์ ์๊ฒ ๋๋ค. ์ฆ, ๋ ์คํฐ์ปค์ ์ผ์ชฝ, ์ค๋ฅธ์ชฝ, ์, ์๋์ ์๋ ์คํฐ์ปค๋ ์ฌ์ฉํ ์ ์๊ฒ ๋๋ค. ๋ชจ๋ ์คํฐ์ปค๋ฅผ ๋ถ์ผ ์ ์๊ฒ๋ ์๋ฅ์ด๋ ๊ฐ ์คํฐ์ปค์ ์ ์๋ฅผ ๋งค๊ธฐ๊ณ , ์ ์์ ํฉ์ด ์ต๋๊ฐ ๋๊ฒ ์คํฐ์ปค๋ฅผ ๋ผ์ด๋ด๋ ค๊ณ ํ๋ค. ๋จผ์ , ๊ทธ๋ฆผ (b)์ ๊ฐ์ด ๊ฐ ์คํฐ์ปค์ ์ ์๋ฅผ ๋งค๊ฒผ๋ค. ์๋ฅ์ด๊ฐ ๋ ์ ์๋ ์คํฐ์ปค์ ์ ์์ ์ต๋๊ฐ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ฆ, 2n๊ฐ์ ์คํฐ์ปค ์ค์์ ์ ์์ ํฉ์ด ์ต๋๊ฐ ๋๋ฉด์ ..
๋ฌธ์ ์์ด A๊ฐ ์ฃผ์ด์ก์ ๋, ๊ฐ์ฅ ๊ธด ๊ฐ์ํ๋ ๋ถ๋ถ ์์ด์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์๋ฅผ ๋ค์ด, ์์ด A = {10, 30, 10, 20, 20, 10} ์ธ ๊ฒฝ์ฐ์ ๊ฐ์ฅ ๊ธด ๊ฐ์ํ๋ ๋ถ๋ถ ์์ด์ A = {10, 30, 10, 20, 20, 10} ์ด๊ณ , ๊ธธ์ด๋ 3์ด๋ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ ์์ด A์ ํฌ๊ธฐ N (1 ≤ N ≤ 1,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์๋ ์์ด A๋ฅผ ์ด๋ฃจ๊ณ ์๋ Ai๊ฐ ์ฃผ์ด์ง๋ค. (1 ≤ Ai ≤ 1,000) ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ์์ด A์ ๊ฐ์ฅ ๊ธด ๊ฐ์ํ๋ ๋ถ๋ถ ์์ด์ ๊ธธ์ด๋ฅผ ์ถ๋ ฅํ๋ค. DP๋ฅผ ์ด์ฉํ์ฌ ํ ์ ์๋ ๋ฌธ์ . ์ฌ์ค์ 11053๋ฒ ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด ๋ฌธ์ ์์ ๊ดํธ๋ง ๋ฐ๊พธ๋ฉด ํ ์ ์๋ ๋ฌธ์ ์ด๋ค. ์ค๋ช ์ ๋งํฌ ์ฐธ์กฐ. ์ ๊ทผ ๋ฐฉ์์ ๋ค์๊ณผ ๊ฐ๋ค. 1. A ๋ฐฐ์ด ๋ด์์ ..
๋ฌธ์ ์์ด A๊ฐ ์ฃผ์ด์ก์ ๋, ๊ทธ ์์ด์ ์ฆ๊ฐ ๋ถ๋ถ ์์ด ์ค์์ ํฉ์ด ๊ฐ์ฅ ํฐ ๊ฒ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์๋ฅผ ๋ค์ด, ์์ด A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} ์ธ ๊ฒฝ์ฐ์ ํฉ์ด ๊ฐ์ฅ ํฐ ์ฆ๊ฐ ๋ถ๋ถ ์์ด์ A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} ์ด๊ณ , ํฉ์ 113์ด๋ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ ์์ด A์ ํฌ๊ธฐ N (1 ≤ N ≤ 1,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์๋ ์์ด A๋ฅผ ์ด๋ฃจ๊ณ ์๋ Ai๊ฐ ์ฃผ์ด์ง๋ค. (1 ≤ Ai ≤ 1,000) ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ์์ด A์ ํฉ์ด ๊ฐ์ฅ ํฐ ์ฆ๊ฐ ๋ถ๋ถ ์์ด์ ํฉ์ ์ถ๋ ฅํ๋ค. DP๋ฅผ ์ด์ฉํ๋ ๋ฌธ์ ..์ด์ LIS ๋ฌธ์ ์ด๋ค. 11053๋ฒ ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด ๋ฌธ์ ์ ๋์ผํ๊ฒ ์์ ๋ณด๋ค ์์ ์กด์ฌํ๋ ๋ฐฐ์ด ๊ฐ ..
๋ฌธ์ ์์ด A๊ฐ ์ฃผ์ด์ก์ ๋, ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์๋ฅผ ๋ค์ด, ์์ด A = {10, 20, 10, 30, 20, 50} ์ธ ๊ฒฝ์ฐ์ ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ A = {10, 20, 10, 30, 20, 50} ์ด๊ณ , ๊ธธ์ด๋ 4์ด๋ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ ์์ด A์ ํฌ๊ธฐ N (1 ≤ N ≤ 1,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์๋ ์์ด A๋ฅผ ์ด๋ฃจ๊ณ ์๋ Ai๊ฐ ์ฃผ์ด์ง๋ค. (1 ≤ Ai ≤ 1,000) ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ์์ด A์ ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ ๊ธธ์ด๋ฅผ ์ถ๋ ฅํ๋ค. DP๋ฅผ ์ด์ฉํ์ฌ ํ ์ ์๋ ๋ฌธ์ . ์ฌํ๊น์ง ํ์๋ ๋ค๋ฅธ DP๋ฌธ์ ๋ค๊ณผ ์กฐ๊ธ ๋ค๋ฅด๊ฒ ์ ๊ทผํด์ผ๋ผ์ ์ด๋ ค์ ๋ ๋ฌธ์ ๊ฐ๋ค. ๊ฒ์ํด๋ณด๋ ์ด๋ฌํ ๋ฌธ์ ์ ํ์ LIS(Longest Increasing Subsequ..
๋ฌธ์ 0๊ณผ 1๋ก๋ง ์ด๋ฃจ์ด์ง ์๋ฅผ ์ด์ง์๋ผ ํ๋ค. ์ด๋ฌํ ์ด์ง์ ์ค ํน๋ณํ ์ฑ์ง์ ๊ฐ๋ ๊ฒ๋ค์ด ์๋๋ฐ, ์ด๋ค์ ์ด์น์(pinary number)๋ผ ํ๋ค. ์ด์น์๋ ๋ค์์ ์ฑ์ง์ ๋ง์กฑํ๋ค. ์ด์น์๋ 0์ผ๋ก ์์ํ์ง ์๋๋ค. ์ด์น์์์๋ 1์ด ๋ ๋ฒ ์ฐ์์ผ๋ก ๋ํ๋์ง ์๋๋ค. ์ฆ, 11์ ๋ถ๋ถ ๋ฌธ์์ด๋ก ๊ฐ์ง ์๋๋ค. ์๋ฅผ ๋ค๋ฉด 1, 10, 100, 101, 1000, 1001 ๋ฑ์ด ์ด์น์๊ฐ ๋๋ค. ํ์ง๋ง 0010101์ด๋ 101101์ ๊ฐ๊ฐ 1, 2๋ฒ ๊ท์น์ ์๋ฐฐ๋๋ฏ๋ก ์ด์น์๊ฐ ์๋๋ค. N(1 ≤ N ≤ 90)์ด ์ฃผ์ด์ก์ ๋, N์๋ฆฌ ์ด์น์์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ N์ด ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ N์๋ฆฌ ์ด์น์์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค. DP๋ฅผ ์ด์ฉํ์ฌ ํ ์ ์๋ ๋ฌธ์ . ์ด์น์๋ 0์ผ..
๋ฌธ์ ์ค๋ฅด๋ง ์๋ ์์ ์๋ฆฌ๊ฐ ์ค๋ฆ์ฐจ์์ ์ด๋ฃจ๋ ์๋ฅผ ๋งํ๋ค. ์ด๋, ์ธ์ ํ ์๊ฐ ๊ฐ์๋ ์ค๋ฆ์ฐจ์์ผ๋ก ์น๋ค. ์๋ฅผ ๋ค์ด, 2234์ 3678, 11119๋ ์ค๋ฅด๋ง ์์ด์ง๋ง, 2232, 3676, 91111์ ์ค๋ฅด๋ง ์๊ฐ ์๋๋ค. ์์ ๊ธธ์ด N์ด ์ฃผ์ด์ก์ ๋, ์ค๋ฅด๋ง ์์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์๋ 0์ผ๋ก ์์ํ ์ ์๋ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ N (1 ≤ N ≤ 1,000)์ด ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ๊ธธ์ด๊ฐ N์ธ ์ค๋ฅด๋ง ์์ ๊ฐ์๋ฅผ 10,007๋ก ๋๋ ๋๋จธ์ง๋ฅผ ์ถ๋ ฅํ๋ค. DP๋ฅผ ์ฌ์ฉํ์ฌ ํ ์ ์๋ ๋ฌธ์ . ์์ ํ์๋ 10844๋ฒ ์ฌ์ด ๊ณ๋จ์ ๋ฌธ์ ์ ๋น์ทํ๋ค. N = 1 ์ผ๋๋ 0๋ถํฐ 9๊น์ง(์๋ 0์ผ๋ก ์์ํ ์ ์์) 10๊ฐ์ง์ด๊ณ , N = 2 ์ผ๋๋ { 00, 01, ..., 11, 12..
๋ฌธ์ 45656์ด๋ ์๋ฅผ ๋ณด์. ์ด ์๋ ์ธ์ ํ ๋ชจ๋ ์๋ฆฌ์์ ์ฐจ์ด๊ฐ 1์ด ๋๋ค. ์ด๋ฐ ์๋ฅผ ๊ณ๋จ ์๋ผ๊ณ ํ๋ค. ์ธ์ค์ด๋ ์์ ๊ธธ์ด๊ฐ N์ธ ๊ณ๋จ ์๊ฐ ๋ช ๊ฐ ์๋์ง ๊ถ๊ธํด์ก๋ค. N์ด ์ฃผ์ด์ง ๋, ๊ธธ์ด๊ฐ N์ธ ๊ณ๋จ ์๊ฐ ์ด ๋ช ๊ฐ ์๋์ง ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. (0์ผ๋ก ์์ํ๋ ์๋ ์๋ค.) ์ ๋ ฅ ์ฒซ์งธ ์ค์ N์ด ์ฃผ์ด์ง๋ค. N์ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 100๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ์ ๋ต์ 1,000,000,000์ผ๋ก ๋๋ ๋๋จธ์ง๋ฅผ ์ถ๋ ฅํ๋ค. DP๋ฅผ ์ด์ฉํ์ฌ ํ ์ ์๋ ๋ฌธ์ . ๋ฌธ์ ์ด๋ฆ์ ์ฌ์ด ๊ณ๋จ์์ธ๋ฐ ํ๋๋ ์์ฝ๋ค. N = 1์ผ๋๋ 1๋ถํฐ 9๊น์ง(0์ ํฌํจํ์ง ์์) 9๊ฐ์ง๊ณ , N = 2์ผ๋๋ { 10, 12, 21, 23, 32, 34, ... , 89, 98 } (90์ ..