๋ฐ์ํ
Algorithm
[Dynamic Programming] ๋ฐฐ๋ญ ๋ฌธ์ (Knapsack Problem)
[Dynamic Programming] ๋ฐฐ๋ญ ๋ฌธ์ (Knapsack Problem)
2020.07.17์ค๋ช
๋ฐฐ๋ญ ๋ฌธ์ (Knapsack Problem)๋ ์กฐํฉ ์ต์ ํ์ ์ ๋ช
ํ ๋ฌธ์ ๋ค. ์๋ฅผ ๋ค์ด ์ค๋ช
ํด๋ณด์. ํ ์ฌํ๊ฐ๊ฐ ์ฌํ์ ๋ ๋๋ ค๊ณ ํ๋ค. ์ฌํ๊ฐ๊ฐ ๊ฐ์ง๊ณ ๊ฐ๋ ๋ฐฐ๋ญ์๋ ๋ด์ ์ ์๋ ๋ฌด๊ฒ์ ์ต๋๊ฐ์ด ์ ํด์ ธ ์๊ณ ๋ฐฐ๋ญ์ ๋ฃ์ ์ ์๋ ์ง์๋ ๊ฐ๊ฐ์ ๋ฌด๊ฒ(W)์ ๊ฐ์น(V)๊ฐ ์ ํด์ ธ ์๋ค. ์ด ์ฌํ๊ฐ๊ฐ ๋ฐฐ๋ญ์ ๋ฌด๊ฒ๋ฅผ ์ต๋ํ ๊ฝ ์ฑ์ฐ๋ ๊ฐ์น์ ํฉ์ด ์ต๋๊ฐ ๋๋๋ก ์ง์ ๊ณ ๋ฅด๋ ค๋ฉด ์ด๋ป๊ฒ ํด์ผ ํ ๊น? ์ฌ๊ธฐ์ ์ง์ ์ชผ๊ฐค ์ ์๋ ๊ฒฝ์ฐ(๋ฌด๊ฒ๊ฐ ์์์ผ ์ ์๋ ๊ฒฝ์ฐ)์ ์ง์ ์ชผ๊ฐค ์ ์๋ ๊ฒฝ์ฐ ๋ ๊ฐ์ง๋ก ๋๋ ์ ์๋ค. ์ง์ ์ชผ๊ฐค ์ ์๋ ๋ถํ ๊ฐ๋ฅ ๋ฐฐ๋ญ ๋ฌธ์ (Fractional Knapsack Problem) - ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ ์ง์ ์ชผ๊ฐค ์ ์๋ ๋ฐฐ๋ญ ๋ฌธ์ (Knapsack Problem) - ๋์ ๊ณํ๋ฒ(Dynami..
[C++, Golang] 12865๋ฒ: ํ๋ฒํ ๋ฐฐ๋ญ
[C++, Golang] 12865๋ฒ: ํ๋ฒํ ๋ฐฐ๋ญ
2020.07.17ํด๋น ๊ธ์ ๋ด์ฉ์ ์ต์ ์ ์๊ณ ๋ฆฌ์ฆ์ด ์๋ ๊ธ์ด์ด์ ์ฃผ๊ด์ ์ธ ํ์ด์
๋๋ค. ๋ ์ข์ ํ์ด๊ฐ ์๋ค๋ฉด ๋๊ธ๋ก ํผ๋๋ฐฑ ๋ถํ๋๋ฆฝ๋๋ค(__) ๋งํฌ https://www.acmicpc.net/problem/12865 12865๋ฒ: ํ๋ฒํ ๋ฐฐ๋ญ ์ฒซ ์ค์ ๋ฌผํ์ ์ N(1 ≤ N ≤ 100)๊ณผ ์ค์๊ฐ ๋ฒํธ ์ ์๋ ๋ฌด๊ฒ K(1 ≤ K ≤ 100,000)๊ฐ ์ฃผ์ด์ง๋ค. ๋ ๋ฒ์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ๊ฑฐ์ณ ๊ฐ ๋ฌผ๊ฑด์ ๋ฌด๊ฒ W(1 ≤ W ≤ 100,000)์ ํด๋น ๋ฌผ๊ฑด์ ๊ฐ์น V(0 ≤ V ≤ 1,000) www.acmicpc.net ๋ฌธ์ ์ค๋ช
์ด ๋ฌธ์ ๋ ์์ฃผ ํ๋ฒํ ๋ฐฐ๋ญ์ ๊ดํ ๋ฌธ์ ์ด๋ค. ํ ๋ฌ ํ๋ฉด ๊ตญ๊ฐ์ ๋ถ๋ฆ์ ๋ฐ๊ฒ ๋๋ ์ค์๋ ์ฌํ์ ๊ฐ๋ ค๊ณ ํ๋ค. ์ธ์๊ณผ์ ๋จ์ ์ ์ฌํผํ๋ฉฐ ์ต๋ํ ์ฆ๊ธฐ๊ธฐ ์ํ ์ฌํ์ด๊ธฐ ๋๋ฌธ์, ๊ฐ์ง๊ณ ๋ค๋ ..
[C++, Golang] 2798๋ฒ: ๋ธ๋์ญ
[C++, Golang] 2798๋ฒ: ๋ธ๋์ญ
2020.07.14ํด๋น ๊ธ์ ๋ด์ฉ์ ์ต์ ์ ์๊ณ ๋ฆฌ์ฆ์ด ์๋ ๊ธ์ด์ด์ ์ฃผ๊ด์ ์ธ ํ์ด์
๋๋ค. ๋ ์ข์ ํ์ด๊ฐ ์๋ค๋ฉด ๋๊ธ๋ก ํผ๋๋ฐฑ ๋ถํ๋๋ฆฝ๋๋ค(__) ๋งํฌ https://www.acmicpc.net/problem/2798 2798๋ฒ: ๋ธ๋์ญ ๋ฌธ์ ์นด์ง๋
ธ์์ ์ ์ผ ์ธ๊ธฐ ์๋ ๊ฒ์ ๋ธ๋์ญ์ ๊ท์น์ ์๋นํ ์ฝ๋ค. ์นด๋์ ํฉ์ด 21์ ๋์ง ์๋ ํ๋ ๋ด์์, ์นด๋์ ํฉ์ ์ต๋ํ ํฌ๊ฒ ๋ง๋๋ ๊ฒ์์ด๋ค. ๋ธ๋์ญ์ ์นด์ง๋
ธ๋ง๋ค ๋ค์ํ ๊ท์ ์ด ๏ฟฝ๏ฟฝ www.acmicpc.net ๋ฌธ์ ์ค๋ช
์นด์ง๋
ธ์์ ์ ์ผ ์ธ๊ธฐ ์๋ ๊ฒ์ ๋ธ๋์ญ์ ๊ท์น์ ์๋นํ ์ฝ๋ค. ์นด๋์ ํฉ์ด 21์ ๋์ง ์๋ ํ๋ ๋ด์์, ์นด๋์ ํฉ์ ์ต๋ํ ํฌ๊ฒ ๋ง๋๋ ๊ฒ์์ด๋ค. ๋ธ๋์ญ์ ์นด์ง๋
ธ๋ง๋ค ๋ค์ํ ๊ท์ ์ด ์๋ค. ํ๊ตญ ์ต๊ณ ์ ๋ธ๋์ญ ๊ณ ์ ๊น์ ์ธ์ ์๋ก์ด ๋ธ๋์ญ ๊ท์น์ ๋ง๋ค์ด ์๊ทผ..
[C++, Golang, Java] 14888๋ฒ: ์ฐ์ฐ์ ๋ผ์๋ฃ๊ธฐ
[C++, Golang, Java] 14888๋ฒ: ์ฐ์ฐ์ ๋ผ์๋ฃ๊ธฐ
2020.07.10ํด๋น ๊ธ์ ๋ด์ฉ์ ์ต์ ์ ์๊ณ ๋ฆฌ์ฆ์ด ์๋ ๊ธ์ด์ด์ ์ฃผ๊ด์ ์ธ ํ์ด์
๋๋ค. ๋ ์ข์ ํ์ด๊ฐ ์๋ค๋ฉด ๋๊ธ๋ก ํผ๋๋ฐฑ ๋ถํ๋๋ฆฝ๋๋ค(__) ๋งํฌ https://www.acmicpc.net/problem/14888 14888๋ฒ: ์ฐ์ฐ์ ๋ผ์๋ฃ๊ธฐ ์ฒซ์งธ ์ค์ ์์ ๊ฐ์ N(2 ≤ N ≤ 11)๊ฐ ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์๋ A1, A2, ..., AN์ด ์ฃผ์ด์ง๋ค. (1 ≤ Ai ≤ 100) ์
์งธ ์ค์๋ ํฉ์ด N-1์ธ 4๊ฐ์ ์ ์๊ฐ ์ฃผ์ด์ง๋๋ฐ, ์ฐจ๋ก๋๋ก ๋ง์
(+)์ ๊ฐ์, ๋บ์
(-)์ ๊ฐ์, ๏ฟฝ๏ฟฝ www.acmicpc.net ๋ฌธ์ ์ค๋ช
N๊ฐ์ ์๋ก ์ด๋ฃจ์ด์ง ์์ด A1, A2,..., AN์ด ์ฃผ์ด์ง๋ค. ๋, ์์ ์ ์ฌ์ด์ ๋ผ์ ๋ฃ์ ์ ์๋ N-1๊ฐ์ ์ฐ์ฐ์๊ฐ ์ฃผ์ด์ง๋ค. ์ฐ์ฐ์๋ ๋ง์
(+), ๋บ์
(-), ๊ณฑ์
(×), ๋๋์
(÷..
[C++, Golang] 11729๋ฒ: ํ๋
ธ์ด ํ ์ด๋ ์์
[C++, Golang] 11729๋ฒ: ํ๋ ธ์ด ํ ์ด๋ ์์
2020.07.10ํด๋น ๊ธ์ ๋ด์ฉ์ ์ต์ ์ ์๊ณ ๋ฆฌ์ฆ์ด ์๋ ๊ธ์ด์ด์ ์ฃผ๊ด์ ์ธ ํ์ด์
๋๋ค. ๋ ์ข์ ํ์ด๊ฐ ์๋ค๋ฉด ๋๊ธ๋ก ํผ๋๋ฐฑ ๋ถํ๋๋ฆฝ๋๋ค(__) ๋งํฌ https://www.acmicpc.net/problem/11729 11729๋ฒ: ํ๋
ธ์ด ํ ์ด๋ ์์ ์ธ ๊ฐ์ ์ฅ๋๊ฐ ์๊ณ ์ฒซ ๋ฒ์งธ ์ฅ๋์๋ ๋ฐ๊ฒฝ์ด ์๋ก ๋ค๋ฅธ n๊ฐ์ ์ํ์ด ์์ฌ ์๋ค. ๊ฐ ์ํ์ ๋ฐ๊ฒฝ์ด ํฐ ์์๋๋ก ์์ฌ์๋ค. ์ด์ ์๋์น๋ค์ด ๋ค์ ๊ท์น์ ๋ฐ๋ผ ์ฒซ ๋ฒ์งธ ์ฅ๋์์ ์ธ ๋ฒ์งธ ์ฅ๋๋ก www.acmicpc.net ๋ฌธ์ ์ค๋ช
์ธ ๊ฐ์ ์ฅ๋๊ฐ ์๊ณ ์ฒซ ๋ฒ์งธ ์ฅ๋์๋ ๋ฐ๊ฒฝ์ด ์๋ก ๋ค๋ฅธ n๊ฐ์ ์ํ์ด ์์ฌ ์๋ค. ๊ฐ ์ํ์ ๋ฐ๊ฒฝ์ด ํฐ ์์๋๋ก ์์ฌ์๋ค. ์ด์ ์๋์น๋ค์ด ๋ค์ ๊ท์น์ ๋ฐ๋ผ ์ฒซ ๋ฒ์งธ ์ฅ๋์์ ์ธ ๋ฒ์งธ ์ฅ๋๋ก ์ฎ๊ธฐ๋ ค ํ๋ค. ํ ๋ฒ์ ํ ๊ฐ์ ์ํ๋ง์ ๋ค๋ฅธ ํ..
[C++, Golang] 2012๋ฒ: ๋ฑ์ ๋งค๊ธฐ๊ธฐ
[C++, Golang] 2012๋ฒ: ๋ฑ์ ๋งค๊ธฐ๊ธฐ
2020.07.08ํด๋น ๊ธ์ ๋ด์ฉ์ ์ต์ ์ ์๊ณ ๋ฆฌ์ฆ์ด ์๋ ๊ธ์ด์ด์ ์ฃผ๊ด์ ์ธ ํ์ด์
๋๋ค. ๋ ์ข์ ํ์ด๊ฐ ์๋ค๋ฉด ๋๊ธ๋ก ํผ๋๋ฐฑ ๋ถํ๋๋ฆฝ๋๋ค(__) ๋งํฌ https://www.acmicpc.net/problem/2012 2012๋ฒ: ๋ฑ์ ๋งค๊ธฐ๊ธฐ ์ฒซ์งธ ์ค์ ์์ฐ์ N์ด ์ฃผ์ด์ง๋ค. (1 ≤ N ≤ 500,000) ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ๊ฑธ์ณ ๊ฐ ์ฌ๋์ ์์ ๋ฑ์๊ฐ ์์๋๋ก ์ฃผ์ด์ง๋ค. ์์ ๋ฑ์๋ 500,000 ์ดํ์ ์์ฐ์์ด๋ค. www.acmicpc.net ๋ฌธ์ ์ค๋ช
2007๋
KOI์ N๋ช
์ ํ์๋ค์ด ์ฐธ๊ฐํ์๋ค. ๊ฒฝ์์ผ ์ ๋ ์ธ ์๋น์์ง์ผ์, ๋ชจ๋ ํ์๋ค์ ์์ ์ด N๋ช
์ค์์ ๋ช ๋ฑ์ ํ ๊ฒ์ธ์ง ์์ ๋ฑ์๋ฅผ ์ ์ด์ ์ ์ถํ๋๋ก ํ์๋ค. KOI ๋ด๋น ์กฐ๊ต๋ก ์ฐธ๊ฐํ ๊น์ง์ ์กฐ๊ต๋ ์ค์๋ก ๋ชจ๋ ํ์์ ํ๋ก๊ทธ๋จ์ ๋ ๋ ค ๋ฒ๋ ธ๋ค. 1๋ฑ๋ถ..
[C++] 2447๋ฒ: ๋ณ์ฐ๊ธฐ - 10
[C++] 2447๋ฒ: ๋ณ์ฐ๊ธฐ - 10
2020.07.07ํด๋น ๊ธ์ ๋ด์ฉ์ ์ต์ ์ ์๊ณ ๋ฆฌ์ฆ์ด ์๋ ๊ธ์ด์ด์ ์ฃผ๊ด์ ์ธ ํ์ด์
๋๋ค. ๋ ์ข์ ํ์ด๊ฐ ์๋ค๋ฉด ๋๊ธ๋ก ํผ๋๋ฐฑ ๋ถํ๋๋ฆฝ๋๋ค(__) ๋งํฌ https://www.acmicpc.net/problem/2447 2447๋ฒ: ๋ณ ์ฐ๊ธฐ - 10 ์ฌ๊ท์ ์ธ ํจํด์ผ๋ก ๋ณ์ ์ฐ์ด ๋ณด์. N์ด 3์ ๊ฑฐ๋ญ์ ๊ณฑ(3, 9, 27, ...)์ด๋ผ๊ณ ํ ๋, ํฌ๊ธฐ N์ ํจํด์ N×N ์ ์ฌ๊ฐํ ๋ชจ์์ด๋ค. ํฌ๊ธฐ 3์ ํจํด์ ๊ฐ์ด๋ฐ์ ๊ณต๋ฐฑ์ด ์๊ณ , ๊ฐ์ด๋ฐ๋ฅผ ์ ์ธํ ๋ชจ๋ ์นธ์ ๋ณ์ด ๏ฟฝ www.acmicpc.net ๋ฌธ์ ์ค๋ช
์ฌ๊ท์ ์ธ ํจํด์ผ๋ก ๋ณ์ ์ฐ์ด ๋ณด์. N์ด 3์ ๊ฑฐ๋ญ์ ๊ณฑ(3, 9, 27,...)์ด๋ผ๊ณ ํ ๋, ํฌ๊ธฐ N์ ํจํด์ N×N ์ ์ฌ๊ฐํ ๋ชจ์์ด๋ค. ํฌ๊ธฐ 3์ ํจํด์ ๊ฐ์ด๋ฐ์ ๊ณต๋ฐฑ์ด ์๊ณ , ๊ฐ์ด๋ฐ๋ฅผ ์ ์ธํ ๋ชจ๋ ์นธ์ ๋ณ์ด ํ๋์ฉ ์๋..
[Golang] 2447๋ฒ: ๋ณ์ฐ๊ธฐ - 10
[Golang] 2447๋ฒ: ๋ณ์ฐ๊ธฐ - 10
2020.07.07ํด๋น ๊ธ์ ๋ด์ฉ์ ์ต์ ์ ์๊ณ ๋ฆฌ์ฆ์ด ์๋ ๊ธ์ด์ด์ ์ฃผ๊ด์ ์ธ ํ์ด์
๋๋ค. ๋ ์ข์ ํ์ด๊ฐ ์๋ค๋ฉด ๋๊ธ๋ก ํผ๋๋ฐฑ ๋ถํ๋๋ฆฝ๋๋ค(__) ๋งํฌ https://www.acmicpc.net/problem/2447 2447๋ฒ: ๋ณ ์ฐ๊ธฐ - 10 ์ฌ๊ท์ ์ธ ํจํด์ผ๋ก ๋ณ์ ์ฐ์ด ๋ณด์. N์ด 3์ ๊ฑฐ๋ญ์ ๊ณฑ(3, 9, 27, ...)์ด๋ผ๊ณ ํ ๋, ํฌ๊ธฐ N์ ํจํด์ N×N ์ ์ฌ๊ฐํ ๋ชจ์์ด๋ค. ํฌ๊ธฐ 3์ ํจํด์ ๊ฐ์ด๋ฐ์ ๊ณต๋ฐฑ์ด ์๊ณ , ๊ฐ์ด๋ฐ๋ฅผ ์ ์ธํ ๋ชจ๋ ์นธ์ ๋ณ์ด ๏ฟฝ www.acmicpc.net ๋ฌธ์ ์ค๋ช
์ฌ๊ท์ ์ธ ํจํด์ผ๋ก ๋ณ์ ์ฐ์ด ๋ณด์. N์ด 3์ ๊ฑฐ๋ญ์ ๊ณฑ(3, 9, 27,...)์ด๋ผ๊ณ ํ ๋, ํฌ๊ธฐ N์ ํจํด์ N×N ์ ์ฌ๊ฐํ ๋ชจ์์ด๋ค. ํฌ๊ธฐ 3์ ํจํด์ ๊ฐ์ด๋ฐ์ ๊ณต๋ฐฑ์ด ์๊ณ , ๊ฐ์ด๋ฐ๋ฅผ ์ ์ธํ ๋ชจ๋ ์นธ์ ๋ณ์ด ํ๋์ฉ ์๋..
[C++] ์ฃผ์ ๊ฐ๊ฒฉ
[C++] ์ฃผ์ ๊ฐ๊ฒฉ
2019.09.15๋งํฌ https://programmers.co.kr/learn/courses/30/lessons/42584# ์ฝ๋ฉํ
์คํธ ์ฐ์ต - ์ฃผ์๊ฐ๊ฒฉ | ํ๋ก๊ทธ๋๋จธ์ค ์ด ๋จ์๋ก ๊ธฐ๋ก๋ ์ฃผ์๊ฐ๊ฒฉ์ด ๋ด๊ธด ๋ฐฐ์ด prices๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๊ฐ๊ฒฉ์ด ๋จ์ด์ง์ง ์์ ๊ธฐ๊ฐ์ ๋ช ์ด์ธ์ง๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํ์ธ์. ์ ํ์ฌํญ prices์ ๊ฐ ๊ฐ๊ฒฉ์ 1 ์ด์ 10,000 ์ดํ์ธ ์์ฐ์์
๋๋ค. prices์ ๊ธธ์ด๋ 2 ์ด์ 100,000 ์ดํ์
๋๋ค. ์
์ถ๋ ฅ ์ prices return [1, 2, 3, 2, 3] [4, 3, 1, 1, 0] ์
์ถ๋ ฅ ์ ์ค๋ช
1์ด ์์ ์ โฉ1์ ๋๊น์ง ๊ฐ๊ฒฉ์ด ๋จ์ด์ง์ง programmers.co.kr ๋ฌธ์ ์ค๋ช
์ด ๋จ์๋ก ๊ธฐ๋ก๋ ์ฃผ์ ๊ฐ๊ฒฉ์ด ๋ด๊ธด ๋ฐฐ์ด prices๊ฐ ..
[C++] x๋งํผ ๊ฐ๊ฒฉ์ด ์๋ n๊ฐ์ ์ซ์
[C++] x๋งํผ ๊ฐ๊ฒฉ์ด ์๋ n๊ฐ์ ์ซ์
2019.09.10๋งํฌ https://programmers.co.kr/learn/courses/30/lessons/12954# ์ฝ๋ฉํ
์คํธ ์ฐ์ต - x๋งํผ ๊ฐ๊ฒฉ์ด ์๋ n๊ฐ์ ์ซ์ | ํ๋ก๊ทธ๋๋จธ์ค ํจ์ solution์ ์ ์ x์ ์์ฐ์ n์ ์
๋ ฅ ๋ฐ์, x๋ถํฐ ์์ํด x์ฉ ์ฆ๊ฐํ๋ ์ซ์๋ฅผ n๊ฐ ์ง๋๋ ๋ฆฌ์คํธ๋ฅผ ๋ฆฌํดํด์ผ ํฉ๋๋ค. ๋ค์ ์ ํ ์กฐ๊ฑด์ ๋ณด๊ณ , ์กฐ๊ฑด์ ๋ง์กฑํ๋ ํจ์, solution์ ์์ฑํด์ฃผ์ธ์. ์ ํ ์กฐ๊ฑด x๋ -10000000 ์ด์, 10000000 ์ดํ์ธ ์ ์์
๋๋ค. n์ 1000 ์ดํ์ธ ์์ฐ์์
๋๋ค. ์
์ถ๋ ฅ ์ x n answer 2 5 [2,4,6,8,10] 4 3 [4,8,12] -4 2 [-4, -8] programmers.co.kr ๋ฌธ์ ์ค๋ช
ํจ์ solution์ ์ ์ x์ ์์ฐ์ n์ ์
๋ ฅ๋ฐ์,..
[Golang] x๋งํผ ๊ฐ๊ฒฉ์ด ์๋ n๊ฐ์ ์ซ์
[Golang] x๋งํผ ๊ฐ๊ฒฉ์ด ์๋ n๊ฐ์ ์ซ์
2019.09.10๋งํฌ https://programmers.co.kr/learn/courses/30/lessons/12954# ์ฝ๋ฉํ
์คํธ ์ฐ์ต - x๋งํผ ๊ฐ๊ฒฉ์ด ์๋ n๊ฐ์ ์ซ์ | ํ๋ก๊ทธ๋๋จธ์ค ํจ์ solution์ ์ ์ x์ ์์ฐ์ n์ ์
๋ ฅ ๋ฐ์, x๋ถํฐ ์์ํด x์ฉ ์ฆ๊ฐํ๋ ์ซ์๋ฅผ n๊ฐ ์ง๋๋ ๋ฆฌ์คํธ๋ฅผ ๋ฆฌํดํด์ผ ํฉ๋๋ค. ๋ค์ ์ ํ ์กฐ๊ฑด์ ๋ณด๊ณ , ์กฐ๊ฑด์ ๋ง์กฑํ๋ ํจ์, solution์ ์์ฑํด์ฃผ์ธ์. ์ ํ ์กฐ๊ฑด x๋ -10000000 ์ด์, 10000000 ์ดํ์ธ ์ ์์
๋๋ค. n์ 1000 ์ดํ์ธ ์์ฐ์์
๋๋ค. ์
์ถ๋ ฅ ์ x n answer 2 5 [2,4,6,8,10] 4 3 [4,8,12] -4 2 [-4, -8] programmers.co.kr ๋ฌธ์ ์ค๋ช
ํจ์ solution์ ์ ์ x์ ์์ฐ์ n์ ์
๋ ฅ๋ฐ์,..