Algorithm/ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค 51

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค/PythonํŒŒ์ด์ฌ] ์…”ํ‹€๋ฒ„์Šค(2018 ์นด์นด์˜ค ์ฝ”๋”ฉํ…Œ์ŠคํŠธ 1์ฐจ)

๋ฌธ์ œ ๋งํฌ: programmers.co.kr/learn/courses/30/lessons/17678์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - [1์ฐจ] ์…”ํ‹€๋ฒ„์Šค10 60 45 ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"] "18:00"programmers.co.kr ๋ฌธ์ œ ์„ค๋ช…์‹œ๊ฐ„ ๊ณ„์‚ฐ์„ ์‰ฝ๊ฒŒ ํ•˜๊ธฐ ์œ„ํ•ด์„œ "HH:MM" ํ˜•์‹์˜ ์‹œ๊ฐ„์„ ๋ชจ๋‘ ๋ถ„์œผ๋กœ ๋ณ€ํ™˜ํ•ด์„œ ์ƒ๊ฐํ–ˆ์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด "09:10"์ธ ๊ฒฝ์šฐ 9*60 + 10 = 550(๋ถ„)์œผ๋กœ ๋ณ€ํ™˜ํ•ฉ๋‹ˆ๋‹ค. ์ด๋Ÿฐ ์‹์œผ๋กœ ๋ณ€ํ™˜ํ•˜๋ฉด ์ •์ˆ˜ ๋น„๊ต ์—ฐ์‚ฐ์„ ํ†ตํ•ด ๋ˆ„๊ฐ€ ๋จผ์ € ์™”๋Š”์ง€๋ฅผ ํŒ๋‹จํ•  ์ˆ˜..

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค / Python ํŒŒ์ด์ฌ] ๋‹คํŠธ ๊ฒŒ์ž„(2018 ์นด์นด์˜ค ์ฝ”๋”ฉํ…Œ์ŠคํŠธ 1์ฐจ)

๋ฌธ์ œ ๋งํฌ: programmers.co.kr/learn/courses/30/lessons/17682 ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - [1์ฐจ] ๋‹คํŠธ ๊ฒŒ์ž„ programmers.co.kr ๋ฌธ์ œ ์„ค๋ช…result, prev, curr์— ๊ฐ๊ฐ ๋ˆ„์  ์ ์ˆ˜, ๋ฐ”๋กœ ์ง์ „ ์ ์ˆ˜, ํ˜„์žฌ ์ ์ˆ˜๋ฅผ ์ €์žฅํ–ˆ์Šต๋‹ˆ๋‹ค. ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ๋ฌธ์ž์—ด์˜ ๋ฌธ์ž๋ฅผ ํ•˜๋‚˜์”ฉ ๋Œ๋ฉด์„œ ๋‹ค์Œ์„ ๊ณ„์‚ฐํ•ฉ๋‹ˆ๋‹ค. ๋ฌธ์ž๊ฐ€ ์ˆซ์ž(0~9)๋ผ๋ฉด 1) result์— prev๋ฅผ ๋”ํ•œ๋‹ค. (prev๋Š” ์ด์ œ ๋ณด๋„ˆ์Šค๋‚˜ ์˜ต์…˜์ด ์ ์šฉ ์•ˆ๋˜๋ฏ€๋กœ) 2) curr๊ฐ€ prev๊ฐ€ ๋œ๋‹ค. 3) ํ˜„์žฌ ๋ฌธ์ž๊ฐ€ curr๊ฐ€ ๋œ๋‹ค. ๋ฌธ์ž๊ฐ€ ๋ณด๋„ˆ์Šค(S, D, T)๋ผ๋ฉด 1) D์ผ ๊ฒฝ์šฐ curr์„ ์ œ๊ณฑํ•œ๋‹ค. 2) T์ผ ๊ฒฝ์šฐ curr์„ ์„ธ์ œ๊ณฑ ํ•œ๋‹ค. ๋ฌธ์ž๊ฐ€ ์˜ต์…˜(*, #)์ด๋ผ๋ฉด 1) *์ผ ๊ฒฝ์šฐ prev์™€ curr์— 2๋ฅผ..

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค / Python] ๋น„๋ฐ€์ง€๋„(2018 ์นด์นด์˜ค ์ฝ”๋”ฉํ…Œ์ŠคํŠธ 1์ฐจ)

