๋ฐ˜์‘ํ˜•

๐Ÿ”‘ CS 11

[๋ฐฑ์ค€ 16235๋ฒˆ] ๋‚˜๋ฌด ์ œํ…Œํฌ (์•…์˜ ์›ํ‰ defaultdict)

๊ฑฐ์˜ ๋ชจ๋“  ๋ฌธ์ œ์— defaultdict๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ๋‚˜ ์ด์œ ๋Š” ์ผ๋‹จ ๋„ˆ๋ฌด ํŽธํ•˜๋‹ค ๊ทธ๋ฆฌ๊ณ  ์ฒ˜์Œ์— ๋ชจ๋“  case์— ๋Œ€ํ•ด ๋‹ค ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ํ• ๋‹นํ•˜๋Š” ๊ฒƒ๋ณด๋‹ค ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์•„๋ผ๋Š” ๋Š๋‚Œ์„ ๋ฐ›์„ ์ˆ˜ ์žˆ๋‹ค. ๊ทผ๋ฐ ์ด์ „์— ์˜ฌ๋ฆฐ ๋ฐฑ์ค€ 14425๋ฒˆ์— ์ด์–ด์„œ ์ด๋ฒˆ์—๋„ ๊ณ„์† ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ•œ ์›์ธ์ด defaultdict์˜€๋‹ค.. ๐ŸŒผ ๋ฌธ์ œ ๋งํฌ https://www.acmicpc.net/problem/16235 16235๋ฒˆ: ๋‚˜๋ฌด ์žฌํ…Œํฌ ๋ถ€๋™์‚ฐ ํˆฌ์ž๋กœ ์–ต๋Œ€์˜ ๋ˆ์„ ๋ฒˆ ์ƒ๋„๋Š” ์ตœ๊ทผ N×N ํฌ๊ธฐ์˜ ๋•…์„ ๊ตฌ๋งคํ–ˆ๋‹ค. ์ƒ๋„๋Š” ์†์‰ฌ์šด ๋•… ๊ด€๋ฆฌ๋ฅผ ์œ„ํ•ด ๋•…์„ 1×1 ํฌ๊ธฐ์˜ ์นธ์œผ๋กœ ๋‚˜๋ˆ„์–ด ๋†“์•˜๋‹ค. ๊ฐ๊ฐ์˜ ์นธ์€ (r, c)๋กœ ๋‚˜ํƒ€๋‚ด๋ฉฐ, r์€ ๊ฐ€์žฅ ์œ„์—์„œ๋ถ€ํ„ฐ www.acmicpc.net ํ‹ฐ์–ด: ๊ณจ๋“œ III ๋ถ„๋ฅ˜: ๊ตฌํ˜„, ์ž๋ฃŒ๊ตฌ์กฐ, ์‹œ๋ฎฌ๋ ˆ์ด์…˜ ๋ฌธ์ œ ์ž์ฒด๋Š” ๊ทธ๋ƒฅ ..

[๋ฐฑ์ค€ 14425๋ฒˆ] ๋ฌธ์ž์—ด ์ง‘ํ•ฉ (python/ํŒŒ์ด์ฌ) - Trie ๊ตฌํ˜„ํ•˜๊ธฐ/defaultdict ์“ฐ๋ฉด ์•ˆ๋˜๋Š” ์ด์œ 

