728x90

Algorithms/Programmers 12

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์ž…๊ตญ์‹ฌ์‚ฌ (์ด๋ถ„ํƒ์ƒ‰)

https://programmers.co.kr/learn/courses/30/lessons/43238 ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ์ž…๊ตญ์‹ฌ์‚ฌ n๋ช…์ด ์ž…๊ตญ์‹ฌ์‚ฌ๋ฅผ ์œ„ํ•ด ์ค„์„ ์„œ์„œ ๊ธฐ๋‹ค๋ฆฌ๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฐ ์ž…๊ตญ์‹ฌ์‚ฌ๋Œ€์— ์žˆ๋Š” ์‹ฌ์‚ฌ๊ด€๋งˆ๋‹ค ์‹ฌ์‚ฌํ•˜๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์€ ๋‹ค๋ฆ…๋‹ˆ๋‹ค. ์ฒ˜์Œ์— ๋ชจ๋“  ์‹ฌ์‚ฌ๋Œ€๋Š” ๋น„์–ด์žˆ์Šต๋‹ˆ๋‹ค. ํ•œ ์‹ฌ์‚ฌ๋Œ€์—์„œ๋Š” ๋™์‹œ์— ํ•œ programmers.co.kr def solution(n, times): answer = 0 left = 1 right = max(times) * n # ๊ฐ€์žฅ ๋น„ํšจ์œจ์ ์ธ ์‹ฌ์‚ฌ ์‹œ๊ฐ„ while left = n: break if count >= n: right = mid - 1 elif count < n: left = mid + 1 return left print(solution(6, [7, 10..

๋„คํŠธ์›Œํฌ DFS/BFS

https://programmers.co.kr/learn/courses/30/lessons/43162 ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ๋„คํŠธ์›Œํฌ ๋„คํŠธ์›Œํฌ๋ž€ ์ปดํ“จํ„ฐ ์ƒํ˜ธ ๊ฐ„์— ์ •๋ณด๋ฅผ ๊ตํ™˜ํ•  ์ˆ˜ ์žˆ๋„๋ก ์—ฐ๊ฒฐ๋œ ํ˜•ํƒœ๋ฅผ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์ปดํ“จํ„ฐ A์™€ ์ปดํ“จํ„ฐ B๊ฐ€ ์ง์ ‘์ ์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด์žˆ๊ณ , ์ปดํ“จํ„ฐ B์™€ ์ปดํ“จํ„ฐ C๊ฐ€ ์ง์ ‘์ ์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ programmers.co.kr ๋ฌธ์ œ ์„ค๋ช… ๋„คํŠธ์›Œํฌ๋ž€ ์ปดํ“จํ„ฐ ์ƒํ˜ธ ๊ฐ„์— ์ •๋ณด๋ฅผ ๊ตํ™˜ํ•  ์ˆ˜ ์žˆ๋„๋ก ์—ฐ๊ฒฐ๋œ ํ˜•ํƒœ๋ฅผ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์ปดํ“จํ„ฐ A์™€ ์ปดํ“จํ„ฐ B๊ฐ€ ์ง์ ‘์ ์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด์žˆ๊ณ , ์ปดํ“จํ„ฐ B์™€ ์ปดํ“จํ„ฐ C๊ฐ€ ์ง์ ‘์ ์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์„ ๋•Œ ์ปดํ“จํ„ฐ A์™€ ์ปดํ“จํ„ฐ C๋„ ๊ฐ„์ ‘์ ์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์ •๋ณด๋ฅผ ๊ตํ™˜ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ ์ปดํ“จํ„ฐ A, B, C๋Š” ๋ชจ๋‘ ๊ฐ™์€ ๋„คํŠธ์›Œํฌ ์ƒ์— ์žˆ๋‹ค๊ณ  ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค..

ํƒ€๊ฒŸ ๋„˜๋ฒ„ (DFS/BFS lv2)

