Problem Solving4 [ํ๋ก๊ทธ๋๋จธ์ค] ๋ฒ ์คํธ์จ๋ฒ (C++) ๋ฌธ์ ์ค๋ช ์คํธ๋ฆฌ๋ฐ ์ฌ์ดํธ์์ ์ฅ๋ฅด ๋ณ๋ก ๊ฐ์ฅ ๋ง์ด ์ฌ์๋ ๋ ธ๋๋ฅผ ๋ ๊ฐ์ฉ ๋ชจ์ ๋ฒ ์คํธ ์จ๋ฒ์ ์ถ์ํ๋ ค ํฉ๋๋ค. ๋ ธ๋๋ ๊ณ ์ ๋ฒํธ๋ก ๊ตฌ๋ถํ๋ฉฐ, ๋ ธ๋๋ฅผ ์๋กํ๋ ๊ธฐ์ค์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค. ์ํ ๋ ธ๋๊ฐ ๋ง์ด ์ฌ์๋ ์ฅ๋ฅด๋ฅผ ๋จผ์ ์๋กํฉ๋๋ค. ์ฅ๋ฅด ๋ด์์ ๋ง์ด ์ฌ์๋ ๋ ธ๋๋ฅผ ๋จผ์ ์๋กํฉ๋๋ค. ์ฅ๋ฅด ๋ด์์ ์ฌ์ ํ์๊ฐ ๊ฐ์ ๋ ธ๋ ์ค์์๋ ๊ณ ์ ๋ฒํธ๊ฐ ๋ฎ์ ๋ ธ๋๋ฅผ ๋จผ์ ์๋กํฉ๋๋ค. ๋ ธ๋์ ์ฅ๋ฅด๋ฅผ ๋ํ๋ด๋ ๋ฌธ์์ด ๋ฐฐ์ด genres์ ๋ ธ๋๋ณ ์ฌ์ ํ์๋ฅผ ๋ํ๋ด๋ ์ ์ ๋ฐฐ์ด plays๊ฐ ์ฃผ์ด์ง ๋, ๋ฒ ์คํธ ์จ๋ฒ์ ๋ค์ด๊ฐ ๋ ธ๋์ ๊ณ ์ ๋ฒํธ๋ฅผ ์์๋๋ก return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํ์ธ์. ์ ํ์ฌํญ genres[i]๋ ๊ณ ์ ๋ฒํธ๊ฐ i์ธ ๋ ธ๋์ ์ฅ๋ฅด์ ๋๋ค. plays[i]๋ ๊ณ ์ ๋ฒํธ๊ฐ i์ธ ๋ ธ๋๊ฐ ์ฌ์๋ ํ์์ ๋.. 2022. 6. 4. [ํ๋ก๊ทธ๋๋จธ์ค] ์ ํ๋ฒํธ ๋ชฉ๋ก (C++) ๋ฌธ์ ์ค๋ช ์ ํ๋ฒํธ๋ถ์ ์ ํ ์ ํ๋ฒํธ ์ค, ํ ๋ฒํธ๊ฐ ๋ค๋ฅธ ๋ฒํธ์ ์ ๋์ด์ธ ๊ฒฝ์ฐ๊ฐ ์๋์ง ํ์ธํ๋ ค ํฉ๋๋ค. ์ ํ๋ฒํธ๊ฐ ๋ค์๊ณผ ๊ฐ์ ๊ฒฝ์ฐ, ๊ตฌ์กฐ๋ ์ ํ๋ฒํธ๋ ์์์ด์ ์ ํ๋ฒํธ์ ์ ๋์ฌ์ ๋๋ค. ๊ตฌ์กฐ๋ : 119 ๋ฐ์ค์ : 97 674 223 ์ง์์ : 11 9552 4421 ์ ํ๋ฒํธ๋ถ์ ์ ํ ์ ํ๋ฒํธ๋ฅผ ๋ด์ ๋ฐฐ์ด phone_book ์ด solution ํจ์์ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์ด๋ค ๋ฒํธ๊ฐ ๋ค๋ฅธ ๋ฒํธ์ ์ ๋์ด์ธ ๊ฒฝ์ฐ๊ฐ ์์ผ๋ฉด false๋ฅผ ๊ทธ๋ ์ง ์์ผ๋ฉด true๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. ์ ํ ์ฌํญ phone_book์ ๊ธธ์ด๋ 1 ์ด์ 1,000,000 ์ดํ์ ๋๋ค. ๊ฐ ์ ํ๋ฒํธ์ ๊ธธ์ด๋ 1 ์ด์ 20 ์ดํ์ ๋๋ค. ๊ฐ์ ์ ํ๋ฒํธ๊ฐ ์ค๋ณตํด์ ๋ค์ด์์ง ์์ต๋๋ค. ๋ฌธ์ ๋ถ์ ํด์๋ฅผ.. 2022. 6. 4. [ํ๋ก๊ทธ๋๋จธ์ค] ๋ฐฐ๋ฌ (C++) ๋ฌธ์ ๋ถ์ - N๊ฐ์ ๋ง์๋ก ๊ตฌ์ฑ - ์๋ฐฉํฅ์ผ๋ก ํตํํ ์ ์๋ ๋๋ก๋ก ์ฐ๊ฒฐ - 1๋ฒ ๋ง์์ ์๋ ์์์ ์์ ๊ฐ ๋ง์๋ก ์์ ๋ฐฐ๋ฌ - N๊ฐ์ ๋ง์ ์ค K ์๊ฐ ์ดํ๋ก ๋ฐฐ๋ฌ์ด ๊ฐ๋ฅํ ๋ง์์ ์ ๋ฐํ ์์ ) ์ ๊ทธ๋ฆผ์์ 1๋ฒ ๋ง์์ ์๋ ์์์ ์ [1, 2, 4, 5] ๋ฒ ๋ง์๊น์ง๋ 3 ์ดํ์ ์๊ฐ์ ๋ฐฐ๋ฌํ ์ ์์ต๋๋ค. ๊ทธ๋ฌ๋ 3๋ฒ ๋ง์๊น์ง๋ 3์๊ฐ ์ด๋ด๋ก ๋ฐฐ๋ฌํ ์ ์๋ ๊ฒฝ๋ก๊ฐ ์์ผ๋ฏ๋ก 3๋ฒ ๋ง์์์๋ ์ฃผ๋ฌธ์ ๋ฐ์ง ์์ต๋๋ค. ๋ฐ๋ผ์ 1๋ฒ ๋ง์์ ์๋ ์์์ ์ด ๋ฐฐ๋ฌ ์ฃผ๋ฌธ์ ๋ฐ์ ์ ์๋ ๋ง์์ 4๊ฐ๊ฐ ๋ฉ๋๋ค. Dijkstra ์ ํ์ ์ฐ์ตํด๋ณด๊ธฐ ์ํด ํ์ด๋ณธ ๋ฌธ์ ์ด๋ฏ๋ก Dijkstra๋ฅผ ์ฌ์ฉํ๋ฉด ๊ฐ๋จํ ํ๋ฆฐ๋ค. ํ์ด ๋ฐฉ๋ฒ์ ๋ค์๊ณผ ๊ฐ๋ค. 1) road์ ๋ด๊ธด ๊ฐ์ ์ ์ ๋ณด๋ฅผ adj ๋ฒกํฐ์ ์ธ๋ฑ์ค๋ณ๋ก ์ ์ฅํ๋ค. .. 2022. 5. 17. [๋ฐฑ์ค] 1477๋ฒ: ํด๊ฒ์ ์ธ์ฐ๊ธฐ Parametric Search ์ฌ์ฉํ๋ ๋ฌธ์ ๋ฅผ ์ฐ์ตํ๊ธฐ ์ํด 1477๋ฒ์ ํ์ด๋ณด์์ผ๋ ์๋ฌด๋ฆฌ ์๊ฐํด๋ ์ด๋ถํ์์ ์ด๋ป๊ฒ ๋๋ ค์ผํ ์ง ๊ฐ์ด ์์๋ค. ๊ฒฐ๊ตญ ๋ดํ์ผ๋ก๋ ์ต์ ํ ๋ฌธ์ ๋ฅผ ๊ฒฐ์ ๋ฌธ์ ๋ก ๋ณํํ ์ ์๋ค๊ณ ํ๋จํด์ ๋ธ๋ก๊ทธ์ ๋์์ ๋ฐ์๋ค. Parametric Search: ์กฐ๊ฑด์ ๋ง์กฑํ๋ ์ต์/์ต๋๊ฐ์ ๊ตฌํ๋ ๋ฌธ์ (์ต์ ํ ๋ฌธ์ )๋ฅผ ๊ฒฐ์ ๋ฌธ์ ๋ก ๋ณํํด ์ด๋ถํ์์ ์ํํ๋๋ฐฉ๋ฒ ์๋ ๋ฌธ์ ๋ ํด๊ฒ์ ์๋ ๊ตฌ๊ฐ์ ๊ธธ์ด๋ฅผ ์ต์๋ก ๋ง๋๋ ๊ฒ์ด๋ผ๋ฉด ์ด๋ฅผ ๊ฒฐ์ ๋ฌธ์ ๋ก ๋ณํํด์ ์๋ก ์ธ์ธ ํด๊ฒ์ ๊ฐ์ ๊ธธ์ด๊ฐ X์ผ ๋, ํด๊ฒ์ ๊ฐ์๊ฐ M๊ฐ์ธ๊ฐ ์๋๊ฐ์ ๋ํด ๋ฌธ์ ๋ฅผ ํ์ด์ผ ํ๋ค. ์๋ก ์ธ์ธ ํด๊ฒ์ ๊ฐ์ ๊ธธ์ด X๋ ์์ฑ๋ ํด๊ฒ์ ๊ฐ์๊ฐ M๊ฐ ์ด์์ผ ๊ฒฝ์ฐ ๊ธธ์ด๋ฅผ ๋๋ฆฌ๊ณ M๊ฐ ์ดํ์ผ ๊ฒฝ์ฐ ๊ธธ์ด๋ฅผ ์ค์ด๋ ๋ฐฉ์์ผ๋ก ๊ตฌํด์ผ ํ๋ฏ๋ก ์ด.. 2022. 5. 10. ์ด์ 1 ๋ค์