Trie๋ฅผ ์—ฐ์Šตํ•ด๋ณผ ์ˆ˜ ์žˆ๋Š” ๋Œ€ํ‘œ์ ์ธ ๋ฌธ์ œ์ด๋‹ค. ์‚ฌ์‹ค python์œผ๋กœ ํ‘ธ๋Š” ๊ฒฝ์šฐ Trie๋ฅผ ์ด์šฉํ•˜๋Š” ๊ฒƒ๋ณด๋‹ค set์„ ์ด์šฉํ•˜๋Š”๊ฒŒ ๋” ๋น ๋ฅด๋‹ค (์ด์œ ๋Š” set์€ HashTable๋กœ ๊ตฌํ˜„๋˜์–ด ์žˆ์–ด, ์›์†Œ ํƒ์ƒ‰์— ์„ ํ˜•์‹œ๊ฐ„์ด ๊ฑธ๋ฆฌ๊ธฐ ๋•Œ๋ฌธ์ด๋ผ๊ณ  ํ•จ). ์‹ฌ์ง€์–ด python์œผ๋กœ ํ•˜๋ฉด ํ†ต๊ณผ๋ฅผ ๋ชปํ•˜๊ณ , Pypy3์œผ๋กœ ์ œ์ถœํ•ด์•ผ ํ•œ๋‹ค. ๋‚˜๋Š” trie ์—ฐ์Šต์„ ์œ„ํ•ด trie๋กœ ํ’€์–ด ๋ณด์•˜๋‹ค. Node์˜ children์„ dictionary๋กœ ๊ตฌํ˜„ํ•˜๋Š” ๊ฒƒ๋ณด๋‹ค๋Š” defaultdict๋กœ ๊ตฌํ˜„ํ•˜๋Š” ๊ฒŒ search์—์„œ ๋” ์œ ๋ฆฌํ•  ๊ฒƒ ๊ฐ™๋‹ค๊ณ  ์ƒ๊ฐํ–ˆ๋Š”๋ฐ,์˜คํžˆ๋ ค ์‹œ๊ฐ„์ด ๋” ๊ฑธ๋ ค์„œ ๊ทธ ์ด์œ ๋ฅผ ์•Œ์•„๋ณด์•˜๋‹ค. ๐ŸŒผ ๋ฌธ์ œ ๋งํฌ https://www.acmicpc.net/problem/14425 14425๋ฒˆ: ๋ฌธ์ž์—ด ์ง‘ํ•ฉ ์ฒซ์งธ ์ค„์— ๋ฌธ์ž์—ด์˜ ๊ฐœ์ˆ˜ N๊ณผ M (..

[๋ฐฑ์ค€ 9084๋ฒˆ] ๋™์ „ (python/ํŒŒ์ด์ฌ) + ์‹ค๋ฒ„ II ๋‹ฌ์„ฑ

๊ทธ๋ฆฌ๋””๋กœ ๋ชปํ‘ธ๋Š” ๋ฌธ์ œ์ด๊ธธ๋ž˜ DP์ธ์ค„ ์•Œ๊ณ  ์งฐ๋‹ค๊ฐ€ DP๋„ ์•„๋‹ˆ๊ตฌ๋‚˜ ์‹ถ์–ด์„œ DFS ๋น„์Šทํ•˜๊ฒŒ ํ’€์—ˆ๋‹ค๊ฐ€ ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋– ์„œ DFS + DP๋กœ ์„ฑ๊ณต ๐ŸŒผ ๋ฌธ์ œ ๋งํฌ https://www.acmicpc.net/problem/9084 9084๋ฒˆ: ๋™์ „ ์šฐ๋ฆฌ๋‚˜๋ผ ํ™”ํ๋‹จ์œ„, ํŠนํžˆ ๋™์ „์—๋Š” 1์›, 5์›, 10์›, 50์›, 100์›, 500์›์ด ์žˆ๋‹ค. ์ด ๋™์ „๋“ค๋กœ๋Š” ์ •์ˆ˜์˜ ๊ธˆ์•ก์„ ๋งŒ๋“ค ์ˆ˜ ์žˆ์œผ๋ฉฐ ๊ทธ ๋ฐฉ๋ฒ•๋„ ์—ฌ๋Ÿฌ ๊ฐ€์ง€๊ฐ€ ์žˆ์„ ์ˆ˜ ์žˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, 30์›์„ ๋งŒ๋“ค๊ธฐ ์œ„ํ•ด์„œ๋Š” www.acmicpc.net ํ‹ฐ์–ด: ๊ณจ๋“œ V ๋ถ„๋ฅ˜: ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ โ— TRIAL 1. ๋”๋ณด๊ธฐ ์ฝ”๋“œ def solution(N, coins, target): c = coins.pop() #largest if N == 1: if target % c == 0: ..

[๋ฐฑ์ค€ 2579๋ฒˆ] ๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ (python/ํŒŒ์ด์ฌ)