๋ฌธ์ œ ๋งํฌ: programmers.co.kr/learn/courses/30/lessons/17681์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - [1์ฐจ] ๋น„๋ฐ€์ง€๋„๋น„๋ฐ€์ง€๋„ ๋„ค์˜ค๋Š” ํ‰์†Œ ํ”„๋กœ๋„๊ฐ€ ๋น„์ƒ๊ธˆ์„ ์ˆจ๊ฒจ๋†“๋Š” ์žฅ์†Œ๋ฅผ ์•Œ๋ ค์ค„ ๋น„๋ฐ€์ง€๋„๋ฅผ ์†์— ๋„ฃ์—ˆ๋‹ค. ๊ทธ๋Ÿฐ๋ฐ ์ด ๋น„๋ฐ€์ง€๋„๋Š” ์ˆซ์ž๋กœ ์•”ํ˜ธํ™”๋˜์–ด ์žˆ์–ด ์œ„์น˜๋ฅผ ํ™•์ธํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ์•”ํ˜ธ๋ฅผ ํ•ด๋…ํ•ด์•ผ ํ•œ๋‹ค. ๋‹คprogrammers.co.kr ๋ฌธ์ œ ์„ค๋ช…๋‘ ์ง€๋„๋ฅผ ๊ฐ๊ฐ ์ด์ง„์ˆ˜๋กœ ๋ณ€ํ™˜ํ•œ๋‹ค. ๋‘ ์ง€๋„๋ฅผ ํ•ฉ์นœ๋‹ค.ํ•ฉ์นœ ์ง€๋„๋ฅผ ์ถœ๋ ฅ ํฌ๋งท์— ๋งž๊ฒŒ ๊ณต๋ฐฑ๊ณผ ๋ฒฝ์œผ๋กœ ์น˜ํ™˜ํ•œ๋‹ค. ์œ„์™€ ๊ฐ™์€ ์ˆœ์„œ๋กœ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ–ˆ์Šต๋‹ˆ๋‹ค. ์ด๋•Œ 1, 2๋ฒˆ ๊ณผ์ •์€ ๋‹ค์Œ ์ฝ”๋“œ๋กœ ํ‘œํ˜„๋ฉ๋‹ˆ๋‹ค. answer.append(bin(arr1[i] | arr2[i])[2:].zfill(n))bin(arr1[i] | arr2[i])๋Š” ๊ฐ๊ฐ์˜ ์ง€๋„๋ฅผ ์ด์ง„์ˆ˜๋กœ ๋ณ€..

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค / Python] ๋„๋‘‘์งˆ

