Logo
Hyunsu Blog
algorithm-dynamic-programming

๐Ÿ“†Published :Feb 24, 2024 โ€ข

๐Ÿ“†Updated :Feb 24, 2024 โ€ข

โ˜•๏ธ3min

๋™์ ๊ณ„ํš๋ฒ•

  • ๊ณจ๋“ ๋ž˜๋น— ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ ํ•ฉ๊ฒฉ์ž ๋˜๊ธฐ ํŒŒ์ด์ฌ ํŽธ์˜ 15์žฅ ์จ๋จธ๋ฆฌ๊ฐ€ ํฌํ•จ๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค.
  • ๋™์ ๊ณ„ํš๋ฒ•์€ ๋ชจ๋“  ๋ฌธ์ œ๋ฅผ ๋‹ค ํ’€์ง„ ๋ชปํ–ˆ๋‹ค. ์–ด๋ ต๊ธฐ๋„ ํ–ˆ์ง€๋งŒ, DP์˜ ์ž˜ ์•Œ๋ ค์ง„ ์—ฐ์Šต ๋ฌธ์ œ์— ์ต์ˆ™ํ•ด ์ง€๋Š” ๊ฒƒ์ด ๋ชฉํ‘œ์ด๋‹ค.

๋™์ ๊ณ„ํš๋ฒ• ๋ฌธ์ œ ์กฐ๊ฑด

  1. ์ตœ์  ๋ถ€๋ถ„ ๊ตฌ์กฐ(Optimal substructure) ํฐ ๋ฌธ์ œ์˜ ํ•ด๊ฒฐ์ฑ…์€ ์ž‘์€ ๋ฌธ์ œ์˜ ํ•ด๊ฒฐ์ฑ…์˜ ํ•ฉ์œผ๋กœ ๊ตฌ์„ฑํ•  ์ˆ˜ ์žˆ์–ด์•ผ ํ•œ๋‹ค.
    ๊ตฌํ˜„ ๋ฐฉ๋ฒ• : ์ ํ™”์‹ ์„ธ์šฐ๊ธฐ

  2. ์ค‘๋ณต ๋ถ€๋ถ„ ๋ฌธ์ œ(Overlapping subproblems) ์ž‘์€ ๋ฌธ์ œ๋“ค์ด ๊ฐ™์•„์•ผ ํ•˜๊ณ  ๋ฐ˜๋ณต๋˜์–ด์•ผ ํ•œ๋‹ค. ๊ตฌํ˜„ ๋ฐฉ๋ฒ• : ๋ฉ”๋ชจ์ด์ œ์ด์…˜์„ ํ†ตํ•ด ๋ฐ˜๋ณต๋˜๋Š” ์ž‘์€ ๋ฌธ์ œ์— ์—ฐ์‚ฐ ํšŸ์ˆ˜๋ฅผ ์ค„์—ฌ ์—ฐ์‚ฐ ํšจ์œจํ™” ์ฆ๋Œ€.

๋ฌธ์ œ ์ ์šฉ

LIS๊ธธ์ด ๊ณ„์‚ฐํ•˜๊ธฐ

๋ฌธ์ œ ์„ค๋ช… ์ •์ˆ˜ ๋ฐฐ์—ด nums์—์„œ LIS์˜ ๊ธธ์ด๋ฅผ ์ฐพ๋Š” ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•˜์„ธ์š”. nums์˜ ์ตœ๋Œ€ ๊ธธ์ด 1,000์˜ ์ •์ˆ˜ ๋ฐฐ์—ด nums์˜ ๊ฐ ์š”์†Œ๋Š” -1000 ์ด์ƒ 1000์ดํ•˜์˜ ์ •์ˆ˜ ์ž…๋‹ˆ๋‹ค. ์ž…๋ ฅ [1,4,2,3,1,5,7,3], 5 [3,2,1] 1

LIS(Longest Increasing Subsequence) ๋Š” ์ตœ์žฅ ์ฆ๊ฐ€ ๋ถ€๋ถ„ ์ˆ˜์—ด๋กœ์„œ ์ฃผ์–ด์ง„ ์ˆ˜์—ด์—์„œ ๋งŒ๋“ค์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ๋ถ€๋ถ„ ์ˆ˜์—ด์—์„œ ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ์ˆ˜์—ด์„ ๊ตฌํ•œ๋‹ค. ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์„ ๊ตฌํ•  ๋•Œ ์ „ํ›„ ๊ด€๊ณ„๋ฅผ ์œ ์ง€ ํ•ด์•ผ ํ•œ๋‹ค.