DFS๋กœ ํ’€์—ˆ๋‹ค๊ฐ€ ์‹คํŒจํ•˜๊ณ  DP๋กœ ์„ฑ๊ณต ์‹ค๋ฒ„ 3 ์ ˆ๋Œ€์•„๋‹˜ ๐ŸŒผ ๋ฌธ์ œ ๋งํฌ https://www.acmicpc.net/problem/2579 2579๋ฒˆ: ๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ ๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ ๊ฒŒ์ž„์€ ๊ณ„๋‹จ ์•„๋ž˜ ์‹œ์ž‘์ ๋ถ€ํ„ฐ ๊ณ„๋‹จ ๊ผญ๋Œ€๊ธฐ์— ์œ„์น˜ํ•œ ๋„์ฐฉ์ ๊นŒ์ง€ ๊ฐ€๋Š” ๊ฒŒ์ž„์ด๋‹ค. ๊ณผ ๊ฐ™์ด ๊ฐ๊ฐ์˜ ๊ณ„๋‹จ์—๋Š” ์ผ์ •ํ•œ ์ ์ˆ˜๊ฐ€ ์“ฐ์—ฌ ์žˆ๋Š”๋ฐ ๊ณ„๋‹จ์„ ๋ฐŸ์œผ๋ฉด ๊ทธ ๊ณ„๋‹จ์— ์“ฐ์—ฌ ์žˆ๋Š” ์  www.acmicpc.net ํ‹ฐ์–ด: ์‹ค๋ฒ„ III ๋ถ„๋ฅ˜: ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ โ— TRIAL 1. ๋”๋ณด๊ธฐ ์ฝ”๋“œ import sys input = sys.stdin.readline def dfs(stairs, val, ctr): if not stairs: return val next_val = stairs.pop() if ctr != 2: dfs1 = dfs(stairs,..

[๋ฐฑ์ค€ 14500๋ฒˆ] ํ…ŒํŠธ๋กœ๋ฏธ๋…ธ (python/ํŒŒ์ด์ฌ)

๋ถ„๋…ธ์˜ ํ…ŒํŠธ๋ฆฌ์Šค.. ๋จธ๋ฆฌ๊ฐ€ ๋‚˜์˜๋ฉด ๋ชธ์ด ๊ณ ์ƒํ•œ๋‹ค ๐ŸŒผ ๋ฌธ์ œ ๋งํฌ https://www.acmicpc.net/problem/14500 14500๋ฒˆ: ํ…ŒํŠธ๋กœ๋ฏธ๋…ธ ํด๋ฆฌ์˜ค๋ฏธ๋…ธ๋ž€ ํฌ๊ธฐ๊ฐ€ 1×1์ธ ์ •์‚ฌ๊ฐํ˜•์„ ์—ฌ๋Ÿฌ ๊ฐœ ์ด์–ด์„œ ๋ถ™์ธ ๋„ํ˜•์ด๋ฉฐ, ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์กฐ๊ฑด์„ ๋งŒ์กฑํ•ด์•ผ ํ•œ๋‹ค. ์ •์‚ฌ๊ฐํ˜•์€ ์„œ๋กœ ๊ฒน์น˜๋ฉด ์•ˆ ๋œ๋‹ค. ๋„ํ˜•์€ ๋ชจ๋‘ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์–ด์•ผ ํ•œ๋‹ค. ์ •์‚ฌ๊ฐํ˜•์˜ ๋ณ€ www.acmicpc.net ํ‹ฐ์–ด: ๊ณจ๋“œ IV ๋ถ„๋ฅ˜: ๊ตฌํ˜„, ๋ธŒ๋ฃจํŠธํฌ์Šค ์•Œ๊ณ ๋ฆฌ์ฆ˜ โ— TRIAL 1. ๋”๋ณด๊ธฐ ์ฝ”๋“œ import sys input = sys.stdin.readline from collections import deque N, M = list(map(int, input().split())) paper = [] totalmax = 0 for _ in r..

[๋ฐฑ์ค€ 7569๋ฒˆ] ํ† ๋งˆํ†  (python/ํŒŒ์ด์ฌ)