๋ฌธ์ œ ๋งํฌ: programmers.co.kr/learn/courses/30/lessons/42897 ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ๋„๋‘‘์งˆ ๋„๋‘‘์ด ์–ด๋Š ๋งˆ์„์„ ํ„ธ ๊ณ„ํš์„ ํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ๋งˆ์„์˜ ๋ชจ๋“  ์ง‘๋“ค์€ ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ๋™๊ทธ๋ž—๊ฒŒ ๋ฐฐ์น˜๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฐ ์ง‘๋“ค์€ ์„œ๋กœ ์ธ์ ‘ํ•œ ์ง‘๋“ค๊ณผ ๋ฐฉ๋ฒ”์žฅ์น˜๊ฐ€ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ์ธ์ ‘ํ•œ programmers.co.kr ๋ฌธ์ œ ์„ค๋ช… ๋„๋‘‘์ด ํ›”์น  ์ˆ˜ ์žˆ๋Š” ๋ˆ์˜ ์ตœ๋Œ“๊ฐ’์„ ์ €์žฅํ•˜๋Š” dp ํ…Œ์ด๋ธ”์„ ์ƒ์„ฑํ•ฉ๋‹ˆ๋‹ค. dp[i]๋Š” 1๋ฒˆ๋ถ€ํ„ฐ i๋ฒˆ์งธ ์ง‘๊นŒ์ง€ ํ„ธ์—ˆ์„ ๋•Œ ํ›”์น  ์ˆ˜ ์žˆ๋Š” ๋ˆ์˜ ์ตœ๋Œ“๊ฐ’์ž…๋‹ˆ๋‹ค. ๋งŒ์•ฝ ์ด์ „ ์ง‘์„ ํ„ธ์—ˆ๋‹ค๋ฉด ํ˜„์žฌ ์ง‘์€ ํ„ธ์ง€ ๋ชปํ•˜๋ฏ€๋กœ dp[i]๋Š” (๋ฐ”๋กœ ์ „ ์ง‘๊นŒ์ง€ ํ›”์น  ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ“๊ฐ’)์™€ (์ „์ „์ง‘๊นŒ์ง€์˜ ํ›”์น  ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ“๊ฐ’ + ํ˜„์žฌ ์ง‘์˜ money) ๋‘ ๊ฐ€์ง€ ๊ฒฝ์šฐ๋กœ ๋‚˜๋‰ฉ๋‹ˆ๋‹ค. dp[i]..

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค / Python] ๋“ฑ๊ตฃ๊ธธ

๋ฌธ์ œ ๋งํฌ: programmers.co.kr/learn/courses/30/lessons/42898 ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ๋“ฑ๊ตฃ๊ธธ ๊ณ„์†๋˜๋Š” ํญ์šฐ๋กœ ์ผ๋ถ€ ์ง€์—ญ์ด ๋ฌผ์— ์ž ๊ฒผ์Šต๋‹ˆ๋‹ค. ๋ฌผ์— ์ž ๊ธฐ์ง€ ์•Š์€ ์ง€์—ญ์„ ํ†ตํ•ด ํ•™๊ต๋ฅผ ๊ฐ€๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์ง‘์—์„œ ํ•™๊ต๊นŒ์ง€ ๊ฐ€๋Š” ๊ธธ์€ m x n ํฌ๊ธฐ์˜ ๊ฒฉ์ž๋ชจ์–‘์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์•„๋ž˜ ๊ทธ๋ฆผ์€ m = programmers.co.kr ๋ฌธ์ œ ์„ค๋ช… ํ•ด๋‹น ์ขŒํ‘œ์— ๋„๋‹ฌํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ €์žฅํ•˜๋Š” dp ํ…Œ์ด๋ธ”์„ ๋งŒ๋“ญ๋‹ˆ๋‹ค. ์ด๋™์€ ์˜ค๋ฅธ์ชฝ, ์•„๋ž˜๋กœ๋งŒ ๊ฐ€๋Šฅํ•˜๋ฏ€๋กœ (x, y)์— ๋„๋‹ฌํ•˜๋Š” ๋ฐฉ๋ฒ•์€ (x - 1, y)์—์„œ ์˜ค๊ฑฐ๋‚˜ (x, y - 1)์—์„œ ์˜ค๋Š” 2๊ฐ€์ง€์ž…๋‹ˆ๋‹ค. ๋ฌธ์ œ์—์„œ๋Š” mxn ํฌ๊ธฐ์˜ ๋ฐฐ์—ด์ด๋ผ๊ณ  ํ–ˆ์ง€๋งŒ ๋ฆฌ์ŠคํŠธ ์ธ๋ฑ์‹ฑ์˜ ํŽธ์˜์ƒ n์„ ํ–‰, m์„ ์—ด๋กœ ์ƒ๊ฐํ–ˆ์Šต๋‹ˆ๋‹ค. (n + 1) X (m + ..

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค / Python] ์ •์ˆ˜ ์‚ผ๊ฐํ˜•