1 4 2 3 1 5 7 3 ์—์„œ ์ „ํ›„ ๊ด€๊ณ„๋ฅผ ์œ ์ง€ํ•œ ์ˆ˜์—ด 1 2 3 5 ์ „ํ›„ ๊ด€๊ณ„๋ฅผ ์œ ์ง€ํ•˜์ง€ ์•Š์€ ์ˆ˜์—ด 1 3 2 5 (์ธ๋ฑ์Šค์˜ ์ „ ํ›„ ์ˆœ์„œ๋ฅผ ๋ฐ”๊พธ๋ฉด ์•ˆ๋œ๋‹ค)

์ด ๋ฌธ์ œ๋ฅผ brute force๋กœ ์ ‘๊ทผ ํ•  ๊ฒฝ์šฐ, 1๋กœ ๋๋‚˜๋Š” ๋ถ€๋ถ„์ˆ˜์—ด, 4๋กœ ๋๋‚˜๋Š” ๋ถ€๋ถ„์ˆ˜์—ด, 2์œผ๋กœ ๋๋‚˜๋Š” ๋ถ€๋ถ„์ˆ˜์—ด,... 3๋กœ ๋๋‚˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์—์„œ ์ฆ๊ฐ€ํ•˜๋Š” ์กฐ๊ฑด์„ ๋งŒ์กฑํ•˜๋Š” ์ตœ๋Œ€ ๊ธธ์ด๋ฅผ ๊ตฌํ•˜๊ฒŒ ๋  ๊ฒƒ ์ด๋‹ค. ์‹œ๊ฐ„๋ณต์žก๋„๋Š” 2^1000 ์ด ๋˜๋ฏ€๋กœ ์—ฐ์‚ฐ์˜ ์ตœ์ ํ™”๊ฐ€ ํ•„์š”ํ•˜๋‹ค.

1 4 2 3 ์—์„œ [1] 1๋กœ ๋๋‚˜๋Š” LIS๊ธธ์ด [1,4] 4๋กœ ๋๋‚˜๋Š” LIS๊ธธ์ด [1,4,2] 2๋กœ ๋๋‚˜๋Š” LIS๊ธธ์ด [1,4,2,3,] 3๋กœ ๋๋‚˜๋Š” LIS๊ธธ์ด ์ตœ์  ๋ถ€๋ถ„ ๊ตฌ์กฐ : ๊ฐ ์ˆซ์ž๋กœ ๋๋‚˜๋Š” LIS๊ธธ์ด ์ค‘ ์ตœ๋Œ€๊ฐ’ (์—ฌ๊ธฐ์„œ ๊ฐ ์ˆซ์ž๋Š” ๊ฐ€์žฅ ์ž‘์€ ๊ธธ์ด 1 ์„ ์•Œ์•„์•ผ ํ•œ๋‹ค.) ์ค‘๋ณต ๋ถ€๋ถ„ ๋ฌธ์ œ : 2๋กœ ๋๋‚˜๋Š” LIS์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•  ๋•, 4๋กœ ๋๋‚˜๋Š” LIS ๊ธธ์ด๋ฅผ ์ฐธ์กฐํ•œ๋‹ค. ๋ฌธ์ œ์—์„œ ๊ตฌํ•˜๊ณ ์ž ํ•˜๋Š”๊ฒƒ dp[N]: arr[N]์ด ๋งˆ์ง€๋ง‰ ์ˆซ์ž๋กœ ๋๋‚˜๋Š” LIS์˜ ๊ธธ์ด. dp์˜ ์ ํ™”์‹ ์€ DP[N] = max(dp[k] )+1 ์ด ๋˜๊ณ  ์—ฌ๊ธฐ์˜ ์กฐ๊ฑด์€ `arr[k]<arr[N]` ์ด ๋œ๋‹ค. k: 0~ N-1 , N ์ด์ „์˜ ์ˆซ์ž๋ฅผ ๋ณด๋Š” ํฌ์ธํ„ฐ ์ข…๋ฃŒ ์กฐ๊ฑด : dp[1] =1 //๊ธธ์ด๊ฐ€ 1์ผ ๋•Œ, ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ์ˆ˜์—ด์˜ ๊ธธ์ด๋Š” 1๊ฐœ์ด๋‹ค. //์‹œ๊ฐ„ ๋ณต์žก๋„ : O(n^2) function solution(nums){ let dp = Array.from({length: nums.length+1}, ()=> 1) for (let i=0; i<nums.length; i++){ for(let j=0; j<i;j++){ if(nums[i]>nums[j]){ dp[i] = Math.max(dp[i], dp[j]+1) } } } return Math.max(...dp) }

