728x90

Algorithms 21

๋ฐฑ์ค€ ์ด๋ถ„ํƒ์ƒ‰ ๋ฌธ์ œ๋“ค (1072 ๊ฒŒ์ž„, 1654 ๋žœ์„ ์ž๋ฅด๊ธฐ, 1920 ์ˆ˜์ฐพ๊ธฐ, 2512 ์˜ˆ์‚ฐ)

https://www.acmicpc.net/problem/1072 1072๋ฒˆ: ๊ฒŒ์ž„ ๊น€ํ˜•ํƒ์€ ์ง€๊ธˆ ๋ชฐ๋ž˜ Spider Solitaire(์ŠคํŒŒ์ด๋” ์นด๋“œ๋†€์ด)๋ฅผ ํ•˜๊ณ  ์žˆ๋‹ค. ํ˜•ํƒ์ด๋Š” ์ด ๊ฒŒ์ž„์„ ์ด๊ธธ ๋•Œ๋„ ์žˆ์—ˆ์ง€๋งŒ, ์งˆ ๋•Œ๋„ ์žˆ์—ˆ๋‹ค. ๋ˆ„๊ตฐ๊ฐ€์˜ ์‹œ์„ ์ด ๋Š๊ปด์ง„ ํ˜•ํƒ์ด๋Š” ๊ฒŒ์ž„์„ ์ค‘๋‹จํ•˜๊ณ  ์ฝ”๋”ฉ์„ ํ•˜๊ธฐ ์‹œ www.acmicpc.net import sys input = sys.stdin.readline x, y = map(int, input().split()) z = int(100 * y / x) if z >= 99: print(-1) else: ans = 0 start = 0 end = 1000000000 while(start

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

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..

์ˆ˜ ์ฐพ๊ธฐ (๋ฐฑ์ค€ 1920๋ฒˆ, ํ•ด์‹œ)

https://www.acmicpc.net/problem/1920 1920๋ฒˆ: ์ˆ˜ ์ฐพ๊ธฐ ์ฒซ์งธ ์ค„์— ์ž์—ฐ์ˆ˜ N(1 ≤ N ≤ 100,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ ์ค„์—๋Š” N๊ฐœ์˜ ์ •์ˆ˜ A[1], A[2], …, A[N]์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ ์ค„์—๋Š” M(1 ≤ M ≤ 100,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ ์ค„์—๋Š” M๊ฐœ์˜ ์ˆ˜๋“ค์ด ์ฃผ์–ด์ง€๋Š”๋ฐ, ์ด ์ˆ˜๋“ค www.acmicpc.net import sys input = sys.stdin.readline n = map(int, input()) a = list(map(int, input().split())) pool = {} for k in a: pool[k] = 1 print(pool) m = map(int, input()) b = list(map(int, input().split(..

1๋กœ๋งŒ๋“ค๊ธฐ (๋ฐฑ์ค€1463)

https://www.acmicpc.net/problem/1463 1463๋ฒˆ: 1๋กœ ๋งŒ๋“ค๊ธฐ ์ฒซ์งธ ์ค„์— 1๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 106๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ •์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. www.acmicpc.net Dnamic Programming(๋™์ ๊ณ„ํš๋ฒ•)์€ ๋ฉ”๋ชจ์ด์ œ์ด์…˜ ํ†ตํ•ด ์ค‘๋ณต๊ณ„์‚ฐ๊ฐ’์„ ์ €์žฅํ•ด ํšจ์œจ์„ ๋†’์—ฌ์ค€๋‹ค. 1) Python ์ด์šฉ # DP --> ๋ฉ”๋ชจ์ด์ œ์ด์…˜: ์ค‘๋ณต๊ณ„์‚ฐ๊ฐ’์„ ์ค„์—ฌ ํšจ์œจ ๋†’์—ฌ์คŒ n = int(input()) d = [0] * (n + 1) # d์— ๊ณ„์‚ฐ๊ฐ’ ์ €์žฅ # d[0] = 0, d[1] = 0 for i in range(2, n + 1): d[i] = d[i - 1] + 1 if i % 3 == 0: d[i] = min(d[i], d[i // 3] + 1) if i % 2 == 0: d[i] = ..

์ˆœ์—ด ์‚ฌ์ดํด (๋ฐฑ์ค€ 10451)

https://www.acmicpc.net/problem/10451 10451๋ฒˆ: ์ˆœ์—ด ์‚ฌ์ดํด 1๋ถ€ํ„ฐ N๊นŒ์ง€ ์ •์ˆ˜ N๊ฐœ๋กœ ์ด๋ฃจ์–ด์ง„ ์ˆœ์—ด์„ ๋‚˜ํƒ€๋‚ด๋Š” ๋ฐฉ๋ฒ•์€ ์—ฌ๋Ÿฌ ๊ฐ€์ง€๊ฐ€ ์žˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, 8๊ฐœ์˜ ์ˆ˜๋กœ ์ด๋ฃจ์–ด์ง„ ์ˆœ์—ด (3, 2, 7, 8, 1, 4, 5, 6)์„ ๋ฐฐ์—ด์„ ์ด์šฉํ•ด ํ‘œํ˜„ํ•˜๋ฉด \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net ์ฒ˜์Œ์— ๊ทธ๋ž˜ํ”„๋ฅผ ๋งŒ๋“ค์–ด์„œ ์žฌ๊ท€๋ฅผ ํ–ˆ๋Š”๋ฐ ์‹œ๊ฐ„ ์ œํ•œ์œผ๋กœ ์‹คํŒจ! ์‹คํŒจํ•œ ์ฝ”๋“œ import sys sys.setrecursionlimit(1000000) input = sys.stdin.readline t = int(input()) def dfs(v): visited[v] = 1 for i in range(n + 1): if vi..