๋ถ„๋…ธ์˜ ํ† ๋งˆํ† ...๐Ÿ… ์ ‘๊ทผ๋ฐฉ๋ฒ•์ด ํ‹€๋ ค์„œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋ช‡๋ฒˆ์”ฉ ์ˆ˜์ •ํ–ˆ๋‹ค ๐ŸŒผ ๋ฌธ์ œ ๋งํฌ https://www.acmicpc.net/problem/7569 7569๋ฒˆ: ํ† ๋งˆํ†  ์ฒซ ์ค„์—๋Š” ์ƒ์ž์˜ ํฌ๊ธฐ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ๋‘ ์ •์ˆ˜ M,N๊ณผ ์Œ“์•„์˜ฌ๋ ค์ง€๋Š” ์ƒ์ž์˜ ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” H๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. M์€ ์ƒ์ž์˜ ๊ฐ€๋กœ ์นธ์˜ ์ˆ˜, N์€ ์ƒ์ž์˜ ์„ธ๋กœ ์นธ์˜ ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค. ๋‹จ, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net ํ‹ฐ์–ด: ๊ณจ๋“œ V ๋ถ„๋ฅ˜: ๊ทธ๋ž˜ํ”„ ์ด๋ก , ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰, ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ โ— TRIAL 1. ๋”๋ณด๊ธฐ ์ฝ”๋“œ import sys input = sys.stdin.readline from collections import deque M, N, H = map(int, input().split()) #fill..

์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ •๋ฆฌ + Python ๊ตฌํ˜„ (Bubble sort, Selection sort, Insertion sort, Merge sort, Quick sort)

$O(n^2)$ ์‹คํ–‰์‹œ๊ฐ„์„ ๊ฐ–๋Š” ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ธ ๊ฐ€์ง€์™€ $O(n\log n)$ ์‹คํ–‰์‹œ๊ฐ„์„ ๊ฐ–๋Š” ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋‘ ๊ฐ€์ง€, ๊ทธ๋ฆฌ๊ณ  ๊ฐ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํŒŒ์ด์ฌ ์ฝ”๋“œ๋ฅผ ์ •๋ฆฌํ–ˆ๋‹ค. ๋ชฉ์ฐจ $O(n^2)$ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ Bubble sort Selection sort Insertion sort $O(n\log n)$ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ Merge sort Quick sort ๋‹ค์Œ ์‚ฌ์ดํŠธ์—์„œ ๊ฐ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹œ๊ฐํ™”๋ฅผ ํ•œ๋ˆˆ์— ํ™•์ธํ•  ์ˆ˜ ์žˆ๋‹ค. Comparison Sorting Visualization www.cs.usfca.edu $O(n^2)$ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋‹ค์Œ์˜ ์„ธ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ swap ํ•จ์ˆ˜๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค. def swap(arr, i, j): temp = arr[i] arr[i] = arr[j] arr[j] = ..

[๋ฐฑ์ค€ 16926๋ฒˆ] ๋ฐฐ์—ด ๋Œ๋ฆฌ๊ธฐ 1 (python/ํŒŒ์ด์ฌ)

๋ฌธ์ œ ์„ค๋ช…์„ ๊ทธ๋Œ€๋กœ ๊ตฌํ˜„ํ–ˆ๋”๋‹ˆ ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋– ์„œ, ์ข€๋” ํšจ์œจ์ ์ธ ๋ฐฉ๋ฒ•์„ ๊ณ ์•ˆํ•ด์•ผ ํ–ˆ์Œ. ๐ŸŒผ ๋ฌธ์ œ ๋งํฌ https://www.acmicpc.net/problem/16926 16926๋ฒˆ: ๋ฐฐ์—ด ๋Œ๋ฆฌ๊ธฐ 1 ํฌ๊ธฐ๊ฐ€ N×M์ธ ๋ฐฐ์—ด์ด ์žˆ์„ ๋•Œ, ๋ฐฐ์—ด์„ ๋Œ๋ ค๋ณด๋ ค๊ณ  ํ•œ๋‹ค. ๋ฐฐ์—ด์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๋ฐ˜์‹œ๊ณ„ ๋ฐฉํ–ฅ์œผ๋กœ ๋Œ๋ ค์•ผ ํ•œ๋‹ค. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net ํ‹ฐ์–ด: ์‹ค๋ฒ„ I ๋ถ„๋ฅ˜: ๊ตฌํ˜„ โ— TRIAL 1. ๋”๋ณด๊ธฐ ์ฝ”๋“œ def move(v1, v2, direction, arr, ans): if direction == 'l': x = v1[0] for y in r..

[๋ฐฑ์ค€ 2504๋ฒˆ] ๊ด„ํ˜ธ์˜ ๊ฐ’ (python/ํŒŒ์ด์ฌ)