LCS ๊ธธ์ด ๊ณ„์‚ฐํ•˜๊ธฐ

๋ฌธ์ œํ’€์ด ์ฃผ์–ด์ง„ ๋‘ ๊ฐœ์˜ ๋ฌธ์ž์—ด str1๊ณผ str2์— ๋Œ€ํ•ด ์ตœ์žฅ ๊ณตํ†ต ๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ๊ธธ์ด๋ฅผ ๊ณ„์‚ฐํ•˜๋Š” solution() ํ•จ์ˆ˜๋ฅผ ๊ตฌํ˜„ํ•˜์„ธ์š”.

์ œ์•ฝ ์กฐ๊ฑด

  • ๊ฐ ๋ฌธ์ž์—ด str1๊ณผ str2์˜ ๊ธธ์ด๋Š” 1 ์ด์ƒ 1,000์ดํ•˜ ์ž…๋‹ˆ๋‹ค.
  • ๋ฌธ์ž์—ด์€ ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž, ์†Œ๋ฌธ์ž๋กœ ๊ตฌ์„ฑ ๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค.

LCS(Longest Common Subsequence) ๋Š” ๋‘ ์ˆ˜์—ด์—์„œ ๊ณตํ†ต์œผ๋กœ ๋ฐœ๊ฒฌํ•  ์ˆ˜ ์žˆ๋Š” ๊ฐ€์žฅ ๊ธด ๋ถ€๋ถ„ ์ˆ˜์—ด์„ ์˜๋ฏธํ•œ๋‹ค.

๋‘ ๊ฐœ์˜ ๋ฌธ์ž์—ด์˜ ์ธ๋ฑ์Šค๋ฅผ ํ•˜๋‚˜์”ฉ ๋น„๊ตํ•ด ๋ด์•ผ ํ•œ๋‹ค.

๋ฌธ์ œ์—์„œ ๊ตฌํ•˜๊ณ ์ž ํ•˜๋Š”๊ฒƒ dp[i][j]: ์ฒซ ๋ฌธ์ž์—ด์˜ ์ธ๋ฑ์Šค 0~ i๋ฒˆ์งธ๊นŒ์ง€์˜ ๋ฌธ์ž์—ด๊ณผ ๋‘๋ฒˆ์งธ ๋ฌธ์ž์—ด ์ธ๋ฑ์Šค 0~j๋ฒˆ์งธ ๊นŒ์ง€์˜ ๋ฌธ์ž์—ด์„ ๋น„๊ตํ–ˆ์„ ๋•Œ,๊ณตํ†ต ๋ถ€๋ถ„ ๋ฌธ์ž์—ด์˜ ์ตœ๋Œ€ ๊ธธ์ด ์ ํ™”์‹ dp[i][j] = dp[i-1][j-1]+1 if str1[i] === str2[j] dp[i][j] = dp[i-1,j][i,j-1] if str1[i] !== str2[j] dp[0][0] = 0 // ์‹œ๊ฐ„๋ณต์žก๋„: O(str1.length*str2.length)

ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜ ๋ฌธ์ œ ์ถœ์ฒ˜: ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

๋ฌธ์ œ ์„ค๋ช… ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜๋Š” F(0) = 0, F(1) = 1์ผ ๋•Œ, 1 ์ด์ƒ์˜ n์— ๋Œ€ํ•˜์—ฌ F(n) = F(n-1) + F(n-2) ๊ฐ€ ์ ์šฉ๋˜๋Š” ์ˆ˜ ์ž…๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ๋“ค์–ด

F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = 2 + 3 = 5 ์™€ ๊ฐ™์ด ์ด์–ด์ง‘๋‹ˆ๋‹ค.

2 ์ด์ƒ์˜ n์ด ์ž…๋ ฅ๋˜์—ˆ์„ ๋•Œ, n๋ฒˆ์งธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜๋ฅผ >1234567์œผ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ๋ฆฌํ„ดํ•˜๋Š” ํ•จ์ˆ˜, solution์„> ์™„์„ฑํ•ด ์ฃผ์„ธ์š”.