https://programmers.co.kr/learn/courses/30/lessons/43165 ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ํƒ€๊ฒŸ ๋„˜๋ฒ„ n๊ฐœ์˜ ์Œ์ด ์•„๋‹Œ ์ •์ˆ˜๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ์ˆ˜๋ฅผ ์ ์ ˆํžˆ ๋”ํ•˜๊ฑฐ๋‚˜ ๋นผ์„œ ํƒ€๊ฒŸ ๋„˜๋ฒ„๋ฅผ ๋งŒ๋“ค๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด [1, 1, 1, 1, 1]๋กœ ์ˆซ์ž 3์„ ๋งŒ๋“ค๋ ค๋ฉด ๋‹ค์Œ ๋‹ค์„ฏ ๋ฐฉ๋ฒ•์„ ์“ธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr ๋ฌธ์ œ ์„ค๋ช… n๊ฐœ์˜ ์Œ์ด ์•„๋‹Œ ์ •์ˆ˜๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ์ˆ˜๋ฅผ ์ ์ ˆํžˆ ๋”ํ•˜๊ฑฐ๋‚˜ ๋นผ์„œ ํƒ€๊ฒŸ ๋„˜๋ฒ„๋ฅผ ๋งŒ๋“ค๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด [1, 1, 1, 1, 1]๋กœ ์ˆซ์ž 3์„ ๋งŒ๋“ค๋ ค๋ฉด ๋‹ค์Œ ๋‹ค์„ฏ ๋ฐฉ๋ฒ•์„ ์“ธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3..

์Šคํƒ/ํ lv2. ๊ธฐ๋Šฅ ๊ฐœ๋ฐœ

https://programmers.co.kr/learn/courses/30/lessons/42586 ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ๊ธฐ๋Šฅ๊ฐœ๋ฐœ ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ํŒ€์—์„œ๋Š” ๊ธฐ๋Šฅ ๊ฐœ์„  ์ž‘์—…์„ ์ˆ˜ํ–‰ ์ค‘์ž…๋‹ˆ๋‹ค. ๊ฐ ๊ธฐ๋Šฅ์€ ์ง„๋„๊ฐ€ 100%์ผ ๋•Œ ์„œ๋น„์Šค์— ๋ฐ˜์˜ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋˜, ๊ฐ ๊ธฐ๋Šฅ์˜ ๊ฐœ๋ฐœ์†๋„๋Š” ๋ชจ๋‘ ๋‹ค๋ฅด๊ธฐ ๋•Œ๋ฌธ์— ๋’ค์— ์žˆ๋Š” ๊ธฐ๋Šฅ์ด ์•ž์— ์žˆ๋Š” programmers.co.kr ๋ฌธ์ œ ์„ค๋ช… ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ํŒ€์—์„œ๋Š” ๊ธฐ๋Šฅ ๊ฐœ์„  ์ž‘์—…์„ ์ˆ˜ํ–‰ ์ค‘์ž…๋‹ˆ๋‹ค. ๊ฐ ๊ธฐ๋Šฅ์€ ์ง„๋„๊ฐ€ 100%์ผ ๋•Œ ์„œ๋น„์Šค์— ๋ฐ˜์˜ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋˜, ๊ฐ ๊ธฐ๋Šฅ์˜ ๊ฐœ๋ฐœ์†๋„๋Š” ๋ชจ๋‘ ๋‹ค๋ฅด๊ธฐ ๋•Œ๋ฌธ์— ๋’ค์— ์žˆ๋Š” ๊ธฐ๋Šฅ์ด ์•ž์— ์žˆ๋Š” ๊ธฐ๋Šฅ๋ณด๋‹ค ๋จผ์ € ๊ฐœ๋ฐœ๋  ์ˆ˜ ์žˆ๊ณ , ์ด๋•Œ ๋’ค์— ์žˆ๋Š” ๊ธฐ๋Šฅ์€ ์•ž์— ์žˆ๋Š” ๊ธฐ๋Šฅ์ด ๋ฐฐํฌ๋  ๋•Œ ํ•จ๊ป˜ ๋ฐฐํฌ๋ฉ๋‹ˆ๋‹ค. ๋จผ์ € ๋ฐฐํฌ๋˜์–ด์•ผ ํ•˜๋Š” ์ˆœ์„œ๋Œ€๋กœ ์ž‘์—…์˜ ์ง„๋„๊ฐ€ ์ ํžŒ ..

