๐ปProgramming/Algorithm
-
[๋ฐฑ์ค] ์ด๋ถ ๊ทธ๋ํ(๊ณจ๋4)๐ปProgramming/Algorithm 2025. 9. 10. 18:30
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/7569 ์ด๋ถ ๊ทธ๋ํ(Bipartite Graph)์ ์ ์- ์ ์ ์ ๋ ๊ทธ๋ฃน์ผ๋ก ๋๋ ์ ์๋ ๊ทธ๋ํ- ์ด๋ถ ๊ทธ๋ํ๊ฐ ๋ ์ ์๋ ์กฐ๊ฑด: ๊ฐ์ ๊ทธ๋ฃน ์์๋ ๊ฐ์ ์ด ์์ด์ผํจ- ์ฆ ๋ชจ๋ ๊ฐ์ ์ ๋ค๋ฅด ๊ทธ๋ฃน์ ์ฐ๊ฒฐ ์์๊ทธ๋ฃน 1: {A, B} ๊ทธ๋ฃน 2: {C, D} ๊ฐ์ : A-C, A-D, B-C, B-D → ๊ฐ๋ฅ โ ๊ฐ์ : A-B → A์ B๊ฐ ๊ฐ์ ๊ทธ๋ฃน → โbfs ์ด์ฉ ๋ฌธ์ - is_bipartite ํจ์์์ ์ ์ฒด for ๋ฌธ์ ๋๋ ์ด์ : ๊ทธ๋ํ๊ฐ ์ฐ๊ฒฐ ๊ทธ๋ํ๊ฐ ์๋ ์๋ ์๊ธฐ ๋๋ฌธ์ - bfs ๊ตฌํ ์ฝ๋- ์ธ์ ๋ ธ๋๋ค์ ๋ชจ๋ ๋๋ฉด์ ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ๋ ธ๋์ธ ๊ฒฝ์ฐ ํ์ฌ ๋ ธ๋์ ๋ฐ๋ ์๊น์ ์ ์ฉ- ๋ง์ฝ ๋ฐฉ๋ฌธํ ๋ ธ๋์ธ๋ฐ ํ์ฌ ๋ ธ๋์ ์์ด ๊ฐ์ ๊ฒฝ..
-
[๋ฐฑ์ค] ํ ๋งํ (๊ณจ๋5)๐ปProgramming/Algorithm 2025. 9. 9. 21:17
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/7569 bfs(๊ทธ์ค์์๋ ๋ฉํฐ์์ค bfs) ์ด์ฉ ๋ฌธ์ 1. ์์์ด ๋งจ ์ฒซ๋ฒ์งธ ์ธ๋ฑ์ค์์๊ฐ ์๋-> 3์ค for๋ฌธ์ ๋๋ฉฐ ์ต์ ํ ๋งํ ๋ฅผ ๋ชจ๋ ํ์ ์ฝ์ 2. ํ๋ฅผ ๋๋ฉฐ ์ต์ ํ ๋งํ ์ ์๋ ์ ์ผ์ชฝ ์ค๋ฅธ์ชฝ ์ ๋ค๋ฅผ ํ์ฌ ์ต์ ํ ๋งํ ๊ฐ + 1 ์ ํด์ ๋ฃ์ด์ค -> ์ต์ ์ผ์๋ฅผ ๊ตฌํ๋ ํต์ฌ ํฌ์ธํธ์ด ๊ฐ์ด ์ต์ ์ผ์๋ฅผ ์๋ฏธ 3. ํ ์์๋ค์ด ๋ชจ๋ ์์ง๋๋ฉด 3์ค for๋ฌธ์ ํตํด ๊ทธ๋ํ๋ฅผ ๋๋ฉฐ ๋ชจ๋ ํ ๋งํ ๊ฐ ์ต์๋์ง ๋ต์ด ๋ฌด์์ธ์ง ํ์ธํจ- ์ฌ๊ธฐ์ max๋ฅผ ํตํด ์ผ์๋ฅผ ์ฐพ๋๋ฐ ์ ์ต์ ์ผ์๋ฅผ ์ฐพ์ผ๋ฉด์ ์ต๋ ์ผ์๋ฅผ ๊ตฌํ๋ ๋ผ๋ ์๋ฌธ์ด ์๊ธธ ์ ์์๊ฐ์ฅ ๋ฆ๊ฒ ์ต์ ํ ๋งํ ๊ฐ ์ต์ ๋ ์ง๋ฅผ ์์์ผํจ ๊ตฌํ ์ฝ๋from collections import dequ..
-
[๋ฐฑ์ค] ๋ฒฝ ๋ถ์๊ณ ์ด๋ํ๊ธฐ(๊ณจ๋3)๐ปProgramming/Algorithm 2025. 9. 8. 18:31
๋ฌธ์ ๋งํฌhttps://www.acmicpc.net/problem/2206 BFS ์ด์ฉ ๋ฌธ์ 1. q์ ๋ฃ๋ ์ ๋ณด: y, x, , ์ง๊ธ๊น์ง ์จ ๊ฑฐ๋ฆฌ 2. ํ์ฌ ์ธ๋ฑ์ค์์ dy, dx ๋ณ์๋ฅผ ์ด์ฉํ์ฌ ์ํ์ข์ฐ๋ฅผ ์ด๋ํ๋ฉฐ,๋ค์์ q์ ๋ฃ์ด์ค ์ธ๋ฑ์ค(y, x)๊ฐ ๋ฐฐ์ด์ ์ธ๋ฑ์ค ๋ฒ์๋ฅผ ๋ฒ์ด๋์ง ์๋์ง ํ์ธ 3. ๋ฒฝ์ด ์๋๊ณ ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ๊ฒฝ์ฐ / ๋ฒฝ์ด๊ณ ์์ง ๋ฒฝ์ ๋ถ์์ ์ด ์๋ ๊ฒฝ์ฐ๋ก ๋๋์ด q์ ์ฝ์ -> ๋ฒฝ์ธ๋ฐ ์ด๋ฏธ ๋ฒฝ์ ํ ๋ฒ ๋ถ์์ ์ด ์๋ ๊ฒฝ์ฐ๋ ์๋์ผ๋ก ์ค๋จ๋จ 4. ๋ต์ return y, x๊ฐ n-1, m-1์ ๋๋ฌํ์ ๊ฒฝ์ฐ dist ๋ณ์ returnwhile๋ฌธ์ด ์ข ๋ฃ๋์๋๋ฐ dist๊ฐ return ๋์ง ์์ ๊ฒฝ์ฐ-> 0, 0์์ n-1, m-1๋ก ๊ฐ๋ ๊ฒฝ๋ก๊ฐ ์กด์ฌํ์ง ์์ผ๋ -1 return ..
-
[๋ฐฑ์ค] ํธ๋ฆฌ์ ์ง๋ฆ(๊ณจ๋4)๐ปProgramming/Algorithm 2025. 9. 2. 16:25
๋ฌธ์ ๋งํฌhttps://www.acmicpc.net/problem/1967 ํธ๋ฆฌ์ ์ง๋ฆ ์๊ณ ๋ฆฌ์ฆ ๊ตฌํ1. ์๋ฌด ๋ ธ๋์์ ์์ํด์ ๊ฐ์ฅ ๋จผ ๋ ธ๋๋ฅผ ์ฐพ๋๋ค. (DFS ์ด์ฉ) ์ฌ๊ธฐ์๋ 1- ์๋ฅผ ๋ค์ด์ 1๋ฒ ๋ ธ๋์์ DFS/BFS ๋ฅผ ๋๋ ค์ ๊ฐ์ฅ ๋จผ ๋ ธ๋๋ฅผ ์ฐพ๊ณ , ๊ทธ๊ฒ9๋ผ๊ณ ํ์- ์ด๋ 9๋ฒ ๋ ธ๋๋ ํธ๋ฆฌ์ ํ์ชฝ ๋(leaf)์ 2. ๊ฐ์ฅ ๋จผ ๋ ธ๋ 9์์ ๋ค์ํ๋ฒ DFS9์์ ๊ฐ์ฅ ๋จผ ๋ ธ๋๋ฅผ ์ฐพ์ผ๋ฉด ๊ทธ๊ฒ ๋ค๋ฅธ ์ชฝ ๋ ๋ ธ๋์ -> ์ง๋ฆ ์๋ฏธ ํธ๋ฆฌ์ ํน์ง์ ์ด์ฉ -> ์ด๋ค ๋ ธ๋์์ ๊ฐ์ฅ ๋ฉ๋ฆฌ ์๋ ๋ ธ๋๋ ํญ์ ์ง๋ฆ์ ์ ๋ ์ค ํ๋๊ฐ ๋๋ค. ์ฝ๋import syssys.setrecursionlimit(10**6)input = sys.stdin.readlinen = int(input())graph = [[] for ..
-
[ํ๋ก๊ทธ๋๋จธ์ค] N์ผ๋ก ํํ(level3)๐ปProgramming/Algorithm 2025. 8. 29. 16:57
๋ฌธ์ ๋งํฌhttps://school.programmers.co.kr/learn/courses/30/lessons/42895 ํ๋ก๊ทธ๋๋จธ์คSW๊ฐ๋ฐ์๋ฅผ ์ํ ํ๊ฐ, ๊ต์ก์ Total Solution์ ์ ๊ณตํ๋ ๊ฐ๋ฐ์ ์ฑ์ฅ์ ์ํ ๋ฒ ์ด์ค์บ ํprogrammers.co.kr ๋์ ๊ณํ๋ฒ(Dynamic Programming) ์ด์ฉ ๋ฌธ์ 1. ์ ํ์ ์๋ฏธ ์ ์dp[i]: N์ ์ ํํ i๋ฒ ์ฌ์ฉํ์ฌ ๋ง๋ค ์ ์๋ ๋ชจ๋ ์๋ค์ ์งํฉ 2. dp ์ด๊ธฐํN์ ํ ๋ฒ ์ฌ์ฉํ๋ฉด ํํํ ์ ์๋ ์๋ N๋ฟ dp[1] = {N} 3. ๋ฐ๋ณต๊ตฌ์ฑ i = 2 ~ 8dp[i]์ ์ซ์๋ฅผ ์ด์ด๋ถ์ธ ๊ฐ int(str(N) * i)์ ์ถ๊ฐ1~i๊น์ง j ๋ณ์๋ฅผ ํตํด ๋๋ฉด์ dp[j]์ dp[i-j]๋ฅผ ์ด์ฉํด + , -, *, // ์ฌ์น์ฐ์ฐ i ๋ฐ๋ณต๋ฌธ..
-
[Algorithm] BFS, DFS (with Python)๐ปProgramming/Algorithm 2024. 6. 28. 16:03
BFS(Breadth First Search, ๋๋น ์ฐ์ ํ์)์ด ์๊ณ ๋ฆฌ์ฆ์ ํต์ฌ์ ํ(Queue)๋ฅผ ์ฌ์ฉํ๋ ๊ฒ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ๋ฉด์ ์ธ์ ํ ๋ ธ๋ ์ค ๋ฐฉ๋ฌธํ์ง ์์๋ ๋ ธ๋์ ์ ๋ณด๋ฅผ ํ์ ๋ฃ์ด ํ์ ๋จผ์ ๋ค์ด์๋ ๋ ธ๋๋ถํฐ ๋ฐฉ๋ฌธ.list ํ์์ ์ฌ์ฉํด ํ๋ฅผ ๊ตฌํํ ์๋ ์์ง๋ง, list.pop(0)์ ์๊ฐ๋ณต์ก๋๊ฐ O(N)์ด๋ฏ๋ก ๋นํจ์จ์ . -> collections ๋ผ์ด๋ธ๋ฌ๋ฆฌ์ deque๋ฅผ ์ฌ์ฉ. ๋ฐฉ๋ฌธํ์ง ์์๋ ๋ ธ๋๋ฅผ ํ์ ๋ฃ์๋๋ setํ์ ์ ์ฌ์ฉ. DFS(Depth First Search, ๊น์ด ์ฐ์ ํ์)์ด ์๊ณ ๋ฆฌ์ฆ์ ํต์ฌ์ ์คํ(Stack)์ ์ฌ์ฉํ๋ ๊ฒ.
-
[Algorithm] ์ฌ๊ทํจ์๋ฅผ ์ด์ฉํ ํผ๋ณด๋์น ์์ด ๊ตฌํ๐ปProgramming/Algorithm 2024. 4. 11. 17:34
๋ฌธ์ 1) ํผ๋ณด๋ํค ์์ด์ ์ถ๋ ฅํ๋ค. ํผ๋ณด๋์น ์์ด์ด๋ ์์ 2๊ฐ์ ์๋ฅผ ํฉํ์ฌ ๋ค์ ์ซ์๊ฐ ๋๋ ์์ด์ด๋ค. 2) ์ ๋ ฅ์ ํผ๋ณด๋์น ์์ด์ ์ด ํญ์ ์ ์ด๋ค. ๋ง์ฝ 7์ด ์ ๋ ฅ๋๋ฉด 1 1 2 3 5 8 13์ ์ถ๋ ฅํ๋ฉด ๋๋ค. ๋ฉ๋ชจ์ด์ ์ด์ ์ ์ฌ์ฉํ์ง ์์ ๊ตฌํ import java.util.Scanner; public class Section7_4_Ver1 { public static int DFS(int n) { if (n == 1 || n == 2) return 1; else return DFS(n - 2) + DFS(n - 1); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scann..
-
[Algorithm] ์ด์งํ์(Binary Search)๐ปProgramming/Algorithm 2024. 4. 9. 15:15
์ด์งํ์์ด๋? "์ ๋ ฌ๋์ด ์๋ ๋ฐ์ดํฐ"์์ ํน์ ํ ๊ฐ์ ์ฐพ์๋ด๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ๋ฌธ์ ์์์ N๊ฐ์ ์ซ์๊ฐ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋๋ค. N๊ฐ์ ์๋ฅผ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ ๋ค์ N๊ฐ์ ์ ์ค ํ ๊ฐ์ ์์ธ M์ด ์ฃผ์ด์ง๋ฉด ์ด๋ถ๊ฒ์์ผ๋ก M์ด ์ ๋ ฌ๋ ์ํ์์ ๋ช ๋ฒ์งธ์ ์๋์ง ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์ธ์. ๋จ ์ค๋ณต๊ฐ์ ์กด์ฌํ์ง ์์ต๋๋ค. ์ ๋ ฅ ์ฒซ ์ค์ ํ ์ค์ ์์ฐ์ N(3