์ œํ•œ ์‚ฌํ•ญ n์€ 2 ์ด์ƒ 100,000 ์ดํ•˜์ธ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.

์ž…๋ ฅ๊ฐ’์ด ์‹ญ๋งŒ์ด๋‹ˆ O(n)์˜ ๋ณต์žก๋„๋Š” ๊ฐ€๋Šฅํ•˜๋‹ค.

ํ”ผ๋ณด๋‚˜์น˜์˜ ์ˆ˜์—์„œ ์ตœ์  ๋ถ€๋ถ„ ๊ตฌ์กฐ๋Š” F(n)์„ ๊ตฌํ•˜๊ธฐ ์œ„ํ•ด ์ด๋ฏธ ๊ณ„์‚ฐ ๋˜์–ด์ง„ ๋ฐ”๋กœ ์•ž์˜ ๋‘ ํ•ญ์˜ ๊ฐ ๊ฒฐ๊ณผ ๊ฐ’,F(n-1), F(n-2)์ด๋‹ค. ๊ฒฐ๊ณผ ๊ฐ’๋“ค์„ ๊ตฌํ•ด์•ผ ํฐ ๊ฐ’์ธ F(n)์„ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค.

๋งŒ์•ฝ ์ด ๋ฌธ์ œ๋ฅผ ์žฌ๊ท€๋ฅผ ์‚ฌ์šฉํ•˜๊ฒŒ ๋œ๋‹ค๋ฉด, F(4)=F(3)+F(2) ์ผ ๋•Œ F(3) ์„ ๊ณ„์‚ฐ์‹œ F(2) +F(1) ์—์„œ F(2)๋ฅผ ์ค‘๋ณต์œผ๋กœ ๊ณ„์‚ฐํ•˜๋Š” ๋ถ€๋ถ„์„ ๋ฉ”๋ชจ์ด์ œ์ด์…˜์„ ํ†ตํ•ด ์ตœ์ ํ™” ํ•  ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ,์ค‘๋ณต ๋ถ€๋ถ„ ๋ฌธ์ œ์— ํ•ด๋‹น ๋œ๋‹ค.

์•„๋ž˜๋Š” ๋ฉ”๋ชจ์ด์ œ์ด์…˜์„ ๋ฐ”ํ…€์—… ๋ฐฉ์‹์„ ์ ์šฉํ•˜์˜€๋‹ค.

function solution(n) { if(n<2) return 1%1234567 let a=0, b=1 let remainder; for(let i=2; i<=n; i++){ remainder = (a+ b)%1234567 a = b b = remainder } return b; }

2 x n ํƒ€์ผ๋ง ๋ฌธ์ œ์ถœ์ฒ˜: ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

๋ฌธ์ œ์„ค๋ช… ๋ฌธ์ œ ์„ค๋ช… ๊ฐ€๋กœ ๊ธธ์ด๊ฐ€ 2์ด๊ณ  ์„ธ๋กœ์˜ ๊ธธ์ด๊ฐ€ 1์ธ ์ง์‚ฌ๊ฐํ˜•๋ชจ์–‘์˜ ํƒ€์ผ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ์ง์‚ฌ๊ฐํ˜• ํƒ€์ผ์„ ์ด์šฉํ•˜์—ฌ ์„ธ๋กœ์˜ ๊ธธ์ด๊ฐ€ 2์ด๊ณ  ๊ฐ€๋กœ์˜ ๊ธธ์ด๊ฐ€ n์ธ ๋ฐ”๋‹ฅ์„ ๊ฐ€๋“ ์ฑ„์šฐ๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ํƒ€์ผ์„ ์ฑ„์šธ ๋•Œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด 2๊ฐ€์ง€ ๋ฐฉ๋ฒ•์ด ์žˆ์Šต๋‹ˆ๋‹ค.

ํƒ€์ผ์„ ๊ฐ€๋กœ๋กœ ๋ฐฐ์น˜ ํ•˜๋Š” ๊ฒฝ์šฐ ํƒ€์ผ์„ ์„ธ๋กœ๋กœ ๋ฐฐ์น˜ ํ•˜๋Š” ๊ฒฝ์šฐ ์˜ˆ๋ฅผ๋“ค์–ด์„œ n์ด 7์ธ ์ง์‚ฌ๊ฐํ˜•์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ฑ„์šธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

