Python 81

[Baekjoon] 5567_๊ฒฐํ˜ผ์‹

Silver II๋ฌธ์ œ(์ถœ์ฒ˜: https://www.acmicpc.net/problem/5567)๋ฌธ์ œ  ์ƒ๊ทผ์ด๋Š” ์ž์‹ ์˜ ๊ฒฐํ˜ผ์‹์— ํ•™๊ต ๋™๊ธฐ ์ค‘ ์ž์‹ ์˜ ์นœ๊ตฌ์™€ ์นœ๊ตฌ์˜ ์นœ๊ตฌ๋ฅผ ์ดˆ๋Œ€ํ•˜๊ธฐ๋กœ ํ–ˆ๋‹ค. ์ƒ๊ทผ์ด์˜ ๋™๊ธฐ๋Š” ๋ชจ๋‘ N๋ช…์ด๊ณ , ์ด ํ•™์ƒ๋“ค์˜ ํ•™๋ฒˆ์€ ๋ชจ๋‘ 1๋ถ€ํ„ฐ N๊นŒ์ง€์ด๋‹ค. ์ƒ๊ทผ์ด์˜ ํ•™๋ฒˆ์€ 1์ด๋‹ค.์ƒ๊ทผ์ด๋Š” ๋™๊ธฐ๋“ค์˜ ์นœ๊ตฌ ๊ด€๊ณ„๋ฅผ ๋ชจ๋‘ ์กฐ์‚ฌํ•œ ๋ฆฌ์ŠคํŠธ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ์ด ๋ฆฌ์ŠคํŠธ๋ฅผ ๋ฐ”ํƒ•์œผ๋กœ ๊ฒฐํ˜ผ์‹์— ์ดˆ๋Œ€ํ•  ์‚ฌ๋žŒ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.  ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ƒ๊ทผ์ด์˜ ๋™๊ธฐ์˜ ์ˆ˜ n (2 ≤ n ≤ 500)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ๋ฆฌ์ŠคํŠธ์˜ ๊ธธ์ด m (1 ≤ m ≤ 10000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ ์ค„๋ถ€ํ„ฐ m๊ฐœ ์ค„์—๋Š” ์นœ๊ตฌ ๊ด€๊ณ„ ai bi๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ ai  ์ถœ๋ ฅ  ์ฒซ์งธ ์ค„์— ์ƒ๊ทผ์ด์˜ ๊ฒฐํ˜ผ์‹์— ์ดˆ๋Œ€ํ•˜๋Š” ๋™๊ธฐ์˜ ..

[Algorithm] DFS/BFS

โ“DFS์™€ BFS - ์ฃผ์–ด์ง„ ๊ทธ๋ž˜ํ”„์—์„œ ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜  โ“DFS - Depth First Search (๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰)- ์ž„์˜์˜ ์ •์ ์—์„œ ์‹œ์ž‘ํ•˜์—ฌ ์ด์›ƒํ•˜๋Š” ํ•˜๋‚˜์˜ ์ •์ ์„ ๋ฐฉ๋ฌธํ•˜๊ณ , ๋ฐฉ๊ธˆ ๋ฐฉ๋ฌธํ•œ ์ •์ ์˜ ์ด์›ƒ ์ •์ ์„ ๋ฐฉ๋ฌธ def dfs(x): visited[x]=True for i in graph[x]: if not visited[i]: dfs(i)  โ“BFS - Breadth First Search (๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰)- ์ž„์˜์˜ ์ •์ ์—์„œ ์‹œ์ž‘ํ•˜์—ฌ ์ด์›ƒํ•˜๋Š” ๋ชจ๋“  ์ •์ ๋“ค์„ ๋ฐฉ๋ฌธํ•˜๊ณ , ๋ฐฉ๋ฌธํ•œ ์ •์ ๋“ค์˜ ์ด์›ƒ ์ •์ ๋“ค์„ ๋ฐฉ๋ฌธ def bfs(x): queue=[] visited[x]=True queue.append(x) while len(queue)!=0: ..

[Baekjoon] 1012_์œ ๊ธฐ๋† ๋ฐฐ์ถ”

Silver II๋ฌธ์ œ(์ถœ์ฒ˜: https://www.acmicpc.net/problem/1012)๋ฌธ์ œ  ์ฐจ์„ธ๋Œ€ ์˜๋†์ธ ํ•œ๋‚˜๋Š” ๊ฐ•์›๋„ ๊ณ ๋žญ์ง€์—์„œ ์œ ๊ธฐ๋† ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๊ธฐ๋กœ ํ•˜์˜€๋‹ค. ๋†์•ฝ์„ ์“ฐ์ง€ ์•Š๊ณ  ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๋ ค๋ฉด ๋ฐฐ์ถ”๋ฅผ ํ•ด์ถฉ์œผ๋กœ๋ถ€ํ„ฐ ๋ณดํ˜ธํ•˜๋Š” ๊ฒƒ์ด ์ค‘์š”ํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ํ•œ๋‚˜๋Š” ํ•ด์ถฉ ๋ฐฉ์ง€์— ํšจ๊ณผ์ ์ธ ๋ฐฐ์ถ” ํฐ ์ง€๋ ์ด๋ฅผ ๊ตฌ์ž…ํ•˜๊ธฐ๋กœ ๊ฒฐ์‹ฌํ•œ๋‹ค. ์ด ์ง€๋ ์ด๋Š” ๋ฐฐ์ถ” ๊ทผ์ฒ˜์— ์„œ์‹ํ•˜๋ฉฐ ํ•ด์ถฉ์„ ์žก์•„๋จน์Œ์œผ๋กœ์จ ๋ฐฐ์ถ”๋ฅผ ๋ณดํ˜ธํ•œ๋‹ค. ํŠนํžˆ, ์–ด๋–ค ๋ฐฐ์ถ”์— ๋ฐฐ์ถ” ํฐ ์ง€๋ ์ด๊ฐ€ ํ•œ ๋งˆ๋ฆฌ๋ผ๋„ ์‚ด๊ณ  ์žˆ์œผ๋ฉด ์ด ์ง€๋ ์ด๋Š” ์ธ์ ‘ํ•œ ๋‹ค๋ฅธ ๋ฐฐ์ถ”๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ์–ด, ๊ทธ ๋ฐฐ์ถ”๋“ค ์—ญ์‹œ ํ•ด์ถฉ์œผ๋กœ๋ถ€ํ„ฐ ๋ณดํ˜ธ๋ฐ›์„ ์ˆ˜ ์žˆ๋‹ค. ํ•œ ๋ฐฐ์ถ”์˜ ์ƒํ•˜์ขŒ์šฐ ๋„ค ๋ฐฉํ–ฅ์— ๋‹ค๋ฅธ ๋ฐฐ์ถ”๊ฐ€ ์œ„์น˜ํ•œ ๊ฒฝ์šฐ์— ์„œ๋กœ ์ธ์ ‘ํ•ด์žˆ๋Š” ๊ฒƒ์ด๋‹ค.ํ•œ๋‚˜๊ฐ€ ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๋Š” ๋•…์€ ๊ณ ๋ฅด์ง€ ๋ชปํ•ด์„œ ๋ฐฐ์ถ”๋ฅผ ๊ตฐ๋ฐ๊ตฐ๋ฐ ์‹ฌ์–ด ๋†“..

[Baekjoon] 2667_๋‹จ์ง€๋ฒˆํ˜ธ๋ถ™์ด๊ธฐ

Silver I๋ฌธ์ œ(์ถœ์ฒ˜: https://www.acmicpc.net/problem/2667)๋ฌธ์ œ  ๊ณผ ๊ฐ™์ด ์ •์‚ฌ๊ฐํ˜• ๋ชจ์–‘์˜ ์ง€๋„๊ฐ€ ์žˆ๋‹ค. 1์€ ์ง‘์ด ์žˆ๋Š” ๊ณณ์„, 0์€ ์ง‘์ด ์—†๋Š” ๊ณณ์„ ๋‚˜ํƒ€๋‚ธ๋‹ค. ์ฒ ์ˆ˜๋Š” ์ด ์ง€๋„๋ฅผ ๊ฐ€์ง€๊ณ  ์—ฐ๊ฒฐ๋œ ์ง‘์˜ ๋ชจ์ž„์ธ ๋‹จ์ง€๋ฅผ ์ •์˜ํ•˜๊ณ , ๋‹จ์ง€์— ๋ฒˆํ˜ธ๋ฅผ ๋ถ™์ด๋ ค ํ•œ๋‹ค. ์—ฌ๊ธฐ์„œ ์—ฐ๊ฒฐ๋˜์—ˆ๋‹ค๋Š” ๊ฒƒ์€ ์–ด๋–ค ์ง‘์ด ์ขŒ์šฐ, ํ˜น์€ ์•„๋ž˜์œ„๋กœ ๋‹ค๋ฅธ ์ง‘์ด ์žˆ๋Š” ๊ฒฝ์šฐ๋ฅผ ๋งํ•œ๋‹ค. ๋Œ€๊ฐ์„  ์ƒ์— ์ง‘์ด ์žˆ๋Š” ๊ฒฝ์šฐ๋Š” ์—ฐ๊ฒฐ๋œ ๊ฒƒ์ด ์•„๋‹ˆ๋‹ค. ๋Š” ์„ ๋‹จ์ง€๋ณ„๋กœ ๋ฒˆํ˜ธ๋ฅผ ๋ถ™์ธ ๊ฒƒ์ด๋‹ค. ์ง€๋„๋ฅผ ์ž…๋ ฅํ•˜์—ฌ ๋‹จ์ง€์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๊ณ , ๊ฐ ๋‹จ์ง€์— ์†ํ•˜๋Š” ์ง‘์˜ ์ˆ˜๋ฅผ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜์—ฌ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ ๋ฒˆ์งธ ์ค„์—๋Š” ์ง€๋„์˜ ํฌ๊ธฐ N(์ •์‚ฌ๊ฐํ˜•์ด๋ฏ€๋กœ ๊ฐ€๋กœ์™€ ์„ธ๋กœ์˜ ํฌ๊ธฐ๋Š” ๊ฐ™์œผ๋ฉฐ 5≤N≤25)์ด ์ž…๋ ฅ๋˜๊ณ , ๊ทธ๋‹ค์Œ N ์ค„์—๋Š” ๊ฐ๊ฐ..

[Baekjoon] 2606_๋ฐ”์ด๋Ÿฌ์Šค

Silver III๋ฌธ์ œ(์ถœ์ฒ˜: https://www.acmicpc.net/problem/2606)๋ฌธ์ œ  ์‹ ์ข… ๋ฐ”์ด๋Ÿฌ์Šค์ธ ์›œ ๋ฐ”์ด๋Ÿฌ์Šค๋Š” ๋„คํŠธ์›Œํฌ๋ฅผ ํ†ตํ•ด ์ „ํŒŒ๋œ๋‹ค. ํ•œ ์ปดํ“จํ„ฐ๊ฐ€ ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ฆฌ๋ฉด ๊ทธ ์ปดํ“จํ„ฐ์™€ ๋„คํŠธ์›Œํฌ ์ƒ์—์„œ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ๋ชจ๋“  ์ปดํ“จํ„ฐ๋Š” ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ฆฌ๊ฒŒ ๋œ๋‹ค.์˜ˆ๋ฅผ ๋“ค์–ด 7๋Œ€์˜ ์ปดํ“จํ„ฐ๊ฐ€ ๊ณผ ๊ฐ™์ด ๋„คํŠธ์›Œํฌ ์ƒ์—์„œ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋‹ค๊ณ  ํ•˜์ž. 1๋ฒˆ ์ปดํ“จํ„ฐ๊ฐ€ ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ฆฌ๋ฉด ์›œ ๋ฐ”์ด๋Ÿฌ์Šค๋Š” 2๋ฒˆ๊ณผ 5๋ฒˆ ์ปดํ“จํ„ฐ๋ฅผ ๊ฑฐ์ณ 3๋ฒˆ๊ณผ 6๋ฒˆ ์ปดํ“จํ„ฐ๊นŒ์ง€ ์ „ํŒŒ๋˜์–ด 2, 3, 5, 6 ๋„ค ๋Œ€์˜ ์ปดํ“จํ„ฐ๋Š” ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ฆฌ๊ฒŒ ๋œ๋‹ค. ํ•˜์ง€๋งŒ 4๋ฒˆ๊ณผ 7๋ฒˆ ์ปดํ“จํ„ฐ๋Š” 1๋ฒˆ ์ปดํ“จํ„ฐ์™€ ๋„คํŠธ์›Œํฌ์ƒ์—์„œ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์— ์˜ํ–ฅ์„ ๋ฐ›์ง€ ์•Š๋Š”๋‹ค.์–ด๋Š ๋‚  1๋ฒˆ ์ปดํ“จํ„ฐ๊ฐ€ ์›œ ๋ฐ”์ด๋Ÿฌ์Šค์— ๊ฑธ๋ ธ๋‹ค. ์ปดํ“จํ„ฐ์˜ ์ˆ˜์™€ ๋„คํŠธ์›Œํฌ ์ƒ์—์„œ ์„œ..

[Baekjoon] 1260_DFS์™€ BFS

Silver II๋ฌธ์ œ(์ถœ์ฒ˜: https://www.acmicpc.net/problem/1260)๋ฌธ์ œ  ๊ทธ๋ž˜ํ”„๋ฅผ DFS๋กœ ํƒ์ƒ‰ํ•œ ๊ฒฐ๊ณผ์™€ BFS๋กœ ํƒ์ƒ‰ํ•œ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๋‹จ, ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ๋Š” ์ •์ ์ด ์—ฌ๋Ÿฌ ๊ฐœ์ธ ๊ฒฝ์šฐ์—๋Š” ์ •์  ๋ฒˆํ˜ธ๊ฐ€ ์ž‘์€ ๊ฒƒ์„ ๋จผ์ € ๋ฐฉ๋ฌธํ•˜๊ณ , ๋” ์ด์ƒ ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ๋Š” ์ ์ด ์—†๋Š” ๊ฒฝ์šฐ ์ข…๋ฃŒํ•œ๋‹ค. ์ •์  ๋ฒˆํ˜ธ๋Š” 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ๊นŒ์ง€์ด๋‹ค.  ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 1,000), ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ M(1 ≤ M ≤ 10,000), ํƒ์ƒ‰์„ ์‹œ์ž‘ํ•  ์ •์ ์˜ ๋ฒˆํ˜ธ V๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ M๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ„์„ ์ด ์—ฐ๊ฒฐํ•˜๋Š” ๋‘ ์ •์ ์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์–ด๋–ค ๋‘ ์ •์  ์‚ฌ์ด์— ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๊ฐ„์„ ์ด ์žˆ์„ ์ˆ˜ ์žˆ๋‹ค. ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง€๋Š” ๊ฐ„์„ ์€ ์–‘๋ฐฉํ–ฅ์ด๋‹ค. ์ถœ๋ ฅ  ์ฒซ์งธ ์ค„์— DFS๋ฅผ ์ˆ˜ํ–‰ํ•œ ๊ฒฐ๊ณผ..

[Baekjoon] 5397_ํ‚ค๋กœ๊ฑฐ

Silver III๋ฌธ์ œ(์ถœ์ฒ˜: https://www.acmicpc.net/problem/5397)๋ฌธ์ œ  ์ฐฝ์˜์ด๋Š” ๊ฐ•์‚ฐ์ด์˜ ๋น„๋ฐ€๋ฒˆํ˜ธ๋ฅผ ํ›”์น˜๊ธฐ ์œ„ํ•ด์„œ ๊ฐ•์‚ฐ์ด๊ฐ€ ์‚ฌ์šฉํ•˜๋Š” ์ปดํ“จํ„ฐ์— ํ‚ค๋กœ๊ฑฐ๋ฅผ ์„ค์น˜ํ–ˆ๋‹ค. ๋ฉฐ์น ์„ ๊ธฐ๋‹ค๋ฆฐ ๋์— ์ฐฝ์˜์ด๋Š” ๊ฐ•์‚ฐ์ด๊ฐ€ ๋น„๋ฐ€๋ฒˆํ˜ธ ์ฐฝ์— ์ž…๋ ฅํ•˜๋Š” ๊ธ€์ž๋ฅผ ์–ป์–ด๋ƒˆ๋‹ค.ํ‚ค๋กœ๊ฑฐ๋Š” ์‚ฌ์šฉ์ž๊ฐ€ ํ‚ค๋ณด๋“œ๋ฅผ ๋ˆ„๋ฅธ ๋ช…๋ น์„ ๋ชจ๋‘ ๊ธฐ๋กํ•œ๋‹ค. ๋”ฐ๋ผ์„œ, ๊ฐ•์‚ฐ์ด๊ฐ€ ๋น„๋ฐ€๋ฒˆํ˜ธ๋ฅผ ์ž…๋ ฅํ•  ๋•Œ, ํ™”์‚ดํ‘œ๋‚˜ ๋ฐฑ์ŠคํŽ˜์ด์Šค๋ฅผ ์ž…๋ ฅํ•ด๋„ ์ •ํ™•ํ•œ ๋น„๋ฐ€๋ฒˆํ˜ธ๋ฅผ ์•Œ์•„๋‚ผ ์ˆ˜ ์žˆ๋‹ค. ๊ฐ•์‚ฐ์ด๊ฐ€ ๋น„๋ฐ€๋ฒˆํ˜ธ ์ฐฝ์—์„œ ์ž…๋ ฅํ•œ ํ‚ค๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๊ฐ•์‚ฐ์ด์˜ ๋น„๋ฐ€๋ฒˆํ˜ธ๋ฅผ ์•Œ์•„๋‚ด๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๊ฐ•์‚ฐ์ด๋Š” ํ‚ค๋ณด๋“œ๋กœ ์ž…๋ ฅํ•œ ํ‚ค๋Š” ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž, ์†Œ๋ฌธ์ž, ์ˆซ์ž, ๋ฐฑ์ŠคํŽ˜์ด์Šค, ํ™”์‚ดํ‘œ์ด๋‹ค.  ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋Š” ํ•œ ์ค„๋กœ ์ด๋ฃจ์–ด์ ธ..

[Baekjoon] 7795_๋จน์„ ๊ฒƒ์ธ๊ฐ€ ๋จนํž ๊ฒƒ์ธ๊ฐ€

Silver III๋ฌธ์ œ(์ถœ์ฒ˜: https://www.acmicpc.net/problem/7795)๋ฌธ์ œ  ์‹ฌํ•ด์—๋Š” ๋‘ ์ข…๋ฅ˜์˜ ์ƒ๋ช…์ฒด A์™€ B๊ฐ€ ์กด์žฌํ•œ๋‹ค. A๋Š” B๋ฅผ ๋จน๋Š”๋‹ค. A๋Š” ์ž๊ธฐ๋ณด๋‹ค ํฌ๊ธฐ๊ฐ€ ์ž‘์€ ๋จน์ด๋งŒ ๋จน์„ ์ˆ˜ ์žˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, A์˜ ํฌ๊ธฐ๊ฐ€ {8, 1, 7, 3, 1}์ด๊ณ , B์˜ ํฌ๊ธฐ๊ฐ€ {3, 6, 1}์ธ ๊ฒฝ์šฐ์— A๊ฐ€ B๋ฅผ ๋จน์„ ์ˆ˜ ์žˆ๋Š” ์Œ์˜ ๊ฐœ์ˆ˜๋Š” 7๊ฐ€์ง€๊ฐ€ ์žˆ๋‹ค. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.๋‘ ์ƒ๋ช…์ฒด A์™€ B์˜ ํฌ๊ธฐ๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, A์˜ ํฌ๊ธฐ๊ฐ€ B๋ณด๋‹ค ํฐ ์Œ์ด ๋ช‡ ๊ฐœ๋‚˜ ์žˆ๋Š”์ง€ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ฒซ์งธ ์ค„์—๋Š” A์˜ ์ˆ˜ N๊ณผ B์˜ ์ˆ˜ M์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” A์˜ ํฌ๊ธฐ๊ฐ€ ๋ชจ๋‘ ์ฃผ์–ด์ง€..

[Baekjoon] 14426_์ ‘๋‘์‚ฌ ์ฐพ๊ธฐ

Silver III๋ฌธ์ œ(์ถœ์ฒ˜: https://www.acmicpc.net/problem/14426)๋ฌธ์ œ  ๋ฌธ์ž์—ด S์˜ ์ ‘๋‘์‚ฌ๋ž€ S์˜ ๊ฐ€์žฅ ์•ž์—์„œ๋ถ€ํ„ฐ ๋ถ€๋ถ„ ๋ฌธ์ž์—ด์„ ์˜๋ฏธํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, S = "codeplus"์˜ ์ ‘๋‘์‚ฌ๋Š” "code", "co", "codepl", "codeplus"๊ฐ€ ์žˆ๊ณ , "plus", "s", "cude", "crud"๋Š” ์ ‘๋‘์‚ฌ๊ฐ€ ์•„๋‹ˆ๋‹ค. ์ด N๊ฐœ์˜ ๋ฌธ์ž์—ด๋กœ ์ด๋ฃจ์–ด์ง„ ์ง‘ํ•ฉ S๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง€๋Š” M๊ฐœ์˜ ๋ฌธ์ž์—ด ์ค‘์—์„œ ์ง‘ํ•ฉ S์— ํฌํ•จ๋˜์–ด ์žˆ๋Š” ๋ฌธ์ž์—ด ์ค‘ ์ ์–ด๋„ ํ•˜๋‚˜์˜ ์ ‘๋‘์‚ฌ์ธ ๊ฒƒ์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ๋ฌธ์ž์—ด์˜ ๊ฐœ์ˆ˜ N๊ณผ M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ N๊ฐœ์˜ ์ค„์—๋Š” ์ง‘ํ•ฉ S์— ํฌํ•จ๋˜์–ด ์žˆ๋Š” ..

[Baekjoon] 10211_Maximum Subarray

Silver III๋ฌธ์ œ(์ถœ์ฒ˜: https://www.acmicpc.net/problem/10211)๋ฌธ์ œ  ํฌ๊ธฐ N์ธ ์ •์ˆ˜ํ˜• ๋ฐฐ์—ด X๊ฐ€ ์žˆ์„ ๋•Œ, X์˜ ๋ถ€๋ถ„ ๋ฐฐ์—ด(X์˜ ์—ฐ์†ํ•œ ์ผ๋ถ€๋ถ„) ์ค‘ ๊ฐ ์›์†Œ์˜ ํ•ฉ์ด ๊ฐ€์žฅ ํฐ ๋ถ€๋ถ„ ๋ฐฐ์—ด์„ ์ฐพ๋Š” Maximum subarray problem(์ตœ๋Œ€ ๋ถ€๋ถ„ ๋ฐฐ์—ด ๋ฌธ์ œ)์€ ์ปดํ“จํ„ฐ ๊ณผํ•™์—์„œ ๋งค์šฐ ์ž˜ ์•Œ๋ ค์ ธ ์žˆ๋‹ค.์—ฌ๋Ÿฌ๋ถ„์€ N๊ณผ ๋ฐฐ์—ด X๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, X์˜ maximum subarray์˜ ํ•ฉ์„ ๊ตฌํ•˜์ž. ์ฆ‰, max1 ≤ i ≤  j ≤ N (X [i]+...+X [j])๋ฅผ ๊ตฌํ•˜์ž. ์ž…๋ ฅ ์ž…๋ ฅ ํŒŒ์ผ์˜ ์ฒซ ๋ฒˆ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ˆ˜๋ฅผ ์˜๋ฏธํ•˜๋Š” ์ž์—ฐ์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ทธ๋‹ค์Œ์—๋Š” T๊ฐœ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค ๋ณ„๋กœ ์ฒซ ๋ฒˆ์งธ ์ค„์— ๋ฐฐ์—ด์˜ ํฌ๊ธฐ N์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ ..