๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์—ด์ฝ”2

[Week03] ์•Œ๊ณ ๋ฆฌ์ฆ˜ - DFS / BFS ๋ฐฑ์ค€ ๋ฌธ์ œ ๋‘ ๋ฌธ์ œ๋ฅผ ๊ตฌ๋ถ„ํ•˜๋Š” ๊ธฐ์ค€์ด ์•ฝ๊ฐ„ ๋ชจํ˜ธํ•˜์ง€๋งŒ.. ๋ฌธ์ œ๋ฅผ ํ’€๋ฉด์„œ ๋งŒ๋‚ฌ๋˜ ๋ช‡๋ช‡ ์œ ํ˜•๋“ค์„ ๊นŒ๋จน์ง€์•Š๊ธฐ ์œ„ํ•ด ์ •๋ฆฌํ•ด๋‘”๋‹ค. DFS / ๋ฐฑํŠธ๋ž˜ํ‚น nums = [1,2,3] result = [] permute = [] def dfs(): if len(permute) == len(nums) : result.append(permute[:]) return for i in range(len(nums)) : if nums[i] not in permute : permute.append(nums[i]) dfs() permute.pop() dfs() print(result) DFS 25731๋ฒˆ : ๋น™์‚ฐ https://www.acmicpc.net/problem/2573 2573๋ฒˆ: ๋น™์‚ฐ ์ฒซ ์ค„์—๋Š” ์ด์ฐจ์› ๋ฐฐ์—ด์˜ ํ–‰์˜ ๊ฐœ์ˆ˜์™€ ์—ด์˜ ๊ฐœ์ˆ˜๋ฅผ.. 2022. 4. 21.
[SW์‚ฌ๊ด€ํ•™๊ต ์ •๊ธ€] ๋‚˜๋ฅผ ๋Œ์•„๋ณด๋Š” ์‹œ๊ฐ„ ์—์„ธ์ด ๊ณผ๊ฑฐ์— ๋Œ€ํ•œ ์„ฑ์ฐฐ ์ง€๋‚˜์˜จ ์‹œ๊ฐ„์„ ๋Œ์ด์ผœ๋ณด๋ฉด ๋‚˜๋Š” ๋„์ „ํ•˜๊ธฐ๋ณด๋‹จ ํ•ญ์ƒ ์•ˆ์ •์ ์ธ ์„ ํƒํ–ˆ์—ˆ๋‹ค. ๋‹น์‹œ์—๋Š” ๋‚ด๊ฐ€ ์•ˆ์ •์ ์ธ ์‚ถ์„ ์ถ”๊ตฌํ•˜๋Š” ์‚ฌ๋žŒ์ด๋ผ ์ƒ๊ฐํ–ˆ์—ˆ๋Š”๋ฐ ์ง€๊ธˆ ๋˜๋Œ์•„๋ณด๋ฉด ์‹คํŒจํ•˜๋Š”๊ฒŒ ๋‘๋ ค์›Œ์„œ ์•ˆ์ •์ ์ธ ๊ฒƒ์„ ์ข‹์•„ํ•œ๋‹ค๊ณ  ์Šค์Šค๋กœ ํ•ฉ๋ฆฌํ™”๋ฅผ ํ–ˆ๋˜๊ฒƒ๊ฐ™๋‹ค. ๊ฐœ๋ฐœ์ž๊ฐ€ ๋˜๊ณ ์‹ถ๋‹ค๋Š” ์ƒ๊ฐ์€ ๊ณ„์†ํ•˜์˜€์œผ๋‚˜ ์ฐ”๋Ÿฌ๋ณด๊ธฐ์‹์œผ๋กœ๋งŒ ํ•˜๊ณ  ์žฌ๋Œ€๋กœ ๋„์ „ํ•˜์ง€ ๋ชปํ•œ์ฑ„ ๋ช‡๋…„์ด ํ˜๋ €๋‹ค. ํšŒ์‚ฌ๋ฅผ ๊ด€๋‘๊ณ  ์ •๊ธ€์— ์ž…์†Œํ•œ๊ฒƒ์€ ๋‚˜์—๊ฒŒ ํฐ ๋„์ „์ด์˜€๋‹ค. ๋‚˜์—๊ฒŒ ์ฃผ์–ด์ง„ ์ด๋Ÿฌํ•œ ๊ธฐํšŒ๋ฅผ ์†Œ์ค‘ํžˆ ์—ฌ๊ธฐ๊ณ  ํ›„ํšŒํ•˜์ง€ ์•Š๋„๋ก ์ตœ์„ ์„ ๋‹คํ• ๊ฒƒ์ด๋‹ค. 5๊ฐœ์›” ๋™์•ˆ ์–ป์–ด๊ฐ€๊ณ  ์‹ถ์€ ๊ฒƒ ๐Ÿค” ์ •๊ธ€์„ ํ†ตํ•ด ๋งŽ์€ ๊ฒƒ๋“ค์„ ์–ป์–ด๊ฐˆ ์ˆ˜ ์žˆ๊ฒ ์ง€๋งŒ ๊ฐ€์žฅ ์ค‘์š”ํ•œ๊ฒƒ์€ ๊ฐœ๋ฐœ์ž๋กœ์„œ ์ข‹์€ ์Šต๊ด€์„ ๋“ค์ด๋Š”๊ฒƒ์ด๋ผ ์ƒ๊ฐํ•œ๋‹ค. ์ข‹์€ ํ™˜๊ฒฝ์—์„œ ๊ณต๋ถ€ํ•˜๋Š” ๋ฐฉ์‹, ๊ฐœ๋ฐœ์ž์  ์‚ฌ๊ณ  ๋“ฑ ์ข‹์€ ์Šต๊ด€์„ ๋“ค์—ฌ์„œ ์ •๊ธ€ ํ›„์—๋„ ์ง€์†์ ์œผ๋กœ ๋ฐœ์ „๊ฐ€๋Šฅํ•œ.. 2022. 4. 2.