alt text

์ง์‚ฌ๊ฐํ˜•์˜ ๊ฐ€๋กœ์˜ ๊ธธ์ด n์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ์ด ์ง์‚ฌ๊ฐํ˜•์„ ์ฑ„์šฐ๋Š” ๋ฐฉ๋ฒ•์˜ ์ˆ˜๋ฅผ return ํ•˜๋Š” solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.

์ œํ•œ์‚ฌํ•ญ ๊ฐ€๋กœ์˜ ๊ธธ์ด n์€ 60,000์ดํ•˜์˜ ์ž์—ฐ์ˆ˜ ์ž…๋‹ˆ๋‹ค. ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ๋งŽ์•„ ์งˆ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ, ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ 1,000,000,007์œผ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ returnํ•ด์ฃผ์„ธ์š”. ์ž…์ถœ๋ ฅ ์˜ˆ n result 4 5

์ด ๋ฌธ์ œ๊ฐ€ DP์ธ ์ด์œ ๋Š”

  1. ์ตœ์  ๋ถ€๋ถ„ ๊ตฌ์กฐ

alt text

n = 3์€ n = 1์ผ ๋•Œ ๊ฒฝ์šฐ์˜ ์ˆ˜์™€ n=2์ผ ๋•Œ ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ทธ๋Œ€๋กœ ์ด์šฉํ•œ๋‹ค. ์„ธ๋กœ๊ธธ์ด๋Š” ์ •ํ•ด์ ธ ์žˆ๊ณ , ์ฃผ์–ด์ง„ ํƒ€์ผ์˜ ๊ฐ€๋กœ ๊ธธ์ด๋Š” 1๋˜๋Š” 2 ์ด๋ฏ€๋กœ ๊ฐ€๋กœ ๊ธธ์ด๊ฐ€ 1์ผ ๋•Œ์™€ 2์ผ ๋•Œ ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ๋‹ฌ๋ผ์ง„๋‹ค. ๊ทธ๋Ÿผ ๋งˆ์ง€๋ง‰์— ์˜ฌ ํƒ€์ผ์ด ๊ฐ€๋กœ๊ธธ์ด 1์ธ ํƒ€์ผ๊ณผ 2์ธ ํƒ€์ผ ๋‘ ๊ฐœ๋กœ ๊ฒฐ์ • ์ง€์–ด ์ง€๋ฏ€๋กœ, n-1 ๊ฒฝ์šฐ์˜ ์ˆ˜ , n-2 ๊ฒฝ์šฐ์˜ ์ˆ˜ ํ•ฉ์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค. n =3์„ ํ’€๊ธฐ ์œ„ํ•ด์„ , n =2 ๊ฒฝ์˜์˜ ์ˆ˜์™€ n=1์ผ๋•Œ์˜ ๊ฐ€์ง“์ˆ˜์— ์˜์กดํ•œ๋‹ค.

  1. ์ค‘๋ณต ๋ถ€๋ถ„ ๋ฌธ์ œ ์ ํ™”์‹์œผ๋กœ ๋‚˜ํƒ€๋‚ด๋ฉด dp[n] = dp[n-1]+dp[n-2] ๊ฐ€ ๋˜๊ณ , ์ ํ™”์‹์„ ์žฌ๊ท€ ์—ฐ์‚ฐ์„ ์‚ฌ์šฉํ•˜๊ฒŒ ๋˜๋ฉด, ํ”ผ๋ณด๋‚˜์น˜์ˆ˜์—ด์„ ์žฌ๊ท€๋กœ ํ‘œํ˜„ํ•œ ๋ฐฉ์‹ ์ฒ˜๋Ÿผ ๊ฐ™์€ ์—ฐ์‚ฐ์„ ๋ฐ˜๋ณตํ•˜๋Š” ์ผ์ด ์ƒ๊ธฐ๋ฏ€๋กœ ๋ฉ”๋ชจ์ด์ œ์ด์…˜์„ ์‚ฌ์šฉํ•œ๋‹ค. ์กฐ๊ฑด์— ๋งŒ์กฑํ•˜๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.
function solution(n) { let dp = Array.from({length: n+1},()=>0); dp[1] = 1; dp[2] = 2; if(n <= 2 ) return dp[n]; for(let i=3; i<=n; i++){ dp[i] = (dp[i-1] + dp[i-2])%1000000007; } return dp[n] }