์Šคํƒ/ํ 1๋ฒˆ lv2

๋‹ค๋ฆฌ๋ฅผ ์ง€๋‚˜๋Š” ํŠธ๋Ÿญ ๋ฌธ์ œ ์„ค๋ช… ํŠธ๋Ÿญ ์—ฌ๋Ÿฌ ๋Œ€๊ฐ€ ๊ฐ•์„ ๊ฐ€๋กœ์ง€๋ฅด๋Š” ์ผ ์ฐจ์„  ๋‹ค๋ฆฌ๋ฅผ ์ •ํ•ด์ง„ ์ˆœ์œผ๋กœ ๊ฑด๋„ˆ๋ ค ํ•ฉ๋‹ˆ๋‹ค. ๋ชจ๋“  ํŠธ๋Ÿญ์ด ๋‹ค๋ฆฌ๋ฅผ ๊ฑด๋„ˆ๋ ค๋ฉด ์ตœ์†Œ ๋ช‡ ์ดˆ๊ฐ€ ๊ฑธ๋ฆฌ๋Š”์ง€ ์•Œ์•„๋‚ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ํŠธ๋Ÿญ์€ 1์ดˆ์— 1๋งŒํผ ์›€์ง์ด๋ฉฐ, ๋‹ค๋ฆฌ ๊ธธ์ด๋Š” bridge_length์ด๊ณ  ๋‹ค๋ฆฌ๋Š” ๋ฌด๊ฒŒ weight๊นŒ์ง€ ๊ฒฌ๋”ฅ๋‹ˆ๋‹ค. โ€ป ํŠธ๋Ÿญ์ด ๋‹ค๋ฆฌ์— ์™„์ „ํžˆ ์˜ค๋ฅด์ง€ ์•Š์€ ๊ฒฝ์šฐ, ์ด ํŠธ๋Ÿญ์˜ ๋ฌด๊ฒŒ๋Š” ๊ณ ๋ คํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ๊ธธ์ด๊ฐ€ 2์ด๊ณ  10kg ๋ฌด๊ฒŒ๋ฅผ ๊ฒฌ๋””๋Š” ๋‹ค๋ฆฌ๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ๋ฌด๊ฒŒ๊ฐ€ [7, 4, 5, 6]kg์ธ ํŠธ๋Ÿญ์ด ์ˆœ์„œ๋Œ€๋กœ ์ตœ๋‹จ ์‹œ๊ฐ„ ์•ˆ์— ๋‹ค๋ฆฌ๋ฅผ ๊ฑด๋„ˆ๋ ค๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ฑด๋„ˆ์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๊ฒฝ๊ณผ ์‹œ๊ฐ„ / ๋‹ค๋ฆฌ๋ฅผ ์ง€๋‚œ ํŠธ๋Ÿญ / ๋‹ค๋ฆฌ๋ฅผ ๊ฑด๋„ˆ๋Š” ํŠธ๋Ÿญ / ๋Œ€๊ธฐ ํŠธ๋Ÿญ 0 [] [] [7,4,5,6] 1~2 [] [7] [4,5,6] 3 [7] [4] [5..

lv1. ์‹ ๊ทœ ์•„์ด๋”” ์ถ”์ฒœ - ์ •๊ทœํ‘œํ˜„์‹

์‹ ๊ทœ ์•„์ด๋”” ์ถ”์ฒœ ๋ฌธ์ œ ์„ค๋ช… ์นด์นด์˜ค์— ์ž…์‚ฌํ•œ ์‹ ์ž… ๊ฐœ๋ฐœ์ž ๋„ค์˜ค๋Š” "์นด์นด์˜ค๊ณ„์ •๊ฐœ๋ฐœํŒ€"์— ๋ฐฐ์น˜๋˜์–ด, ์นด์นด์˜ค ์„œ๋น„์Šค์— ๊ฐ€์ž…ํ•˜๋Š” ์œ ์ €๋“ค์˜ ์•„์ด๋””๋ฅผ ์ƒ์„ฑํ•˜๋Š” ์—…๋ฌด๋ฅผ ๋‹ด๋‹นํ•˜๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค. "๋„ค์˜ค"์—๊ฒŒ ์ฃผ์–ด์ง„ ์ฒซ ์—…๋ฌด๋Š” ์ƒˆ๋กœ ๊ฐ€์ž…ํ•˜๋Š” ์œ ์ €๋“ค์ด ์นด์นด์˜ค ์•„์ด๋”” ๊ทœ์น™์— ๋งž์ง€ ์•Š๋Š” ์•„์ด๋””๋ฅผ ์ž…๋ ฅํ–ˆ์„ ๋•Œ, ์ž…๋ ฅ๋œ ์•„์ด๋””์™€ ์œ ์‚ฌํ•˜๋ฉด์„œ ๊ทœ์น™์— ๋งž๋Š” ์•„์ด๋””๋ฅผ ์ถ”์ฒœํ•ด์ฃผ๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ๊ฐœ๋ฐœํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. ๋‹ค์Œ์€ ์นด์นด์˜ค ์•„์ด๋””์˜ ๊ทœ์น™์ž…๋‹ˆ๋‹ค. ์•„์ด๋””์˜ ๊ธธ์ด๋Š” 3์ž ์ด์ƒ 15์ž ์ดํ•˜์—ฌ์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์•„์ด๋””๋Š” ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž, ์ˆซ์ž, ๋นผ๊ธฐ(-), ๋ฐ‘์ค„(_), ๋งˆ์นจํ‘œ(.) ๋ฌธ์ž๋งŒ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋‹จ, ๋งˆ์นจํ‘œ(.)๋Š” ์ฒ˜์Œ๊ณผ ๋์— ์‚ฌ์šฉํ•  ์ˆ˜ ์—†์œผ๋ฉฐ ๋˜ํ•œ ์—ฐ์†์œผ๋กœ ์‚ฌ์šฉํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. "๋„ค์˜ค"๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด 7๋‹จ๊ณ„์˜ ์ˆœ์ฐจ์ ์ธ ์ฒ˜๋ฆฌ ๊ณผ์ •์„ ํ†ตํ•ด ์‹ ๊ทœ ..

ํ•ด์‹œ lv3. ๋ฒ ์ŠคํŠธ์•จ๋ฒ”

์ถœ์ฒ˜: ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ ์—ฐ์Šต, https://programmers.co.kr/learn/challenges ๋ฌธ์ œ ์„ค๋ช… ์ŠคํŠธ๋ฆฌ๋ฐ ์‚ฌ์ดํŠธ์—์„œ ์žฅ๋ฅด ๋ณ„๋กœ ๊ฐ€์žฅ ๋งŽ์ด ์žฌ์ƒ๋œ ๋…ธ๋ž˜๋ฅผ ๋‘ ๊ฐœ์”ฉ ๋ชจ์•„ ๋ฒ ์ŠคํŠธ ์•จ๋ฒ”์„ ์ถœ์‹œํ•˜๋ ค ํ•ฉ๋‹ˆ๋‹ค. ๋…ธ๋ž˜๋Š” ๊ณ ์œ  ๋ฒˆํ˜ธ๋กœ ๊ตฌ๋ถ„ํ•˜๋ฉฐ, ๋…ธ๋ž˜๋ฅผ ์ˆ˜๋กํ•˜๋Š” ๊ธฐ์ค€์€ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค. ์†ํ•œ ๋…ธ๋ž˜๊ฐ€ ๋งŽ์ด ์žฌ์ƒ๋œ ์žฅ๋ฅด๋ฅผ ๋จผ์ € ์ˆ˜๋กํ•ฉ๋‹ˆ๋‹ค. ์žฅ๋ฅด ๋‚ด์—์„œ ๋งŽ์ด ์žฌ์ƒ๋œ ๋…ธ๋ž˜๋ฅผ ๋จผ์ € ์ˆ˜๋กํ•ฉ๋‹ˆ๋‹ค. ์žฅ๋ฅด ๋‚ด์—์„œ ์žฌ์ƒ ํšŸ์ˆ˜๊ฐ€ ๊ฐ™์€ ๋…ธ๋ž˜ ์ค‘์—์„œ๋Š” ๊ณ ์œ  ๋ฒˆํ˜ธ๊ฐ€ ๋‚ฎ์€ ๋…ธ๋ž˜๋ฅผ ๋จผ์ € ์ˆ˜๋กํ•ฉ๋‹ˆ๋‹ค. ๋…ธ๋ž˜์˜ ์žฅ๋ฅด๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ๋ฌธ์ž์—ด ๋ฐฐ์—ด genres์™€ ๋…ธ๋ž˜๋ณ„ ์žฌ์ƒ ํšŸ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์ •์ˆ˜ ๋ฐฐ์—ด plays๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ, ๋ฒ ์ŠคํŠธ ์•จ๋ฒ”์— ๋“ค์–ด๊ฐˆ ๋…ธ๋ž˜์˜ ๊ณ ์œ  ๋ฒˆํ˜ธ๋ฅผ ์ˆœ์„œ๋Œ€๋กœ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•˜์„ธ์š”. ์ œํ•œ..

ํ•ด์‹œ - lv2 ์œ„์žฅ

์ถœ์ฒ˜: ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ ์—ฐ์Šต, https://programmers.co.kr/learn/challenges ๋ฌธ์ œ ์„ค๋ช… ์ŠคํŒŒ์ด๋“ค์€ ๋งค์ผ ๋‹ค๋ฅธ ์˜ท์„ ์กฐํ•ฉํ•˜์—ฌ ์ž…์–ด ์ž์‹ ์„ ์œ„์žฅํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ์ŠคํŒŒ์ด๊ฐ€ ๊ฐ€์ง„ ์˜ท์ด ์•„๋ž˜์™€ ๊ฐ™๊ณ  ์˜ค๋Š˜ ์ŠคํŒŒ์ด๊ฐ€ ๋™๊ทธ๋ž€ ์•ˆ๊ฒฝ, ๊ธด ์ฝ”ํŠธ, ํŒŒ๋ž€์ƒ‰ ํ‹ฐ์…”์ธ ๋ฅผ ์ž…์—ˆ๋‹ค๋ฉด ๋‹ค์Œ๋‚ ์€ ์ฒญ๋ฐ”์ง€๋ฅผ ์ถ”๊ฐ€๋กœ ์ž…๊ฑฐ๋‚˜ ๋™๊ทธ๋ž€ ์•ˆ๊ฒฝ ๋Œ€์‹  ๊ฒ€์ • ์„ ๊ธ€๋ผ์Šค๋ฅผ ์ฐฉ์šฉํ•˜๊ฑฐ๋‚˜ ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ข…๋ฅ˜, ์ด๋ฆ„ ์–ผ๊ตด ๋™๊ทธ๋ž€ ์•ˆ๊ฒฝ, ๊ฒ€์ • ์„ ๊ธ€๋ผ์Šค ์ƒ์˜ ํŒŒ๋ž€์ƒ‰ ํ‹ฐ์…”์ธ  ํ•˜์˜ ์ฒญ๋ฐ”์ง€ ๊ฒ‰์˜ท ๊ธด ์ฝ”ํŠธ ์ŠคํŒŒ์ด๊ฐ€ ๊ฐ€์ง„ ์˜์ƒ๋“ค์ด ๋‹ด๊ธด 2์ฐจ์› ๋ฐฐ์—ด clothes๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ ์„œ๋กœ ๋‹ค๋ฅธ ์˜ท์˜ ์กฐํ•ฉ์˜ ์ˆ˜๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”. ์ œํ•œ์‚ฌํ•ญ clothes์˜ ๊ฐ ํ–‰์€ [์˜์ƒ์˜ ์ด๋ฆ„, ์˜์ƒ์˜ ์ข…๋ฅ˜]๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต..

728x90