๋ฌธ์ œ ๋งํฌ: programmers.co.kr/learn/courses/30/lessons/43105 ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ์ •์ˆ˜ ์‚ผ๊ฐํ˜• [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr ๋ฌธ์ œ ์„ค๋ช… ๊ฑฐ์ณ์˜จ ์ˆซ์ž๋“ค์˜ ํ•ฉ์˜ ์ตœ๋Œ“๊ฐ’์„ ์ €์žฅํ•˜๋Š” dp ํ…Œ์ด๋ธ”์„ ์ƒ์„ฑํ•ฉ๋‹ˆ๋‹ค. triangle[i][j]์— ๋„๋‹ฌํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ๋‘ ๊ฐ€์ง€ ๋ฐฉ๋ฒ•์ด ์žˆ์Šต๋‹ˆ๋‹ค. triangle[i - 1][j - 1]์—์„œ triangle[i][j]๋กœ ๊ฐ€๊ธฐ triangle[i - 1][j]์—์„œ triangle[i][j]๋กœ ๊ฐ€๊ธฐ dp[i][j]๋Š” ์œ„ ๋‘ ๊ฐ€์ง€ ๊ฐ’ ์ค‘์—์„œ ์ตœ๋Œ“๊ฐ’์„ ์ €์žฅํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด triangle ๋ฐฐ์—ด์ด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค๋ฉด 7 3 8 8 1 0 2 7 4 ..

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค / Python] N์œผ๋กœ ํ‘œํ˜„

๋ฌธ์ œ ๋งํฌ: programmers.co.kr/learn/courses/30/lessons/42895 ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - N์œผ๋กœ ํ‘œํ˜„ programmers.co.kr ๋ฌธ์ œ ์„ค๋ช… ์ฒ˜์Œ์—” number์— ๋Œ€ํ•œ dp ํ…Œ์ด๋ธ”์„ ์ƒ์„ฑํ•ด์„œ ๋ฌธ์ œ๋ฅผ ํ’€๋ คํ–ˆ๋Š”๋ฐ, ๊ทธ๊ฒŒ ์•„๋‹ˆ๋ผ N์˜ ์‚ฌ์šฉ ํšŸ์ˆ˜์— ๋Œ€ํ•œ dp ํ…Œ์ด๋ธ”์„ ์ด์šฉํ•ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•ด์•ผ ํ–ˆ๋‹ค. ๋ฌธ์ œ์—์„œ ์ตœ์†Ÿ๊ฐ’์ด 8๋ณด๋‹ค ํด ๊ฒฝ์šฐ -1์„ ๋ฐ˜ํ™˜ํ•œ๋‹ค๊ณ  ๋‚˜์™€์žˆ์œผ๋ฏ€๋กœ N์„ 8๋ฒˆ ์‚ฌ์šฉํ•˜๋Š” ๊ฒฝ์šฐ๊นŒ์ง€๋งŒ ๊ณ„์‚ฐํ•˜๋ฉด ๋œ๋‹ค. N์„ i๋ฒˆ ์‚ฌ์šฉํ•˜๋Š” ๊ฒฝ์šฐ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ์ˆ˜: - NNN...N (N์ด i๋ฒˆ ๋ฐ˜๋ณต๋˜๋Š” ๊ฒฝ์šฐ) - (N์„ 1๋ฒˆ ์‚ฌ์šฉํ•œ ์ˆ˜) ์‚ฌ์น™์—ฐ์‚ฐ (N์„ i - 1๋ฒˆ ์‚ฌ์šฉํ•œ ์ˆ˜) - (N์„ 2๋ฒˆ ์‚ฌ์šฉํ•œ ์ˆ˜) ์‚ฌ์น™์—ฐ์‚ฐ (N์„ i - 2๋ฒˆ ์‚ฌ์šฉํ•œ ์ˆ˜) ... - (N์„ i - 1๋ฒˆ ์‚ฌ์šฉํ•œ ์ˆ˜) ์‚ฌ..

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค / Python] ์ˆœ์œ„