์ •์ˆ˜ ์‚ผ๊ฐํ˜• (๋ฌธ์ œ์ถœ์ฒ˜: ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค)[]

alt text

์œ„์™€ ๊ฐ™์€ ์‚ผ๊ฐํ˜•์˜ ๊ผญ๋Œ€๊ธฐ์—์„œ ๋ฐ”๋‹ฅ๊นŒ์ง€ ์ด์–ด์ง€๋Š” ๊ฒฝ๋กœ ์ค‘, ๊ฑฐ์ณ๊ฐ„ ์ˆซ์ž์˜ ํ•ฉ์ด ๊ฐ€์žฅ ํฐ ๊ฒฝ์šฐ๋ฅผ ์ฐพ์•„๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์•„๋ž˜ ์นธ์œผ๋กœ ์ด๋™ํ•  ๋•Œ๋Š” ๋Œ€๊ฐ์„  ๋ฐฉํ–ฅ์œผ๋กœ ํ•œ ์นธ ์˜ค๋ฅธ์ชฝ ๋˜๋Š” ์™ผ์ชฝ์œผ๋กœ๋งŒ ์ด๋™ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด 3์—์„œ๋Š” ๊ทธ ์•„๋ž˜์นธ์˜ 8 ๋˜๋Š” 1๋กœ๋งŒ ์ด๋™์ด ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

์‚ผ๊ฐํ˜•์˜ ์ •๋ณด๊ฐ€ ๋‹ด๊ธด ๋ฐฐ์—ด triangle์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ๊ฑฐ์ณ๊ฐ„ ์ˆซ์ž์˜ ์ตœ๋Œ“๊ฐ’์„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•˜์„ธ์š”.

