์ ์ฒด ๊ธ
-
[Python] 11053 ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ดAlgorithm/๋ฐฑ์ค 2023. 1. 20. 17:20
1. ๋ฌธ์ ๐ https://www.acmicpc.net/problem/11053 11053๋ฒ: ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด ์์ด A๊ฐ ์ฃผ์ด์ก์ ๋, ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์๋ฅผ ๋ค์ด, ์์ด A = {10, 20, 10, 30, 20, 50} ์ธ ๊ฒฝ์ฐ์ ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ A = {10, 20, 10, 30, 20, 50} ์ด www.acmicpc.net 2. ์ ์ถ๋ ฅ ์ ๐ 3. ์๊ณ ๋ฆฌ์ฆ โ N์ด 1000์ด๊ธฐ ๋๋ฌธ์ ์ํ์ผ๋ก ํ๋ฉด ์๊ฐ์ด๊ณผ๊ฐ ๋ ๊ฒ์ด๋ค ์๋ถ๋ถ ์์ด์ ๋ฐ๋ผ ๋ท๋ถ๋ถ ์์ด๊น์ง ์ํฅ์ ์ฃผ๊ธฐ ๋๋ฌธ์ DP๋ก ํ์ด์ผ ํ๋ค! dp ๋ฅผ 1๋ก ์ด๊ธฐํํด์ค ๋ค์, ํ์ฌ index๋ก ์ด์ ์ ์ซ์์ ์ฐจ๊ทผ์ฐจ๊ทผ ๋น๊ตํด์ ์ฆ๊ฐํ๋ ์๋ผ๋ฉด ๊ทธ ์ด์ ์ ์ ์ฅ๋ dp ๊ฐ + 1..
-
[Python] 15657 N๊ณผ M (8)Algorithm/๋ฐฑ์ค 2023. 1. 20. 16:21
1. ๋ฌธ์ ๐ https://www.acmicpc.net/problem/15657 15657๋ฒ: N๊ณผ M (8) N๊ฐ์ ์์ฐ์์ ์์ฐ์ M์ด ์ฃผ์ด์ก์ ๋, ์๋ ์กฐ๊ฑด์ ๋ง์กฑํ๋ ๊ธธ์ด๊ฐ M์ธ ์์ด์ ๋ชจ๋ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. N๊ฐ์ ์์ฐ์๋ ๋ชจ๋ ๋ค๋ฅธ ์์ด๋ค. N๊ฐ์ ์์ฐ์ ์ค์์ M๊ฐ๋ฅผ ๊ณ ๋ฅธ ์์ด www.acmicpc.net 2. ์ ์ถ๋ ฅ ์ ๐ 3. ์๊ณ ๋ฆฌ์ฆ โ ๋ฌธ์ ์กฐ๊ฑด ์ค ๋น๋ด๋ฆผ์ฐจ์์ด ์์๊ธฐ๋๋ฌธ์ ๊ณ ๋ฅธ ์์ด์ ๋น๋ด๋ฆผ์ฐจ์์ด์ด์ผ ํ๋ค. ๊ธธ์ด๊ฐ K์ธ ์์ด A๊ฐ A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK๋ฅผ ๋ง์กฑํ๋ฉด, ๋น๋ด๋ฆผ์ฐจ์์ด๋ผ๊ณ ํ๋ค. 1. ์ ๋ ฌ์ ํด์ฃผ์๊ณ 2. dfs ํ๋ผ๋ฏธํฐ๋ก ๊ทธ ์ด์ ๊ฐ์ ๋ฐ์, ๊ทธ ์ด์ ๊ฐ๋ณด๋ค ํฐ ๊ฐ๋ค๋ง append ์์ผ์ฃผ์๋ค 4. ์์ค์ฝ๋ ๐ป import sys in..
-
[Python] 1987 ์ํ๋ฒณ(dfs)Algorithm/๋ฐฑ์ค 2023. 1. 19. 21:00
1. ๋ฌธ์ ๐ https://www.acmicpc.net/problem/1987 1987๋ฒ: ์ํ๋ฒณ ์ธ๋ก R์นธ, ๊ฐ๋ก C์นธ์ผ๋ก ๋ ํ ๋ชจ์์ ๋ณด๋๊ฐ ์๋ค. ๋ณด๋์ ๊ฐ ์นธ์๋ ๋๋ฌธ์ ์ํ๋ฒณ์ด ํ๋์ฉ ์ ํ ์๊ณ , ์ข์ธก ์๋จ ์นธ (1ํ 1์ด) ์๋ ๋ง์ด ๋์ฌ ์๋ค. ๋ง์ ์ํ์ข์ฐ๋ก ์ธ์ ํ ๋ค ์นธ ์ค์ ํ ์นธ์ผ www.acmicpc.net 2. ์ ์ถ๋ ฅ ์ ๐ 3. ์๊ณ ๋ฆฌ์ฆ โ ๊ทธ๋ํ ๋ฌธ์ + ๋ฐฑํธ๋ํน ๋ฌธ์ ์ด๋ค ์กฐ๊ฑด์ด ์ด๋ฏธ ํ๋ฒ ์ง๋์จ ์ํ๋ฒณ์ ๋ฐฉ๋ฌธํ ์ ์์์ด๋ฏ๋ก ์์ผ๋ก ๋์๊ฐ ๊ณณ์ด ์ด๋ฏธ ์ง๋์จ ์ํ๋ฒณ์ด๋ผ๋ฉด ๋ค๋ก ๊ฐ์ ๋ค์ ํ์์ ํด์ฃผ์ด์ฌํ๋ค bfs๋ก count๋ฅผ ์ธ์ด์ค๋ค์, ๊ฐ์ฅ ์ต๋๊ฐ์ ๋ฆฌํดํด์ฃผ์๋ค! ์ฌ๊ธฐ์ ํฌ์ธํธ๋ ์ฌ๊ทํธ์ถ์ด ๋๋๋ฉด ๋ค์ False๋ก ๋ฐ๊ฟ์ฃผ์ด ํ์์ ํด์ฃผ์ด์ผํ๋ค 4. ์์ค์ฝ๋ ๐ป impor..
-
[Python] 1759 ์ํธ ๋ง๋ค๊ธฐAlgorithm/๋ฐฑ์ค 2023. 1. 18. 21:23
1. ๋ฌธ์ ๐ https://www.acmicpc.net/problem/1759 2. ์ ์ถ๋ ฅ ์ ๐ 3. ์๊ณ ๋ฆฌ์ฆ โ ๋ฐฑํธ๋ํน ๋ฌธ์ ์ด๋ฏ๋ก ์กฐ๊ฑด์ ์ ๋๋ก ๋ด์ผํ๋ ์กฐ๊ฑด1. ์ค๋ณต๋ ๋ฌธ์๊ฐ ์์ ๊ฒ ์กฐ๊ฑด2. ์ํ๋ฒณ์ด ์ํธ์์ ์ฆ๊ฐํ๋ ์์๋๋ก ๋ฐฐ์ด ๋์ ๊ฒ ์กฐ๊ฑด3. ์ต์ ํ๊ฐ์ ๋ชจ์ ์ต์ 2๊ฐ์ ์์ 4. ์์ค์ฝ๋ ๐ป ์ฒ์์ ์คํจํด์ ๋ญ์ง ํ๋๋ฐ ์กฐ๊ฑด3์ ์๋ฐ์ก์๋ค ์๋๋ ๋ฐฑ์ค ์ง๋ฌธ๊ฒ์ํ์ ์๋ ๋ฐ๋ก์ด๋ค input: 3 6 a e i c d z output: acd acz adz cde cdi cez ciz dez dizโ import sys input = sys.stdin.readline L, C = map(int, input().strip().split()) alphabet = sorted(input()...
-
[Python] 3190 ๋ฑAlgorithm/๋ฐฑ์ค 2023. 1. 18. 21:15
1. ๋ฌธ์ ๐ https://www.acmicpc.net/problem/3190 2. ์ ์ถ๋ ฅ ์ ๐ 3. ์๊ณ ๋ฆฌ์ฆ โ ์ฒ์์ ๋ฌธ์ ๋ฅผ ์ดํดํ๋ ๋ฐ๋ง ์ค๋๊ฑธ๋ ธ๋ค;; ์ด๊ธฐ ์์์ (0, 0)์ผ๋ก ๋๊ณ 1์ด๋ผ๊ณ ๋ฌ์ผํ๋ค ๋ณด๊ธฐ ์ฝ๊ฒ $์ ๋ฑ @ ์ ์ฌ๊ณผ๋ผ๊ณ ๋๋ค ์์ 1์ ์ถ๋ ฅํด๋ณด๋ฉด time: 1 direction: Right $ . . . . . . . . . @ . . . . @ . . . . . . . . . . @ . . . . . . . . . time: 2 direction: Right . $ . . . . . . . . @ . . . . @ . . . . . . . . . . @ . . . . . . . . . time: 3 direction: Right . . $ . . . . . . . @ . . ..
-
[OS] Race ConditionComputer Science/OS 2023. 1. 17. 22:02
Race Condition ๋ ๊ฐ ์ด์์ cocurrentํ ํ๋ก์ธ์ค(ํน์ ์ค๋ ๋)๋ค์ด ํ๋์ ์์(๋ฆฌ์์ค)์ ์ ๊ทผํ๊ธฐ ์ํด ๊ฒฝ์ํ๋ ์ํ → ๋์ ์ ๊ทผ ์ ์๋ฃ์ ์ผ๊ด์ฑ์ ํด์น๋ ๊ฒฐ๊ณผ๊ฐ ๋ํ๋จ! e.g) ๊ณต์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ฌ์ฉํ๋ ํ๋ก์ธ์ค๋ฅผ ์ปค๋ ๋ด๋ถ ๋ฐ์ดํฐ๋ฅผ ์ ๊ทผํ๋ ๋ฃจํด๋ค ๊ฐ (์: ์ปค๋๋ชจ๋ ์ํ ์ค ์ธํฐ๋ฝํธ๋ก ์ปค๋๋ชจ๋ ๋ค๋ฅธ ๋ฃจํด ์ํ ์) OS์์ race condition์ ์ธ์ ๋ฐ์ํ๋ ๊ฐ? kernel ์ํ ์ค ์ธํฐ๋ฝํธ ๋ฐ์ - ๋ฌธ์ ์ : ์ปค๋๋ชจ๋์์ ๋ฐ์ดํฐ๋ฅผ ๋ก๋ํ์ฌ ์์ ์ ์ํํ๋ค๊ฐ ์ธํฐ๋ฝํธ๊ฐ ๋ฐ์ํ์ฌ ๊ฐ์ ๋ฐ์ดํฐ๋ฅผ ์กฐ์ํ๋ ๊ฒฝ์ฐ - ํด๊ฒฐ๋ฒ: ์ปค๋๋ชจ๋์์ ์์ ์ ์ํํ๋ ๋์, ์ธํฐ๋ฝํธ๋ฅผ disable ์์ผ CPU ์ ์ด๊ถ์ ๊ฐ์ ธ๊ฐ์ง ๋ชปํ๋๋ก ํ๋ค. Process ๊ฐ system call์ ํ๋ฉฐ k..
-
[OS] CPU ์ค์ผ์ค๋ง - 2 (์ค์ผ์ค๋ง ์๊ณ ๋ฆฌ์ฆ)Computer Science/OS 2023. 1. 17. 21:48
์ค์ผ์ค๋ง ์๊ณ ๋ฆฌ์ฆ 1. ์ ์ ์ ์ถ ์ค์ผ์ค๋ง(First-Come First-Servied: FCFS) ํ๋ก์ธ์ค๊ฐ ์ค๋น ํ์ ๋์ฐฉํ ์๊ฐ ์์๋๋ก CPU๋ฅผ ํ ๋นํ๋ ์๊ฐ ๋จผ์ ๋์ฐฉํ ํ๋ก์ธ์ค์ ์ฑ๊ฒฉ์ ๋ฐ๋ผ ํ๊ท ๋๊ธฐ์๊ฐ์ด ํฌ๊ฒ ๋ฌ๋ผ์ง๋ค ์ฝ๋ณด์ด ํ์์ด ๋ํ๋ ์ ์๋ค. ์ฝ๋ณด์ด ํ์ ? CPU ๋ฒ์คํธ๊ฐ ์งง์ ํ๋ก์ธ์ค๊ฐ CPU ๋ฒ์คํธ๊ฐ ๊ธด ํ๋ก์ธ์ค๋ณด๋ค ๋์ค์ ๋์ฐฉํด ์ค๋ ์๊ฐ์ ๊ธฐ๋ค๋ ค์ผํ๋ ํ์ 2. ์ต๋จ์์ ์ฐ์ ์ค์ผ์ค๋ง(Shortest-Job First: SJF) CPU ๋ฒ์คํธ๊ฐ ๊ฐ์ฅ ์งง์ ํ๋ก์ธ์ค์๊ฒ ์ ์ผ ๋จผ์ CPU๋ฅผ ํ ๋นํ๋ ๋ฐฉ์ SJF ์๊ณ ๋ฆฌ์ฆ์ ๋น์ ์ ํ ๋ฐฉ์๊ณผ ์ ์ ํ ๋ฐฉ์ ๋ ๊ฐ์ง๋ก ๊ตฌํ๋ ์ ์๋ค. ๋น์ ์ ํ ๋ฐฉ์(nonpreemptive) : ์ผ๋จ CPU๋ฅผ ํ๋ํ๋ฉด ๊ทธ ํ๋ก์ธ์ค๊ฐ CPU๋ฅผ ์์ง ๋ฐ๋ฉํ..
-
[OS] CPU ์ค์ผ์ค๋ง - 1 (CPU ์ค์ผ์ค๋ฌ, ์ค์ผ์ค๋ง ์ฑ๋ฅํ๊ฐ)Computer Science/OS 2023. 1. 17. 21:32
CPU ํ๋ก๊ทธ๋จ์ ๊ธฐ๊ณ์ด ๋ช ๋ น์ ์ค์ ๋ก ์ํํ๋ ์ปดํจํฐ ๋ด์ ์ค์ ์ฒ๋ฆฌ ์ฅ์น ์ฌ์ฉ์ ํ๋ก๊ทธ๋จ์ด ์ํ๋๋ ๊ณผ์ = CPU ๊ณผ์ + I/O ์์ ์ ๋ฐ๋ณต(์ ์ถ๋ ฅ ์์ ) CPU ๋ฒ์คํธ(burst) ์ฌ์ฉ์ ํ๋ก๊ทธ๋จ์ด CPU๋ฅผ ์ง์ ๊ฐ์ง๊ณ ๋น ๋ฅธ ๋ช ๋ น์ ์ํํ๋ ์ผ๋ จ์ ๋จ๊ณ I/O ๋ฒ์คํธ(burst) I/O ์์ฒญ์ด ๋ฐ์ํด ์ปค๋์ ์ํด ์ ์ถ๋ ฅ ์์ ์ด ์์ฒญ ๋ ํ ์๋ฃ๋์ด ๋ค์ CPU ๋ฒ์คํธ๋ก ๋์๊ฐ๊ธฐ๊น์ง ์ผ์ด๋๋ ์ผ๋ จ์ ์์ CPU ์ค์ผ์ค๋ฌ ์ค๋น ์ํ์ ์๋ ํ๋ก์ธ์ค๋ค ์ค ์ด๋ ํ ํ๋ก์ธ์ค์๊ฒ CPU๋ฅผ ํ ๋นํ ์ง ๊ฒฐ์ ํ๋ ์ด์์ฒด์ ์ ์ฝ๋ CPU ์ค์ผ์ค๋ฌ ๋ฐฉ์ ๋น์ ์ ํ ๋ฐฉ์ : ํ๋ก์ธ์ค ์ข ๋ฃ or I/O ๋ฑ์ ์ด๋ฒคํธ๊ฐ ์์ ๋๊น์ง ์คํ ๋ณด์ฅ(์ฒ๋ฆฌ์๊ฐ ์์ธก ์ฉ์ดํจ) ์ ์ ํ ๋ฐฉ์ : OS๊ฐ CPU์ ์ฌ์ฉ๊ถ์ ์ ์ ํ ์ ์๋ ๊ฒฝ..