๋ฌธ์ œ ๋งํฌ: programmers.co.kr/learn/courses/30/lessons/49191 ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ์ˆœ์œ„ 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr ๋ฌธ์ œ ์„ค๋ช… 4๋ฒˆ ์„ ์ˆ˜๊ฐ€ 2๋ฒˆ ์„ ์ˆ˜์—๊ฒŒ ์ด๊ธฐ๊ณ  2๋ฒˆ ์„ ์ˆ˜๊ฐ€ 5๋ฒˆ ์„ ์ˆ˜์—๊ฒŒ ์ด๊ธด๋‹ค๋ฉด, 4๋ฒˆ ์„ ์ˆ˜๋Š” ๊ฒฐ๊ตญ 5๋ฒˆ ์„ ์ˆ˜์—๊ฒŒ๋„ ์ด๊น๋‹ˆ๋‹ค. 4๋ฒˆ > 2๋ฒˆ, 2๋ฒˆ > 5๋ฒˆ → 4๋ฒˆ > 5๋ฒˆ ์ด๋Ÿฐ ์‹์œผ๋กœ ๋ชจ๋“  ์„ ์ˆ˜์˜ ๊ฒฝ๊ธฐ ๊ฒฐ๊ณผ๋ฅผ ์ข…ํ•ฉํ•ด์„œ ๊ฒฐ๊ณผ์˜ ๊ฐœ์ˆ˜๊ฐ€ (n - 1)๊ฐœ๋ผ๋ฉด ์ˆœ์œ„๋ฅผ ํ™•์ • ์ง€์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฒฝ๊ธฐ ๊ฒฐ๊ณผ๋ฅผ ์ €์žฅํ•  win, lose ๋”•์…”๋„ˆ๋ฆฌ ์ดˆ๊ธฐํ™” results์— ์žˆ๋Š” ๊ฒฝ๊ธฐ ๊ฒฐ๊ณผ๋ฅผ ์ž…๋ ฅ (์„ ์ˆ˜๊ฐ€ ๊ฒน์น˜์ง€ ์•Š๊ฒŒ set ์ž๋ฃŒํ˜• ์ด์šฉ) n๋ช…์˜ ์„ ์ˆ˜๋“ค์˜ ๊ฒฝ๊ธฐ ๊ฒฐ๊ณผ ํ•ฉ์น˜๊ธฐ 1) ๋งŒ์•ฝ A๊ฐ€ ..

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค / Python] ๊ฐ€์žฅ ๋จผ ๋…ธ๋“œ

๋ฌธ์ œ ๋งํฌ: programmers.co.kr/learn/courses/30/lessons/49189 ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ๊ฐ€์žฅ ๋จผ ๋…ธ๋“œ 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr ๋ฌธ์ œ ์„ค๋ช… 1๋ฒˆ ๋…ธ๋“œ๋กœ๋ถ€ํ„ฐ ๊ฐ€์žฅ ๋ฉ€๋ฆฌ ๋–จ์–ด์ง„ ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. 1๋ฒˆ ๋…ธ๋“œ๋ถ€ํ„ฐ BFS๋ฅผ ์ˆ˜ํ–‰ํ•˜๋ฉฐ 1๋ฒˆ ๋…ธ๋“œ์™€์˜ distance๋ฅผ ์ €์žฅํ•œ ๋’ค, distance๊ฐ€ ๊ฐ€์žฅ ํฐ ๊ฐ’์„ ๊ฐ–๋Š” ์›์†Œ์˜ ๊ฐœ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋„๋ก ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ–ˆ์Šต๋‹ˆ๋‹ค. ์ธ์ ‘ ๋…ธ๋“œ ์ •๋ณด๋ฅผ ์ €์žฅํ•  graph์™€ 1๋ฒˆ ๋…ธ๋“œ๋กœ๋ถ€ํ„ฐ์˜ ๊ฑฐ๋ฆฌ๋ฅผ ์ €์žฅํ•  distance ์ดˆ๊ธฐํ™” ์ฃผ์–ด์ง„ edge ์ •๋ณด๋ฅผ graph์— ์ €์žฅ 1๋ฒˆ ๋…ธ๋“œ์˜ distance๋ฅผ 0์œผ๋กœ ํ•˜๊ณ , 1๋ฒˆ ๋…ธ๋“œ๋ฅผ ํ์—..