๋ฌธ์ https://www.acmicpc.net/problem/9093 9093๋ฒ: ๋จ์ด ๋ค์ง๊ธฐ ์ฒซ์งธ ์ค์ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์ T๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ ์คํธ ์ผ์ด์ค๋ ํ ์ค๋ก ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉฐ, ๋ฌธ์ฅ์ด ํ๋ ์ฃผ์ด์ง๋ค. ๋จ์ด์ ๊ธธ์ด๋ ์ต๋ 20, ๋ฌธ์ฅ์ ๊ธธ์ด๋ ์ต๋ 1000์ด๋ค. ๋จ์ด์ ๋จ์ด ์ฌ์ด์๋ www.acmicpc.net ๋ฌธ์ ํ์ด https://choi95.tistory.com/42?category=881084 ์ ํจํ ํฐ๋ฆฐ๋๋กฌ ๋ฌธ์ ์์์ ์ฝ์ ๋๋ ๋ค์์ ์ฝ์ ๋๋ ๊ฐ์ ๋ฌธ์์ด์ ํฐ๋ฆฐ๋๋กฌ์ด๋ผ๊ณ ํ๋ค. ๋ฌธ์์ด์ด ์ ๋ ฅ๋๋ฉด ํด๋น ๋ฌธ์์ด์ด ํฐ๋ฆฐ๋๋กฌ์ด๋ฉด "YES", ์๋๋ฉด "NO"๋ฅผ ์ถ๋ ฅํ๊ณ ์ ํ๋ค. ๋จ, ํ๋ฌธ์ ๊ฒ์ฌํ ๋ ์ํ choi95.tistory.com ๋ฌธ์ ํ์ด๋ ์ด์ ํฌ์คํ ์ ์ ํจํ ํฐ๋ฆฐ๋๋กฌ๊ณผ ๋น์ท..
๋ฌธ์ https://www.acmicpc.net/problem/10828 10828๋ฒ: ์คํ ์ฒซ์งธ ์ค์ ์ฃผ์ด์ง๋ ๋ช ๋ น์ ์ N (1 ≤ N ≤ 10,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ๋ช ๋ น์ด ํ๋์ฉ ์ฃผ์ด์ง๋ค. ์ฃผ์ด์ง๋ ์ ์๋ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 100,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ๋ค. ๋ฌธ์ ์ ๋์์์ง www.acmicpc.net ๋ฌธ์ ํ์ด ๊ฐ ๋ช ๋ น์ด๋ฅผ ์คํํ ๋๋ง๋ค ์ฝ์์ ์ฐ์ด์ ๊ฒฐ๊ณผ๋ฅผ ํ์ธํ๋ฉด ํ์ ์ค๋ฒ๋ก ์ธํด ์ค๋ต์ด ๋๋ค.์ด์ stack๊ณผ answer์ ์ฐ์ ์ ์ผ๋ก ํด๋น ๋ช ๋ น์ด๋ค์ ๋ํ ์ฐ์ฐ์ ์คํํด์ฃผ๋ฉฐ ์ต์ข ์ ์ธ ๊ฐ์ ๊ฒฐ๊ณผ๊ฐ์ผ๋ก ๋ฆฌํดํด์ค์ผ ๋๋ค. ์ฝ๋ const array = require('fs').readFileSync('/dev/stdin').toString().split('\n'); cons..
๋ฌธ์ ๋ค์ค์ ํ๋ก๋๊ฐ ์ซ์๋์ด๋ฅผ ํ๊ณ ์์ต๋๋ค. ๋ค์ค๊ฐ ํ๋ก๋์๊ฒ ์ซ์๋ฅผ ๊ฑด๋ฌ ๋ ์ผ๋ถ ์๋ฆฟ์๋ฅผ ์๋จ์ด๋ก ๋ฐ๊พผ ์นด๋๋ฅผ ๊ฑด๋ค์ฃผ๋ฉด ํ๋ก๋๋ ์๋ ์ซ์๋ฅผ ์ฐพ๋ ๊ฒ์์ ๋๋ค. ๋ค์์ ์ซ์์ ์ผ๋ถ ์๋ฆฟ์๋ฅผ ์๋จ์ด๋ก ๋ฐ๊พธ๋ ์์์ ๋๋ค. 1478 → "one4seveneight" 234567 → "23four5six7" 10203 → "1zerotwozero3" ์ด๋ ๊ฒ ์ซ์์ ์ผ๋ถ ์๋ฆฟ์๊ฐ ์๋จ์ด๋ก ๋ฐ๋์ด์ก๊ฑฐ๋, ํน์ ๋ฐ๋์ง ์๊ณ ๊ทธ๋๋ก์ธ ๋ฌธ์์ด s๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง๋๋ค. s๊ฐ ์๋ฏธํ๋ ์๋ ์ซ์๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. ์ฐธ๊ณ ๋ก ๊ฐ ์ซ์์ ๋์๋๋ ์๋จ์ด๋ ๋ค์ ํ์ ๊ฐ์ต๋๋ค. ์ซ์์๋จ์ด 0 zero 1 one 2 two 3 three 4 four 5 five 6 six 7 seve..
๋ฌธ์ ์นด์นด์ค์ ์ ์ฌํ ์ ์ ๊ฐ๋ฐ์ ๋ค์ค๋ "์นด์นด์ค๊ณ์ ๊ฐ๋ฐํ"์ ๋ฐฐ์น๋์ด, ์นด์นด์ค ์๋น์ค์ ๊ฐ์ ํ๋ ์ ์ ๋ค์ ์์ด๋๋ฅผ ์์ฑํ๋ ์ ๋ฌด๋ฅผ ๋ด๋นํ๊ฒ ๋์์ต๋๋ค. "๋ค์ค"์๊ฒ ์ฃผ์ด์ง ์ฒซ ์ ๋ฌด๋ ์๋ก ๊ฐ์ ํ๋ ์ ์ ๋ค์ด ์นด์นด์ค ์์ด๋ ๊ท์น์ ๋ง์ง ์๋ ์์ด๋๋ฅผ ์ ๋ ฅํ์ ๋, ์ ๋ ฅ๋ ์์ด๋์ ์ ์ฌํ๋ฉด์ ๊ท์น์ ๋ง๋ ์์ด๋๋ฅผ ์ถ์ฒํด์ฃผ๋ ํ๋ก๊ทธ๋จ์ ๊ฐ๋ฐํ๋ ๊ฒ์ ๋๋ค. ๋ค์์ ์นด์นด์ค ์์ด๋์ ๊ท์น์ ๋๋ค. ์์ด๋์ ๊ธธ์ด๋ 3์ ์ด์ 15์ ์ดํ์ฌ์ผ ํฉ๋๋ค. ์์ด๋๋ ์ํ๋ฒณ ์๋ฌธ์, ์ซ์, ๋นผ๊ธฐ(-), ๋ฐ์ค(_), ๋ง์นจํ(.) ๋ฌธ์๋ง ์ฌ์ฉํ ์ ์์ต๋๋ค. ๋จ, ๋ง์นจํ(.)๋ ์ฒ์๊ณผ ๋์ ์ฌ์ฉํ ์ ์์ผ๋ฉฐ ๋ํ ์ฐ์์ผ๋ก ์ฌ์ฉํ ์ ์์ต๋๋ค. "๋ค์ค"๋ ๋ค์๊ณผ ๊ฐ์ด 7๋จ๊ณ์ ์์ฐจ์ ์ธ ์ฒ๋ฆฌ ๊ณผ์ ์ ํตํด ์ ๊ท ์ ์ ๊ฐ ์ ๋ ฅํ ์์ด๋๊ฐ ..
๋ฌธ์ ๋ก๋ 6/45(์ดํ '๋ก๋'๋ก ํ๊ธฐ)๋ 1๋ถํฐ 45๊น์ง์ ์ซ์ ์ค 6๊ฐ๋ฅผ ์ฐ์ด์ ๋งํ๋ ๋ํ์ ์ธ ๋ณต๊ถ์ ๋๋ค. ์๋๋ ๋ก๋์ ์์๋ฅผ ์ ํ๋ ๋ฐฉ์์ ๋๋ค. 1 ์์๋น์ฒจ ๋ด์ฉ 1 6๊ฐ ๋ฒํธ๊ฐ ๋ชจ๋ ์ผ์น 2 5๊ฐ ๋ฒํธ๊ฐ ์ผ์น 3 4๊ฐ ๋ฒํธ๊ฐ ์ผ์น 4 3๊ฐ ๋ฒํธ๊ฐ ์ผ์น 5 2๊ฐ ๋ฒํธ๊ฐ ์ผ์น 6(๋์ฒจ) ๊ทธ ์ธ ๋ก๋๋ฅผ ๊ตฌ๋งคํ ๋ฏผ์ฐ๋ ๋น์ฒจ ๋ฒํธ ๋ฐํ์ผ์ ํ์๊ณ ๋ํ๊ณ ์์์ต๋๋ค. ํ์ง๋ง, ๋ฏผ์ฐ์ ๋์์ด ๋ก๋์ ๋์๋ฅผ ํ์ฌ, ์ผ๋ถ ๋ฒํธ๋ฅผ ์์๋ณผ ์ ์๊ฒ ๋์์ต๋๋ค. ๋น์ฒจ ๋ฒํธ ๋ฐํ ํ, ๋ฏผ์ฐ๋ ์์ ์ด ๊ตฌ๋งคํ๋ ๋ก๋๋ก ๋น์ฒจ์ด ๊ฐ๋ฅํ๋ ์ต๊ณ ์์์ ์ต์ ์์๋ฅผ ์์๋ณด๊ณ ์ถ์ด ์ก์ต๋๋ค. ์์๋ณผ ์ ์๋ ๋ฒํธ๋ฅผ 0์ผ๋ก ํ๊ธฐํ๊ธฐ๋ก ํ๊ณ , ๋ฏผ์ฐ๊ฐ ๊ตฌ๋งคํ ๋ก๋ ๋ฒํธ 6๊ฐ๊ฐ 44, 1, 0, 0, 31 25๋ผ๊ณ ๊ฐ์ ํด๋ณด๊ฒ ์ต๋๋ค. ๋น..
๋ฌธ์ ์ด๋ฒ ์ ๋ณด์ฌ๋ฆผํผ์๋๋ํ์์ ์ข์ ์ฑ์ ์ ๋ด๊ธฐ ์ํ์ฌ ํ์๋ ์ ์๋์ด ์ฃผ์ N๊ฐ์ ๋ฌธ์ ๋ฅผ ํ๋ ค๊ณ ํฉ๋๋ค.๊ฐ ๋ฌธ์ ๋ ๊ทธ๊ฒ์ ํ์์ ๋ ์ป๋ ์ ์์ ํธ๋๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ด ์ฃผ์ด์ง๊ฒ ๋ฉ๋๋ค. ์ ํ์๊ฐ M์์ N๊ฐ์ ๋ฌธ์ ์ค ์ต๋์ ์๋ฅผ์ป์ ์ ์๋๋ก ํด์ผ ํฉ๋๋ค.(ํด๋น ๋ฌธ์ ๋ ํด๋น์๊ฐ์ด ๊ฑธ๋ฆฌ๋ฉด ํธ๋ ๊ฑธ๋ก ๊ฐ์ฃผํ๋ค, ํ ์ ํ๋น ํ๊ฐ๋ง ํ ์ ์๋ค) 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.acmicp..
๋ฌธ์ https://choi95.tistory.com/119?category=854389 [DFS-Cut Edge]๋์ ๊ตํ ๋ฌธ์ ๋ค์๊ณผ ๊ฐ์ด ์ฌ๋ฌ ๋จ์์ ๋์ ๋ค์ด ์ฃผ์ด์ ธ ์์๋ ๊ฑฐ์ค๋ฆ๋์ ๊ฐ์ฅ ์ ์ ์์ ๋์ ์ผ๋ก ๊ตํํด์ฃผ๋ ค๋ฉด ์ด๋ป๊ฒ ์ฃผ๋ฉด ๋๋๊ฐ?๊ฐ ๋จ์์ ๋์ ์ ๋ฌดํ์ ์ธ ์ ์๋ค. ๋ฌธ์ ํ์ด ์ฝ๋ function solutio choi95.tistory.com ๋์ ๊ตํ ๋ฌธ์ ๋ ์ด์ ํฌ์คํ ์์ ๊น์ด ํ์(DFS)์ ํตํด ํผ ๋ฐ๊ฐ ์๋ค. ๊น์ด ํ์์ ํตํด์๋ ํด๋น ๋ฌธ์ ๋ฅผ ํ ์๋ ์์ผ๋ ์ฌ์ฉ๋๋ ๋์ ์ข ๋ฅ์ ๊ฐฏ์๊ฐ ๋ง๊ฑฐ๋ ์ ์๋ ๊ฑฐ์ค๋ฆ๋ ๊ธ์ก์ด ๋ง์ ๊ฒฝ์ฐ์๋ ์๊ฐ ๋ณต์ก๋ ์ ๋นํจ์จ์ ์ผ ์ ์๊ธฐ ๋๋ฌธ์ ๋ ์ ์๊ณ ๋ฆฌ์ฆ์ ํตํด ํด๋น ๋ฌธ์ ๋ฅผ ํ์ดํด ๋ณด๊ณ ์ ํ๋ค. ๋ฌธ์ ํ์ด ์๋ฅผ ๋ค์ด ๋์ 1์๋ง์ ์ฌ์ฉํ์์ ๋ ๊ฑฐ์ฌ..
๋ฌธ์ N๊ฐ์ ์์ฐ์๋ก ์ด๋ฃจ์ด์ง ์์ด์ด ์ฃผ์ด์ก์ ๋, ๊ทธ ์ค์์ ๊ฐ์ฅ ๊ธธ๊ฒ ์ฆ๊ฐํ๋(์์ ์์์ ํฐ ์๋ก) ์์๋ค์ ์งํฉ์ ์ฐพ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ๋ผ. ์๋ฅผ ๋ค์ด, ์์๊ฐ 2, 7, 5, 8, 6, 4, 7, 12, 3 ์ด๋ฉด ๊ฐ์ฅ ๊ธธ๊ฒ ์ฆ๊ฐํ๋๋ก ์์๋ค์ ์ฐจ๋ก๋๋ก ๋ฝ์๋ด๋ฉด 2, 5, 6, 7, 12๋ฅผ ๋ฝ์๋ด์ด ๊ธธ์ด๊ฐ 5์ธ ์ต๋ ๋ถ๋ถ ์ฆ๊ฐ ์์ด์ ๋ง๋ค ์ ์๋ค. ๋ฌธ์ ํ์ด ์ต์ฅ ์ฆ๊ฐ ๋ถ๋ถ ์์ด(LIS, Longest Increasing Subsequence) ์์๊ฐ n๊ฐ์ธ ๋ฐฐ์ด์ ์ผ๋ถ ์์๋ฅผ ๊ณจ๋ผ๋ด์ ๋ง๋ ๋ถ๋ถ ์์ด ์ค, ๊ฐ ์์๊ฐ ์ด์ ์์๋ณด๋ค ํฌ๋ค๋ ์กฐ๊ฑด์ ๋ง์กฑํ๊ณ , ๊ทธ ๊ธธ์ด๊ฐ ์ต๋์ธ ๋ถ๋ถ ์์ด์ ์ผ์ปซ์ ํด๋น ๋ฌธ์ ์์ ๊ธธ์ด๊ฐ ์ต๋์ธ ๋ถ๋ถ์์ด์ ๊ฐ๋ง์ ์ฐธ์กฐํ์ฌ 1์ ๊ฐ์ฐํ๋ค๋ ํ์ด๋ ๋ค์ ํฌ์คํ ์ ๋ฌธ์ ๋ฅผ ํ์ด..