Algorithm/๋ฐฑ์ค(BOJ)
๐ ๋ฌธ์ N์ฅ์ ์นด๋๊ฐ ์๋ค. ๊ฐ๊ฐ์ ์นด๋๋ ์ฐจ๋ก๋ก 1๋ถํฐ N๊น์ง์ ๋ฒํธ๊ฐ ๋ถ์ด ์์ผ๋ฉฐ, 1๋ฒ ์นด๋๊ฐ ์ ์ผ ์์, N๋ฒ ์นด๋๊ฐ ์ ์ผ ์๋์ธ ์ํ๋ก ์์๋๋ก ์นด๋๊ฐ ๋์ฌ ์๋ค. ์ด์ ๋ค์๊ณผ ๊ฐ์ ๋์์ ์นด๋๊ฐ ํ ์ฅ ๋จ์ ๋๊น์ง ๋ฐ๋ณตํ๊ฒ ๋๋ค. ์ฐ์ , ์ ์ผ ์์ ์๋ ์นด๋๋ฅผ ๋ฐ๋ฅ์ ๋ฒ๋ฆฐ๋ค. ๊ทธ ๋ค์, ์ ์ผ ์์ ์๋ ์นด๋๋ฅผ ์ ์ผ ์๋์ ์๋ ์นด๋ ๋ฐ์ผ๋ก ์ฎ๊ธด๋ค. ์๋ฅผ ๋ค์ด N=4์ธ ๊ฒฝ์ฐ๋ฅผ ์๊ฐํด ๋ณด์. ์นด๋๋ ์ ์ผ ์์์๋ถํฐ 1234 ์ ์์๋ก ๋์ฌ์๋ค. 1์ ๋ฒ๋ฆฌ๋ฉด 234๊ฐ ๋จ๋๋ค. ์ฌ๊ธฐ์ 2๋ฅผ ์ ์ผ ์๋๋ก ์ฎ๊ธฐ๋ฉด 342๊ฐ ๋๋ค. 3์ ๋ฒ๋ฆฌ๋ฉด 42๊ฐ ๋๊ณ , 4๋ฅผ ๋ฐ์ผ๋ก ์ฎ๊ธฐ๋ฉด 24๊ฐ ๋๋ค. ๋ง์ง๋ง์ผ๋ก 2๋ฅผ ๋ฒ๋ฆฌ๊ณ ๋๋ฉด, ๋จ๋ ์นด๋๋ 4๊ฐ ๋๋ค. N์ด ์ฃผ์ด์ก์ ๋, ์ ์ผ ๋ง์ง๋ง์ ๋จ๊ฒ ๋๋ ์นด๋๋ฅผ ๊ตฌํ๋ ..
Algorithm/์ธํ๋ฐ(inflearn)
๐ ์ต๋์ ์ ๊ตฌํ๊ธฐ(๋
์ ์๊ณ ๋ฆฌ์ฆ) ์ด๋ฒ ์ ๋ณด์ฌ๋ฆผํผ์๋๋ํ์์ ์ข์ ์ฑ์ ์ ๋ด๊ธฐ ์ํ์ฌ ํ์๋ ์ ์๋์ด ์ฃผ์ N๊ฐ์ ๋ฌธ์ ๋ฅผ ํ๋ ค๊ณ ํ๋ค. ๊ฐ ๋ฌธ์ ๋ ๊ทธ๊ฒ์ ํ์์ ๋ ์ป๋ ์ ์์ ํธ๋ ๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ด ์ฃผ์ด์ง๊ฒ ๋๋ค. ์ ํ ์๊ฐ M ์์ N๊ฐ์ ๋ฌธ์ ์ค ์ต๋์ ์๋ฅผ ์ป์ ์ ์๋๋ก ํด์ผ ํ๋ค. (ํด๋น ๋ฌธ์ ๋ ํด๋น ์๊ฐ์ด ๊ฑธ๋ฆฌ๋ฉด ํธ๋ ๊ฑธ๋ก ๊ฐ์ฃผํ๋ค. ํ ์ ํ๋น ํ ๊ฐ๋ง ํ ์ ์๋ค.) ์
๋ ฅ์ค๋ช
์ฒซ ๋ฒ์งธ ์ค์ ๋ฌธ์ ์ ๊ฐ์ N(1
Algorithm/์ธํ๋ฐ(inflearn)
๐ ๋์ ๊ตํ(๋
์ ์๊ณ ๋ฆฌ์ฆ) ๋ค์๊ณผ ๊ฐ์ด ์ฌ๋ฌ ๋จ์์ ๋์ ๋ค์ด ์ฃผ์ด์ ธ ์์๋ ๊ฑฐ์ค๋ฆ๋์ ๊ฐ์ฅ ์ ์ ์์ ๋์ ์ผ๋ก ๊ตํํด์ฃผ๋ ค๋ฉด ์ด๋ป๊ฒ ์ฃผ๋ฉด ๋๋๊ฐ? ๊ฐ ๋จ์์ ๋์ ์ ๋ฌดํ์ ์ธ ์ ์๋ค. ์
๋ ฅ์ค๋ช
์ฒซ ๋ฒ์งธ ์ค์๋ ๋์ ์ ์ข
๋ฅ๊ฐ์ N(1
Algorithm/์ธํ๋ฐ(inflearn)
๐ ์ต๋ ๋ถ๋ถ ์ฆ๊ฐ์์ด(LIS) N๊ฐ์ ์์ฐ์๋ก ์ด๋ฃจ์ด์ง ์์ด์ด ์ฃผ์ด์ก์ ๋, ๊ทธ์ค์์ ๊ฐ์ฅ ๊ธธ๊ฒ ์ฆ๊ฐํ๋(์์ ์์์ ํฐ ์๋ก) ์์๋ค์ ์งํฉ์ ์ฐพ๋ ๋ฌธ์ ์ด๋ค. ์๋ฅผ ๋ค์ด, ์์๊ฐ 2, 7, 5, 8, 6, 4, 7, 12, 3์ด๋ฉด ๊ฐ์ฅ ๊ธธ๊ฒ ์ฆ๊ฐํ๋๋ก ์์๋ค์ ์ฐจ๋ก๋๋ก ๋ฝ์๋ด๋ฉด 2, 5, 6, 7, 12๋ฅผ ๋ฝ์๋ด์ด ๊ธธ์ด๊ฐ 5์ธ ์ต๋ ๋ถ๋ถ ์ฆ๊ฐ ์์ด์ ๋ง๋ค ์ ์๋ค. ์
๋ ฅ์ค๋ช
์ฒซ์งธ ์ค์ ์
๋ ฅ๋๋ ๋ฐ์ดํฐ์ ์ N(1= 0; j--) { if (arr[j] < arr[i] && max < dy[j]) { max = dy[j]; } } dy[i] = max + 1; } answer = Math.max(...dy); return answer; } let arr = [2, 7, 5, 8, 6, 4, 7, 12,..
Algorithm/์ธํ๋ฐ(inflearn)
๐ 02 - ๋๋ค๋ฆฌ ๊ฑด๋๊ธฐ(DP) ์ฒ ์๋ ํ๊ต์ ๊ฐ๋๋ฐ ๊ฐ์ธ์ ๋ง๋ฌ๋ค. ๊ฐ์ธ์ N๊ฐ์ ๋๋ก ๋ค๋ฆฌ๋ฅผ ๋ง๋ค์ด ๋์๋ค. ์ฒ ์๋ ๋ ๋ค๋ฆฌ๋ฅผ ๊ฑด๋ ๋ ํ ๋ฒ์ ํ ์นธ ๋๋ ๋ ์นธ์ฉ ๊ฑด๋๋ฐ๋ฉด์ ๋๋ค๋ฆฌ๋ฅผ ๊ฑด๋ ์ ์๋ค. ์ฒ ์๊ฐ ๊ฐ์ธ์ ๊ฑด๋๋ ๋ฐฉ๋ฒ์ ๋ช๊ฐ์ง์ผ๊น? ๐ ์์ค ์ฝ๋ ์ฐธ๊ณ ) ๊ณ๋จ์ค๋ฅด๊ธฐ function solution(n) { let answer = 0; let dy = Array.from({ length: n + 2 }, () => 0); dy[1] = 1; dy[2] = 2; for (let i = 3; i
Algorithm/์ธํ๋ฐ(inflearn)
๐ 01 - ๊ณ๋จ์ค๋ฅด๊ธฐ(๋์ ๊ณํ๋ฒ) ์ฒ ์๋ ๊ณ๋จ์ ์ค๋ฅผ ๋ ํ ๋ฒ์ ํ ๊ณ๋จ ๋๋ ๋ ๊ณ๋จ์ฉ ์ฌ๋ผ๊ฐ๋ค. ๋ง์ฝ ์ด 4๊ณ๋จ์ ์ค๋ฅธ๋ค๋ฉด ๊ทธ ๋ฐฉ๋ฒ์ ์๋ 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2๋ก 5๊ฐ์ง์ด๋ค. ๊ทธ๋ ๋ค๋ฉด ์ด N๊ณ๋จ์ผ ๋ ์ฒ ์๊ฐ ์ฌ๋ผ๊ฐ ์ ์๋ ๋ฐฉ๋ฒ์ ์๋ ๋ช ๊ฐ์ง์ธ๊ฐ? ๐ ํ์ด ๋ฐฉ๋ฒ(DFS, DP) DFS ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ์ฌ ๋ฌธ์ ๋ฅผ ํ์ด๋ณด์๋ค. ์ ๋ต์ ํ๋ฅญํ๊ฒ๋ ์ ๋์จ๋ค ๐ ํ์ง๋ง n์ ๊ฐ์ด ์ปค์ง๋ค๋ฉด...โ ์ฐ์ฐ ํ์๊ฐ ๊ธฐํ๊ธ์์ ์ผ๋ก ์ฆ๊ฐํ๊ฒ ๋๋ค. ์ด๋ฅผ ํด๊ฒฐํ ์ ์๋ ๋ฐฉ๋ฒ์ผ๋ก ๋์ ๊ณํ๋ฒ(dynamic programming, DP)์ด ์กด์ฌํ๋ค. function solution(n) { let answer = 0; function DFS(sum) { if (sum > n)..
Algorithm/์ธํ๋ฐ(inflearn)
๐ 07 - ์ฌ๋๋ผ ์์ผ๋๋(BFS ํ์ฉ) N*N์ ์ฌ๋๋ผ ์์ผ๋๋์ ์ง๋๊ฐ ๊ฒฉ์ํ์ ์ ๋ณด๋ก ์ฃผ์ด์ง๋ค. ๊ฐ ์ฌ์ 1๋ก ํ์๋์ด ์ํ์ข์ฐ์ ๋๊ฐ์ ์ผ๋ก ์ฐ๊ฒฐ๋์ด ์์ผ๋ฉฐ, 0์ ๋ฐ๋ค์ด๋ค. ์ฌ๋๋ผ ์์ผ๋๋์ ๋ช ๊ฐ์ ์ฌ์ด ์๋์ง ๊ตฌํ๋ ๋ฌธ์ ์ด๋ค. ๋ง์ฝ ์์ ๊ฐ๋ค๋ฉด ์ฌ์ ๊ฐ์๋ ์ด 5๊ฐ์ด๋ค. ์ฌ๋๋ผ ์์ผ๋๋(DFS) ๋ฌธ์ ์ ๊ฐ์ง๋ง ์ด๋ฒ์๋ BFS ์๊ณ ๋ฆฌ์ฆ์ ์ด์ฉํด ํ์ด๋ณด์๋ค. ์์ญ์ ํ์ํ๋ ๋ฌธ์ ์ ๊ฒฝ์ฐ์๋ ๋ณธ์ธ์๊ฒ ํธํ ๋ฐฉ๋ฒ์ ์ด์ฉํ์ฌ ํ๋ฉด ๋ ๊ฒ ๊ฐ๋ค..๐ค ๐ ํ์ด ๋ฐฉ๋ฒ ์ด์ค for ๋ฌธ์ ๋๋ฉด์ 1์ด ๋์จ๋ค๋ฉด ์ฌ์ ๋ฐ๊ฒฌํ ๊ฒ์ด๋ฏ๋ก ๋ฐฐ์ด์์ ํด๋น ์ขํ๋ฅผ 0์ผ๋ก ์ฌํ ๋นํ๊ณ answer++์ ํ๋ค. ๋ํ, ๋์ด ์ฐ์ ํ์์ ์ํด ํ์ ํด๋น ์ขํ๋ฅผ ์ถ๊ฐํ๋ค. while ๋ฌธ์ ๋๋ฉด์ ํ์์ shift ํ ์ขํ์ ๋ํด ..
Algorithm/์ธํ๋ฐ(inflearn)
๐ 06 - ์ฌ๋๋ผ ์์ผ๋๋(DFS ํ์ฉ) N*N์ ์ฌ๋๋ผ ์์ผ๋๋์ ์ง๋๊ฐ ๊ฒฉ์ํ์ ์ ๋ณด๋ก ์ฃผ์ด์ง๋ค. ๊ฐ ์ฌ์ 1๋ก ํ์๋์ด ์ํ์ข์ฐ์ ๋๊ฐ์ ์ผ๋ก ์ฐ๊ฒฐ๋์ด ์์ผ๋ฉฐ, 0์ ๋ฐ๋ค์ด๋ค. ์ฌ๋๋ผ ์์ผ๋๋์ ๋ช ๊ฐ์ ์ฌ์ด ์๋์ง ๊ตฌํ๋ ๋ฌธ์ ์ด๋ค. ๋ง์ฝ ์์ ๊ฐ๋ค๋ฉด ์ฌ์ ๊ฐ์๋ ์ด 5๊ฐ์ด๋ค. ๐ ํ์ด ๋ฐฉ๋ฒ ๋ฏธ๋ก ํ์ ๋ฌธ์ ์ ์ ์ฌํ ๋ฌธ์ ์ด๋ฏ๋ก ์ฐธ๊ณ ํ๋ฉด ์ข์ ๋ฏํ๋ค. ์ด์ค for ๋ฌธ์ ๋๋ฉด์ 1์ด ๋์จ๋ค๋ฉด ์ฌ์ ๋ฐ๊ฒฌํ ๊ฒ์ด๋ฏ๋ก ๋ฐฐ์ด์์ ํด๋น ์ขํ๋ฅผ 0์ผ๋ก ์ฌํ ๋นํ๊ณ answer++์ ํ๋ค. ํด๋น ์ขํ์ ๋ํด DFS๋ฅผ ๋๋ฉด์ ์ํ์ข์ฐ์ ๋๊ฐ์ ์ผ๋ก ์ฐ๊ฒฐ๋ ์ขํ๊ฐ ์๋์ง ํ์ํ๋ค. ์ฐ๊ฒฐ๋ ์ขํ๊ฐ ์๋ค๋ฉด 0์ผ๋ก ์ฌ ํ ๋นํ๊ณ ์ฐ๊ฒฐ๋ ์ขํ๋ก ์ด๋ํ๋ค. ๋ ์ด์ ์ฐ๊ฒฐ๋ ์ขํ๊ฐ ์๋ค๋ฉด DFS ํจ์๋ฅผ ๋ชจ๋ ์ข
๋ฃํ๊ณ ์ด์ค for ๋ฌธ์..