์กฐ๊ฑด์„ ์—„์ฒญ ์ถ”๊ฐ€ํ•ด์„œ ํ‘ผ ๊ตฌํ˜„ ๋ฌธ์ œ. ์ฝ”๋“œ๊ฐ€ ๋„ˆ๋ฌด ๋”๋Ÿฌ์šด๋ฐ ๋” ์ข‹์€ ํ’€์ด ๋ฐฉ๋ฒ•์ด ์žˆ์„ ๋“ฏ ๐ŸŒผ ๋ฌธ์ œ ๋งํฌ https://www.acmicpc.net/problem/2504 2504๋ฒˆ: ๊ด„ํ˜ธ์˜ ๊ฐ’ 4๊ฐœ์˜ ๊ธฐํ˜ธ ‘(’, ‘)’, ‘[’, ‘]’๋ฅผ ์ด์šฉํ•ด์„œ ๋งŒ๋“ค์–ด์ง€๋Š” ๊ด„ํ˜ธ์—ด ์ค‘์—์„œ ์˜ฌ๋ฐ”๋ฅธ ๊ด„ํ˜ธ์—ด์ด๋ž€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ •์˜๋œ๋‹ค. ํ•œ ์Œ์˜ ๊ด„ํ˜ธ๋กœ๋งŒ ์ด๋ฃจ์–ด์ง„ ‘()’์™€ ‘[]’๋Š” ์˜ฌ๋ฐ”๋ฅธ ๊ด„ํ˜ธ์—ด์ด๋‹ค. ๋งŒ์ผ www.acmicpc.net ํ‹ฐ์–ด: ์‹ค๋ฒ„ I ๋ถ„๋ฅ˜: ๊ตฌํ˜„, ์ž๋ฃŒ๊ตฌ์กฐ, ์Šคํƒ, ์žฌ๊ท€ โ— TRIAL 1. ๋”๋ณด๊ธฐ ์ฝ”๋“œ inputs = list(input()) couple = {'(': ')', '[': ']'} value = {'(': 2, '[': 3} while len(inputs) != 1: ctr = 0 new_in..

[๋ฐฑ์ค€ 1697๋ฒˆ] ์ˆจ๋ฐ”๊ผญ์งˆ (python/ํŒŒ์ด์ฌ)

๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰ ๋ฌธ์ œ์ธ๋ฐ ์ˆ˜ํ•™์ ์œผ๋กœ ๋จธ๋ฆฌ๋ฅผ ์ž˜ ๊ตด๋ ค์„œ ์ตœ๋Œ€ํ•œ ํšจ์œจ์ ์œผ๋กœ ํƒ์ƒ‰ํ•ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ์˜€๋‹ค. ๊ณ„์† ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋– ์„œ ์ด๊ฒƒ์ €๊ฒƒ ๊ทœ์น™์„ ์ถ”๊ฐ€ํ•˜๋‹ค๊ฐ€ ๋ฌธ์ œ๋ฅผ ๋ฐœ๊ฒฌํ•˜๊ณ  ์„ฑ๊ณตํ–ˆ๋‹ค. ๐ŸŒผ ๋ฌธ์ œ ๋งํฌ https://www.acmicpc.net/problem/1697 1697๋ฒˆ: ์ˆจ๋ฐ”๊ผญ์งˆ ์ˆ˜๋นˆ์ด๋Š” ๋™์ƒ๊ณผ ์ˆจ๋ฐ”๊ผญ์งˆ์„ ํ•˜๊ณ  ์žˆ๋‹ค. ์ˆ˜๋นˆ์ด๋Š” ํ˜„์žฌ ์  N(0 ≤ N ≤ 100,000)์— ์žˆ๊ณ , ๋™์ƒ์€ ์  K(0 ≤ K ≤ 100,000)์— ์žˆ๋‹ค. ์ˆ˜๋นˆ์ด๋Š” ๊ฑท๊ฑฐ๋‚˜ ์ˆœ๊ฐ„์ด๋™์„ ํ•  ์ˆ˜ ์žˆ๋‹ค. ๋งŒ์•ฝ, ์ˆ˜๋นˆ์ด์˜ ์œ„์น˜๊ฐ€ X์ผ www.acmicpc.net ํ‹ฐ์–ด: ์‹ค๋ฒ„ I ๋ถ„๋ฅ˜: ๊ทธ๋ž˜ํ”„ ์ด๋ก , ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰, ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ โ— TRIAL 1. ๋”๋ณด๊ธฐ ์ฝ”๋“œ from collections import deque walk_left = lambda x..

๋ฐ˜์‘ํ˜•