์ œํ•œ์‚ฌํ•ญ ์‚ผ๊ฐํ˜•์˜ ๋†’์ด๋Š” 1 ์ด์ƒ 500 ์ดํ•˜์ž…๋‹ˆ๋‹ค. ์‚ผ๊ฐํ˜•์„ ์ด๋ฃจ๊ณ  ์žˆ๋Š” ์ˆซ์ž๋Š” 0 ์ด์ƒ 9,999 ์ดํ•˜์˜ ์ •์ˆ˜์ž…๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ triangle result [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30

๋ฌธ์ œ์—์„œ ๊ตฌํ•˜๊ณ ์ž ํ•˜๋Š” ๊ฒƒ์€ ์‚ผ๊ฐํ˜•์˜ ๊ผญ๋Œ€๊ธฐ์—์„œ ๋ฐ”๋‹ฅ๊นŒ์ง€ ๊ฑฐ์น˜๋Š” ์ˆซ์ž๋“ค์˜ ํ•ฉ ์ค‘ ๊ฐ€์žฅ ํฐ ์ตœ๋Œ€๊ฐ’์„ ๊ตฌํ•œ๋‹ค.

์ด ๋ฌธ์ œ๋ฅผ brute force๋ฐฉ์‹์œผ๋กœ ํ’€๊ฒŒ ๋˜๋ฉด ๊ผญ๋Œ€๊ธฐ 7->3 ์œผ๋กœ ์‹œ์ž‘ํ•˜์—ฌ ๋„์ฐฉํ•˜๋Š” ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜, 7->8 ๋กœ ์‹œ์ž‘ํ•˜์—ฌ ๋„์ฐฉํ•˜๋Š” ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜์—์„œ ํ•ฉ์„ ์ฐพ์•„๋‚ด์–ด ๊ทธ ์ค‘์˜ ์ตœ๋Œ€๊ฐ’์„ ๊ตฌํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ์ ‘๊ทผํ•œ๋‹ค, ํ•˜์ง€๋งŒ, ๋†’์ด๊ฐ€ 500์ผ ๋•Œ ๊ฒฝ์šฐ์˜ ์ˆ˜๋Š” ๋†’์ด๊ฐ€ 1์ผ ๋•Œ ๊ฒฝ์šฐ์˜ ์ˆ˜ 1, ๋†’์ด๊ฐ€ 2์ผ ๋•Œ ๊ฒฝ์šฐ์˜ ์ˆ˜ 2, ๋†’์ด๊ฐ€ 3์ผ ๋•Œ ๊ฒฝ์šฐ์˜ ์ˆ˜ 4 , 2^(๋†’์ด) ๋กœ 2^500 ์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€๊ฒŒ ๋œ๋‹ค. ์ด๋ฅผ ํ†ตํ•ด DP๋กœ ์—ฐ์‚ฐ์„ ์ตœ์ ํ™” ํ•ด์•ผ ํ•œ๋‹ค.

๋ฐ”๋‹ฅ์— ๋„์ฐฉํ–ˆ์„ ๋•Œ [4, 5, 2, 6, 5] ์— ๋”ฐ๋ผ 4๋กœ ๋„์ฐฉํ•˜๋Š” ๊ฒฝ์šฐ, 5๋กœ ๋„์ฐฉํ•˜๋Š” ๊ฒฝ์šฐ, 6๋กœ ๋„์ฐฉํ•˜๋Š” ๊ฒฝ์šฐ, 5๋กœ ๋„์ฐฉํ•˜๋Š” ๊ฒฝ์šฐ์—์„œ ์ตœ๋Œ€๊ฐ’์ด ๊ผญ๋Œ€๊ธฐ๋ถ€ํ„ฐ ๋ฐ”๋‹ฅ๊นŒ์ง€ ๊ฑฐ์น˜๋Š” ์ˆซ์ž๋“ค์˜ ์ตœ๋Œ€๊ฐ’์ด ๋œ๋‹ค.

๋ฐ”๋‹ฅ์˜ 4๋Š” ๊ทธ ์œ„ ๋‹จ๊ณ„์˜ ํ•ฉ์— ์˜์กดํ•˜๊ฒŒ ๋˜๋ฏ€๋กœ, ์ตœ์  ๋ถ€๋ถ„ ๊ตฌ์กฐ์— ๋งŒ์กฑํ•œ๋‹ค.

๊ทธ๋ฆฌ๊ณ  ๊ฒฝ๋กœ์—์„œ ๋„์ฐฉํ•˜๋Š” ์ง€์ ์—๋Š” ๊ธฐ์–ตํ•ด๋‘” ๊ทธ ์œ„ ๋‹จ๊ณ„์˜ ํ•ฉ์„ ๊ฐ€์ ธ์™€ ๋„์ฐฉ์ง€์ ์„ ํ•ฉ์‚ฐํ•œ๋‹ค๋Š” ์ ์—์„œ ์ค‘๋ณต ๋ถ€๋ถ„ ๋ฌธ์ œ์— ํฌํ•จ๋œ๋‹ค.

function solution(triangle) { for (let row = triangle.length - 2; row >= 0; row--) { for (let col = 0; col < triangle[row].length; col++) { // ์•„๋ž˜์ชฝ ํ–‰์˜ ์ธ์ ‘ํ•œ ๋‘ ์ˆซ์ž ์ค‘ ๋” ํฐ ์ˆซ์ž๋ฅผ ํ˜„์žฌ ์ˆซ์ž์— ๋”ํ•จ triangle[row][col] += Math.max(triangle[row + 1][col], triangle[row + 1][col + 1]); } } // ์ตœ์ƒ๋‹จ์— ์ตœ๋Œ“๊ฐ’์ด ์กด์žฌํ•จ return triangle[0][0]; }

Hi, I'm Hyunsu ๐Ÿ‘‹

Profile Image

์•ˆ๋…•ํ•˜์„ธ์š”. ํ”„๋ก ํŠธ์—”๋“œ ๊ฐœ๋ฐœ์ž ์ฃผํ˜„์ˆ˜์ž…๋‹ˆ๋‹ค.

๊ฐœ๋ฐœ์„ ํ†ตํ•ด ์‚ฌ์šฉ์ž๋“ค์—๊ฒŒ ํ’๋ถ€ํ•˜๊ณ  ๊ฐ€์น˜ ์žˆ๋Š” ๊ฒฝํ—˜์„ ์ œ๊ณตํ•˜๋Š” ์ผ์— ๋ฟŒ๋“ฏํ•จ์„ ๋Š๋‚๋‹ˆ๋‹ค.

์˜ต์‹œ๋””์–ธ(Obsidian)์—์„œ ํ˜„์žฌ ๋ธ”๋กœ๊ทธ๋กœ ํ•˜๋‚˜์”ฉ ๊ธ€์„ ์˜ฎ๊ธฐ๋Š” ๊ณผ์ •์— ์žˆ์–ด์š”. โ˜•๏ธ ๐Ÿ‘ฉโ€๐Ÿ’ป โ›ท

Github on ViewReach Me Out