์ „์ฒด ๊ธ€

์ „์ฒด ๊ธ€

    [์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2020.12.30(์ˆ˜) - 2์ฃผ์ฐจ ๊ฐœ์ธ ๋ชฉํ‘œ

    ๋ชฉํ‘œ : prim ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ kruskal ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐœ๋… ๋ฐ ์‹ค์Šต ๋ฌธ์ œ๋ฅผ ๋ณต์Šตํ•˜๊ณ  ๋ฐฑ์ค€ ๋ฌธ์ œ๋ฅผ ํ†ตํ•ด ์‹ค์ œ ๋ฌธ์ œ์— ์ ์šฉํ•ด๋ณธ๋‹ค. ์‹ค์Šต์€ ์ด 3๋ฌธ์ œ๋กœ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆ˜์—… ์‹œ๊ฐ„์ด ์ง„ํ–‰๋˜์—ˆ๋˜ ์‹ค์Šต ๋ฌธ์ œ์ด๋‹ค. 1. prim ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌด๋ฐฉํ–ฅ ๊ฐ€์ค‘์น˜ ๊ทธ๋ž˜ํ”„๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ prim ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ด์šฉํ•˜์—ฌ MST๋ฅผ ๊ตฌํ•˜๊ณ  ๊ทธ ์—์ง€์˜ ํ•ฉ์„ ์ถœ๋ ฅ. (๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ ์—ฐ๊ฒฐ๋˜์ง€ ์•Š์•„, MST๊ฐ€ ์—†์„ ๊ฒฝ์šฐ 0์„ ์ถœ๋ ฅ) ์ž…๋ ฅ ๊ฐ’์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ฃผ์–ด์ง„๋‹ค. 7 12 # N, M A B C D E F G # ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜ N ๊ฐœ A B 7 # ๊ฐ„์„ ์˜ ์ •๋ณด M ๊ฐœ C B 8 A D 5 C E 5 D B 9 E B 7 D E 15 E G 9 F G 11 E F 8 F D 6 E D 15 2. kruskal ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌด๋ฐฉํ–ฅ ๊ฐ€์ค‘์น˜ ๊ทธ๋ž˜ํ”„๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ kr..

    [์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2020.12.23(์ˆ˜) - 1์ฃผ์ฐจ ๋ชจ์ž„ ๊ฒฐ๊ณผ

    [์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2020.12.23(์ˆ˜) - 1์ฃผ์ฐจ ๋ชจ์ž„ ๊ฒฐ๊ณผ ๊ณ ๋„ํ˜„ - BFS์™€ DFS๋ฅผ ๊ฐœ๋…๊ณผ ์‹ค์Šต ๋ฌธ์ œ๋ฅผ ๋ณต์Šตํ•˜๊ณ  ๋ฐฑ์ค€ ๋ฌธ์ œ๋ฅผ ํ†ตํ•ด ์‹ค์ œ ๋ฌธ์ œ์— ์ ์šฉํ•ด๋ด„์œผ๋กœ์จ ๋‘˜์˜ ์ฐจ์ด์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋™์ž‘๋ฐฉ์‹์— ๋Œ€ํ•ด ํ™•์‹คํ•˜๊ฒŒ ์•„๋Š” ๊ณ„๊ธฐ๊ฐ€ ๋˜์—ˆ๋‹ค. ์‹ ํฌ์Šน - ์ด์ง„ ํŠธ๋ฆฌ๋ฅผ ๊ตฌํ˜„ํ•˜๋ฉด์„œ ํŠธ๋ฆฌ์˜ ๊ตฌ์กฐ๋ฅผ ํŒŒ์•…ํ•˜์˜€๊ณ  ๊ทธ๋ž˜ํ”„๋ฅผ ๋งŒ๋“ค์–ด DFS, BFS์˜ ๋ฐฉ๋ฒ•์œผ๋กœ ํƒ์ƒ‰ํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์—ฐ์Šตํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค. ์ด๋™ํ—Œ - ๋‹ค์–‘ํ•œ ํ˜•ํƒœ๋กœ ๊ทธ๋ž˜ํ”„๋ฅผ ์ž‘์„ฑํ•ด๋ณด์•˜๊ณ  ์ด ๊ทธ๋ž˜ํ”„๋กค ํ†ตํ•ด DFS, BFS์˜ ๋ฐฉ๋ฒ•์œผ๋กœ ํƒ์ƒ‰ํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์—ฐ์Šตํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค. ์ตœํ˜„์„ - ์›น ํฌ๋กค๋ง ๊ธฐ๋ฒ•์„ ํ•™์Šตํ•˜์˜€๋”๋‹ˆ, ๋‹ค์–‘ํ•œ ์˜คํ”ˆ API์—์„œ ํฌ๋กค๋ง์„ ํ•ด๋ณด๊ณ  ์‹ถ๋‹จ ์ƒ๊ฐ์ด ๋“ค์—ˆ๋‹ค. ๊ณ ๋„ํ˜„ - codekodo.tistory.com/5 ์‹ ํฌ์Šน - ciwekdo.tistory.com/4 ์ด๋™ํ—Œ ..

    [์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2020.12.23(์ˆ˜) - 1์ฃผ์ฐจ ๊ฐœ์ธ ๊ฒฐ๊ณผ

    BFS์™€ DFS๋ฅผ ๊ฐœ๋…๊ณผ ์‹ค์Šต ๋ฌธ์ œ๋ฅผ ๋ณต์Šตํ•˜๊ณ  ๋ฐฑ์ค€ ๋ฌธ์ œ๋ฅผ ํ†ตํ•ด ์‹ค์ œ ๋ฌธ์ œ์— ์ ์šฉํ•ด๋ด„์œผ๋กœ์จ ๋‘˜์˜ ์ฐจ์ด์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋™์ž‘๋ฐฉ์‹์— ๋Œ€ํ•ด ํ™•์‹คํ•˜๊ฒŒ ์•„๋Š” ๊ณ„๊ธฐ๊ฐ€ ๋˜์—ˆ๋‹ค. 1. ์ด์›ƒ ๋…ธ๋“œ ์ฐพ๊ธฐ (๊ทธ๋ž˜ํ”„ ๊ธฐ๋ณธ) def main(): n, m = map(int, input().split()) node = list(input().split()) node_dict = dict() for i in range(n): node_dict[node[i]] = [] for i in range(m): srt, dst = input().split() if dst not in node_dict[srt]: node_dict[srt].append(dst) find_node = input() print(len(node_dict[find_node..

    [์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2020.12.23(์ˆ˜) - 1์ฃผ์ฐจ ๋ชจ์ž„ ๋ชฉํ‘œ

    [์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2020.12.23(์ˆ˜) - 1์ฃผ์ฐจ ๋ชจ์ž„ ๋ชฉํ‘œ ๊ณ ๋„ํ˜„ - DFS์™€ BFS๋ฅผ ๊ฐœ๋…๊ณผ ์‹ค์Šต ๋ฌธ์ œ๋ฅผ ๋ณต์Šตํ•˜๊ณ  ๋ฐฑ์ค€ ๋ฌธ์ œ๋ฅผ ํ†ตํ•ด ์‹ค์ œ ๋ฌธ์ œ์— ์ ์šฉํ•ด๋ณธ๋‹ค. ์‹ ํฌ์Šน - ํŠธ๋ฆฌ์™€ ๊ทธ๋ž˜ํ”„์˜ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์ดํ•ดํ•˜๊ณ  ์—ฐ์Šต ๋ฌธ์ œ๋ฅผ ํ†ตํ•ด ๊ฐœ๋…์„ ํ™•๋ฆฝ์‹œํ‚จ๋‹ค. ์ด๋™ํ—Œ - ๊นŠ์ด์šฐ์„ ํƒ์ƒ‰๊ณผ ๋„ˆ๋น„์šฐ์„ ํƒ์ƒ‰์„ ๋ณต์Šตํ•˜๊ณ  ์‹ค์Šต ๋ฌธ์ œ๋ฅผ ํ†ตํ•ด ์ฒดํ™”ํ•œ๋‹ค. ์ตœํ˜„์„ - ์—ฌ๋Ÿฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ณ„์‚ฐํ•˜์—ฌ ์ฒ˜๋ฆฌ์†๋„๊ฐ€ ์šฐ์ˆ˜ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์„ ๋ณ„ํ•œ๋‹ค. ์›น ํฌ๋กค๋ง์ด ๋ฌด์—‡์ธ์ง€ ์•Œ์•„๋ณธ๋‹ค. ๊ณ ๋„ํ˜„ - codekodo.tistory.com/4 ์‹ ํฌ์Šน - ciwekdo.tistory.com/3 ์ด๋™ํ—Œ - https://blog.naver.com/tortoise11/222183985820 ์ตœํ˜„์„ - coderhs.tistory.com/3 ๋น„๊ณต๊ฐœ์ฒ˜๋ฆฌ

    [์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2020.12.23(์ˆ˜) - 1์ฃผ์ฐจ ๊ฐœ์ธ ๋ชฉํ‘œ

    ๋ชฉํ‘œ : BFS์™€ DFS๋ฅผ ๊ฐœ๋…๊ณผ ์‹ค์Šต ๋ฌธ์ œ๋ฅผ ๋ณต์Šตํ•˜๊ณ  ๋ฐฑ์ค€ ๋ฌธ์ œ๋ฅผ ํ†ตํ•ด ์‹ค์ œ ๋ฌธ์ œ์— ์ ์šฉํ•ด๋ณธ๋‹ค. ์‹ค์Šต์€ ์ด 3๋ฌธ์ œ๋กœ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆ˜์—… ์‹œ๊ฐ„์ด ์ง„ํ–‰๋˜์—ˆ๋˜ ์‹ค์Šต ๋ฌธ์ œ์ด๋‹ค. 1. ์ด์›ƒ ๋…ธ๋“œ ์ฐพ๊ธฐ (๊ทธ๋ž˜ํ”„ ๊ธฐ๋ณธ) ์ž…๋ ฅ ๊ฐ’์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ฃผ์–ด์ง„๋‹ค. 4 4 # N M AA BB CC DD # ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜ N ๊ฐœ AA CC # ๊ฐ„์„  ์ •๋ณด M ๊ฐœ BB DD AA BB BB AA AA # ์งˆ์˜ ๋…ธ๋“œ 2. BFS (๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰) ์ž…๋ ฅ ๊ฐ’์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ฃผ์–ด์ง„๋‹ค. 12 11 # N M A B C D E F G H I J K L # ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜ N ๊ฐœ A B # ๊ฐ„์„  ์ •๋ณด M ๊ฐœ A C A D B E B F D G D H E I E J G K G L A # ์งˆ์˜ ๋…ธ๋“œ 3. DFS (๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰) - ์œ„ ๊ทธ๋ž˜ํ”„์™€ ๋™์ผ 4..

    [๋ธŒ๋ฃจํŠธ ํฌ์Šค / Python] BOJ 7568 - ๋ฉ์น˜

    www.acmicpc.net/problem/7568 7568๋ฒˆ: ๋ฉ์น˜ ์šฐ๋ฆฌ๋Š” ์‚ฌ๋žŒ์˜ ๋ฉ์น˜๋ฅผ ํ‚ค์™€ ๋ชธ๋ฌด๊ฒŒ, ์ด ๋‘ ๊ฐœ์˜ ๊ฐ’์œผ๋กœ ํ‘œํ˜„ํ•˜์—ฌ ๊ทธ ๋“ฑ์ˆ˜๋ฅผ ๋งค๊ฒจ๋ณด๋ ค๊ณ  ํ•œ๋‹ค. ์–ด๋–ค ์‚ฌ๋žŒ์˜ ๋ชธ๋ฌด๊ฒŒ๊ฐ€ x kg์ด๊ณ  ํ‚ค๊ฐ€ y cm๋ผ๋ฉด ์ด ์‚ฌ๋žŒ์˜ ๋ฉ์น˜๋Š” (x,y)๋กœ ํ‘œ์‹œ๋œ๋‹ค. ๋‘ ์‚ฌ๋žŒ A ์™€ B์˜ ๋ฉ www.acmicpc.net ์ž…๋ ฅ ์ฒซ ์ค„์—๋Š” ์ „์ฒด ์‚ฌ๋žŒ์˜ ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์ด์–ด์ง€๋Š” N๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ ์‚ฌ๋žŒ์˜ ๋ชธ๋ฌด๊ฒŒ์™€ ํ‚ค๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์–‘์˜ ์ •์ˆ˜ x์™€ y๊ฐ€ ํ•˜๋‚˜์˜ ๊ณต๋ฐฑ์„ ๋‘๊ณ  ๊ฐ๊ฐ ๋‚˜ํƒ€๋‚œ๋‹ค. ์ถœ๋ ฅ ์—ฌ๋Ÿฌ๋ถ„์€ ์ž…๋ ฅ์— ๋‚˜์—ด๋œ ์‚ฌ๋žŒ์˜ ๋ฉ์น˜ ๋“ฑ์ˆ˜๋ฅผ ๊ตฌํ•ด์„œ ๊ทธ ์ˆœ์„œ๋Œ€๋กœ ์ฒซ ์ค„์— ์ถœ๋ ฅํ•ด์•ผ ํ•œ๋‹ค. ๋‹จ, ๊ฐ ๋ฉ์น˜ ๋“ฑ์ˆ˜๋Š” ๊ณต๋ฐฑ๋ฌธ์ž๋กœ ๋ถ„๋ฆฌ๋˜์–ด์•ผ ํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• ๋ฆฌ์ŠคํŠธ์— x, y ๋ฅผ ์ €์žฅํ•˜๊ณ  ๋ฐ˜๋ณต๋ฌธ์„ ํƒ์ƒ‰ํ•œ๋‹ค. ํ•ด๊ฒฐ ๊ณผ์ • ์ด ๋ฌธ์ œ๋ฅผ ๋‘ ๋ฒˆ์—..

    2020๋…„ ๊ฒจ์šธ๋ฐฉํ•™ ๋ชจ๊ฐ์ฝ” ๊ณ„ํš

    - ๋ชฉํ‘œ - 2020-2ํ•™๊ธฐ ์ˆ˜๊ฐ•๊ณผ๋ชฉ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๋ณต์Šต ๋ฐ ๋ฐฑ์ค€ ๋ฌธ์ œ ํ’€์ด - ์„ค๋ช… - ์ด 6์ฃผ์— ๊ฑธ์นœ ๊ธฐ๊ฐ„ ๋™์•ˆ 2020๋…„ 2ํ•™๊ธฐ์— ์ˆ˜๊ฐ•ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜(์ด์˜์„ ๊ต์ˆ˜๋‹˜)์„ ๋ณต์Šตํ•œ๋‹ค. ๋งค์ฃผ ์‹ค์Šต ์‹œ๊ฐ„์— ์ง„ํ–‰๋˜์—ˆ๋˜ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ๋ฌธ์ œ(3 ~ 4๋ฌธ์ œ)๋ฅผ ๋ณต์Šตํ•˜๊ณ  ์ดํ›„ ๋ฐฑ์ค€์—์„œ ๊ด€๋ จ๋œ ๋ฌธ์ œ(1 ~ 2๋ฌธ์ œ)๋ฅผ ํ’€์–ด๋ณธ๋‹ค. - ๊นƒํ—ˆ๋ธŒ - github.com/k906506/2020_Winter_Assemble-And-selfcode k906506/2020_Winter_Assemble-And-selfcode Contribute to k906506/2020_Winter_Assemble-And-selfcode development by creating an account o..