- Today
- Total
- database
- BFS
- spring
- ๋ฐ์ดํฐ๋ฒ ์ด์ค
- ์ธํด
- ์๋ฐ
- OOP
- ๋ฐฑ์ค
- ํ๋ก๊ทธ๋๋จธ์ค
- tree
- CS
- MST
- ์กธ์ ์ํ
- ์๋ฃ๊ตฌ์กฐ
- ๋ฒจ๋งํฌ๋
- ๊ตฌํ
- Algorithm
- PS
- ๋ฐฑ์๋
- ๋ค์ต์คํธ๋ผ
- java
- array
- ์๋ฐ์์ ์
- ๊ทธ๋ฆฌ๋
- leetcode
- pytorch
- ์์์ ๋ ฌ
- ๋ฌธ๋ฒ
- dp
- Graph
๋ชฉ๋ก๐ฅ Algorithm || ๋ฌธ์ ํ์ด (110)
Partially Committed
https://www.acmicpc.net/problem/1463 1463๋ฒ: 1๋ก ๋ง๋ค๊ธฐ ์ฒซ์งธ ์ค์ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 106๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์ ์ N์ด ์ฃผ์ด์ง๋ค. www.acmicpc.net ์ ์ n ์ 1๋ก ๋ง๋ค๊ธฐ ์ํ ์ฐ์ฐ ํ์์ ์ต์๊ฐ์ dp[n] ์ด๋ผ๊ณ ๊ฐ์ ํ์. ๊ทธ๋ฌ๋ฉด dp[0] = dp[1] = 0, dp[2] = 1, dp[3] = 1 dp table ์ ์๋์ ๊ฐ์ด bottom-up ๋ฐฉ์์ผ๋ก ์ฑ์๋๊ฐ ์ ์๋ค. 1. N ์ ๋ํ์ฌ N-1 ์ด ๊ฐ๋ฅํ๋ค๋ฉด dp[n] = dp[n-1]+1 2. N ์ด 2๋ก ๋๋์ด ๋จ์ด์ง๋ฉด dp[n] ์ dp[n/2]+1 ์ dp[n-1]+1 ์ค ๋ ์์ ๊ฐ์ ์ ํ 3. N ์ด 3์ผ๋ก ๋๋์ด ๋จ์ด์ง๋ฉด dp[n] ์ dp[n/3]+1 ์ dp[n-1]+1 ์ค ..
https://www.acmicpc.net/problem/1947 1947๋ฒ: ์ ๋ฌผ ์ ๋ฌ ๊ฒฝ์ฐ์ ์๋ฅผ 1,000,000,000์ผ๋ก ๋๋ ๋๋จธ์ง๋ฅผ ์ฒซ์งธ ์ค์ ์ถ๋ ฅํ๋ค. www.acmicpc.net n ๋ช ์ ์ฌ๋์ด ์๋ก์ ์ ๋ฌผ์ ๊ตํํ๋๋ฐ, ์๊ธฐ์ ์ ๋ฌผ์ ์๊ธฐ ์์ ์ด ๋ฐ์ผ๋ฉด ์๋๋ค. ์ด๋ฌํ ์ํฉ์ ์์ ์์ด์ ์ดํดํ๊ณ ์์ผ๋ฉด ์ฝ๊ฒ ๊ตฌํ ์ ์๋ค. https://namu.wiki/w/%EC%99%84%EC%A0%84%EC%88%9C%EC%97%B4 ์์ ์์ด - ๋๋ฌด์ํค ์์ ์์ด์ ๋ค๋ฃจ๋ ๋ฌธ์ ์์๋, ๊ทธ๋ฅ D5D_5D5โ๊น์ง๋ ์ธ์๋์. ์ฐจ๋ก๋๋ก 0,1,2,9,440, 1, 2, 9, 440,1,2,9,44์ด๋ค. D5=44D_5=44D5โ=44๋ง์ ๋ ๋๋ฌด ๋ง๋ค๊ณ ํ์ฌ ์ ๋์ค์ง ์์ผ๋ฉฐ D6=265D_6=265D..
https://www.acmicpc.net/problem/1256 1256๋ฒ: ์ฌ์ ๋ํธ์ ๊ท์์ด๋ 212ํธ์์ ๋ฌธ์์ด์ ๋ํด ๊ณต๋ถํ๊ณ ์๋ค. ๊น์ง์ ์กฐ๊ต๋ ๋ํธ์ ๊ท์์ด์๊ฒ ํน๋ณ ๊ณผ์ ๋ฅผ ์ฃผ์๋ค. ํน๋ณ ๊ณผ์ ๋ ํน๋ณํ ๋ฌธ์์ด๋ก ์ด๋ฃจ์ด ์ง ์ฌ์ ์ ๋ง๋๋ ๊ฒ์ด๋ค. ์ฌ์ ์ ์๋ก๋ www.acmicpc.net a ์ z ๋ก๋ง ๊ตฌ์ฑ๋ ๋ฌธ์์ด์ ๋ง๋ค ์ ์๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๊ตฌํ๋ค๋ ๊ฒ์ n+m ๊ฐ ์ค์์ n ๊ฐ(ํน์ m ๊ฐ) ๋ฅผ ์ ํํ๋ ๊ฒฝ์ฐ์ ์์ ๊ฐ๋ค. (a ๋ n ๊ฐ, z ๋ m ๊ฐ) ๊ฐ๊ฐ์ ๋ฌธ์์ด์ด ์ฌ์ ์ ๋ฐฐ์ด๋ก ์ด๋ฃจ์ด์ ธ์๋ค๊ณ ๊ฐ์ ํ๋ฏ๋ก, k ๋ฒ์งธ ๋ฌธ์์ด์ ์์๋ด๊ธฐ ์ํด์๋, n+m ๊ฐ์ ๋ฌธ์ ์ค์์ n ๊ฐ (ํน์ m๊ฐ) ๋ฅผ ์ ํํ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๋จผ์ ๊ตฌํด์ผ ํ๋ค. ๊ทธ๋ฆฌ๊ณ ๋์, a ๋ฅผ ์ ํํ๋ค๊ณ ๊ฐ์ ํ๊ณ ๋๋จธ..
https://www.acmicpc.net/problem/1991 1991๋ฒ: ํธ๋ฆฌ ์ํ ์ฒซ์งธ ์ค์๋ ์ด์ง ํธ๋ฆฌ์ ๋ ธ๋์ ๊ฐ์ N(1 ≤ N ≤ 26)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ๊ฑธ์ณ ๊ฐ ๋ ธ๋์ ๊ทธ์ ์ผ์ชฝ ์์ ๋ ธ๋, ์ค๋ฅธ์ชฝ ์์ ๋ ธ๋๊ฐ ์ฃผ์ด์ง๋ค. ๋ ธ๋์ ์ด๋ฆ์ A๋ถํฐ ์ฐจ๋ก๋๋ก ์ํ www.acmicpc.net ๋๋ณด๊ธฐ ์ด์ง ํธ๋ฆฌ๋ฅผ ์ ๋ ฅ๋ฐ์ ์ ์ ์ํ(preorder traversal), ์ค์ ์ํ(inorder traversal), ํ์ ์ํ(postorder traversal)ํ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์๋ฅผ ๋ค์ด ์์ ๊ฐ์ ์ด์ง ํธ๋ฆฌ๊ฐ ์ ๋ ฅ๋๋ฉด, ์ ์ ์ํํ ๊ฒฐ๊ณผ : ABDCEFG // (๋ฃจํธ) (์ผ์ชฝ ์์) (์ค๋ฅธ์ชฝ ์์) ์ค์ ์ํํ ๊ฒฐ๊ณผ : DBAECFG // (์ผ์ชฝ ์..