์—ฐ๊ฒฐ์š”์†Œ์˜๊ฐœ์ˆ˜ (๋ฐฑ์ค€ 11724)

์—ฐ๊ฒฐ ์š”์†Œ์˜ ๊ฐœ์ˆ˜ ๋ฌธ์ œ ๋ฐฉํ–ฅ ์—†๋Š” ๊ทธ๋ž˜ํ”„๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์—ฐ๊ฒฐ ์š”์†Œ (Connected Component)์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ N๊ณผ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ M์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ M๊ฐœ์˜ ์ค„์— ๊ฐ„์„ ์˜ ์–‘ ๋์  u์™€ v๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ u, v ≤ N, u ≠ v) ๊ฐ™์€ ๊ฐ„์„ ์€ ํ•œ ๋ฒˆ๋งŒ ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ์—ฐ๊ฒฐ ์š”์†Œ์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ์˜ˆ์ œ ์ž…๋ ฅ 1 6 5 1 2 2 5 5 1 3 4 4 6 ์˜ˆ์ œ ์ถœ๋ ฅ 1 2 https://www.acmicpc.net/problem/11724 11724๋ฒˆ: ์—ฐ๊ฒฐ ์š”์†Œ์˜ ๊ฐœ์ˆ˜ ์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ N๊ณผ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ M์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 1,000,..

์ด๋ถ„ ๊ทธ๋ž˜ํ”„ (๋ฐฑ์ค€ 1707)

์ด๋ถ„๊ทธ๋ž˜ํ”„ ๋ชจ๋“  ๊ผญ์ง“์ ์„ ๋นจ๊ฐ•๊ณผ ํŒŒ๋ž‘์œผ๋กœ ์ƒ‰์น ํ•˜๋˜, ๋ชจ๋“  ๋ณ€์ด ๋นจ๊ฐ•๊ณผ ํŒŒ๋ž‘ ๊ผญ์ง“์ ์„ ํฌํ•จํ•˜๋„๋ก ์ƒ‰์น ํ•  ์ˆ˜ ์žˆ๋Š” ๊ทธ๋ž˜ํ”„ ์ด๋ถ„ ๊ทธ๋ž˜ํ”„์ธ์ง€ ํ™•์ธํ•˜๋Š” ๋ฐฉ๋ฒ• ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰(BFS), ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰(DFS)์„ ์ด์šฉ → ์„œ๋กœ ์ธ์ ‘ํ•œ ์ •์ ์ด ๊ฐ™์€ ์ƒ‰์ด๋ฉด ์ด๋ถ„ ๊ทธ๋ž˜ํ”„ X 1. BFS, DFS๋กœ ํƒ์ƒ‰ํ•˜๋ฉด์„œ ์ •์ ์„ ๋ฐฉ๋ฌธํ•  ๋•Œ๋งˆ๋‹ค ๋‘ ๊ฐ€์ง€ ์ƒ‰ ์ค‘ ํ•˜๋‚˜๋ฅผ ์น ํ•œ๋‹ค. 2. ๋‹ค์Œ ์ •์ ์„ ๋ฐฉ๋ฌธํ•˜๋ฉด์„œ ์ž์‹ ๊ณผ ์ธ์ ‘ํ•œ ์ •์ ์€ ์ž์‹ ๊ณผ ๋‹ค๋ฅธ ์ƒ‰์œผ๋กœ ์น ํ•œ๋‹ค. 3. ํƒ์ƒ‰์„ ์ง„ํ–‰ํ•  ๋•Œ ์ž์‹ ๊ณผ ์ธ์ ‘ํ•œ ์ •์ ์˜ ์ƒ‰์ด ์ž์‹ ๊ณผ ๋™์ผํ•˜๋ฉด ์ด๋ถ„ ๊ทธ๋ž˜ํ”„๊ฐ€ ์•„๋‹ˆ๋‹ค. 4. BFS์˜ ๊ฒฝ์šฐ ์ •์ ์„ ๋ฐฉ๋ฌธํ•˜๋‹ค๊ฐ€ ๋งŒ์•ฝ ๊ฐ™์€ ๋ ˆ๋ฒจ์—์„œ ์ •์ ์„ ๋‹ค๋ฅธ ์ƒ‰์œผ๋กœ ์น ํ•ด์•ผ ํ•œ๋‹ค๋ฉด ๋ฌด์กฐ๊ฑด ์ด๋ถ„ ๊ทธ๋ž˜ํ”„๊ฐ€ ์•„๋‹ˆ๋‹ค. ๋ชจ๋“  ์ •์ ์„ ๋‹ค ๋ฐฉ๋ฌธํ–ˆ๋Š”๋ฐ ์œ„์™€ ๊ฐ™์€ ๊ฒฝ์šฐ๊ฐ€ ์—†๋‹ค๋ฉด ์ด๋ถ„ ๊ทธ๋ž˜ํ”„์ด๋‹ค. โ€ป ์ด..

๋„คํŠธ์›Œํฌ 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๋Š” ๋ชจ๋‘ ๊ฐ™์€ ๋„คํŠธ์›Œํฌ ์ƒ์— ์žˆ๋‹ค๊ณ  ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค..

728x90