๐ปProgramming/Algorithm
-
[ํ๋ก๊ทธ๋๋จธ์ค-level3] N์ผ๋ก ํํ๐ป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
-
[Algorithm] ์ฝ์ ์ ๋ ฌ(Insertion Sort)๐ปProgramming/Algorithm 2024. 3. 28. 18:22
์ฝ์ ์ ๋ ฌ์ด๋? ํ์ฌ ๋น๊ตํ๊ณ ์ ํ๋ target๊ณผ ๊ทธ ์ด์ ์ ์์๋ค๊ณผ ๋น๊ตํ๋ฉฐ ์๋ฆฌ๋ฅผ ๊ตํ(swap)ํ๋ ์ ๋ ฌ ๋ฐฉ๋ฒ. ์ ํ์ ๋ ฌ, ๋ฒ๋ธ์ ๋ ฌ๊ณผ๋ ๋ค๋ฅด๊ฒ ์์ ์ ๋ ฌ. ์ฝ์ ์ ๋ ฌ์ ๊ณผ์ (์ค๋ฆ์ฐจ์ ๊ธฐ์ค) 1. ์ธ๋ฑ์ค 1๋ถํฐ ์์ํ๋ค. ํ์ฌ ์ธ๋ฑ์ค๋ฅผ ํ๊ฒ ์ธ๋ฑ์ค๋ก ํ๊ณ ๋ณ์์ ๋ฃ๋๋ค. ์ด ๋ณ์๋ณด๋ค ์ด์ ์ธ๋ฑ์ค๊ฐ ์์ผ๋ฉด ์ด์ ์ธ๋ฑ์ค์ ๊ฐ์ ๊ทธ ๋ค์ ์ธ๋ฑ์ค์ ๋ฃ์ด์ค๋ค. 2. ๋ง์ฝ์ ์ธ๋ฑ์ค 2๊ฐ ํ๊ฒ์ด๊ณ , ํ๊ฒ์ ๊ฐ์ด ์ธ๋ฑ์ค 1๋ณด๋ค ์๋ค๋ฉด ๊ทธ ๋ค์ ์ธ๋ฑ์ค์ ๋ฃ๋๋ค. ๋ ์ธ๋ฑ์ค 0์ด ํ๊ฒ๋ณด๋ค ์์ผ๋ฉด ๋ ๊ทธ ๋ค์ ์ธ๋ฑ์ค์ ๋ฃ๋๋ค. ๊ทธ๋ฆฌ๊ณ ํ๊ฒ ์ธ๋ฑ์ค์ ๊ฐ์ ์ธ๋ฑ์ค 0์ ๋ฃ์ด์ค๋ค. 3. ์ด๋ฅผ ๊ณ์ ๋ฐ๋ณตํ๋ค. ๊ตฌํ ์ฝ๋ import java.util.Scanner; public class Main { private int[] s..
-
[Algorithm] ๋ฒ๋ธ ์ ๋ ฌ(Bubble Sort)๐ปProgramming/Algorithm 2024. 3. 27. 17:37
๋ฒ๋ธ ์ ๋ ฌ์ด๋? ์ ํ ์ ๋ ฌ๊ณผ ์ ์ฌํ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ์๋ก ์ธ์ ํ ๋ ์์์ ๋์๋ฅผ ๋น๊ตํ๊ณ , ์กฐ๊ฑด์ ๋ง์ง ์๋ค๋ฉด ์๋ฆฌ๋ฅผ ๊ตํํ๋ฉฐ ์ ๋ ฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ์ด๋ฆ์ ์ ๋๋ก๋ ์ ๋ ฌ ๊ณผ์ ์์ ์์์ ์ด๋์ด ๊ฑฐํ์ด ์๋ฉด์ผ๋ก ์ฌ๋ผ์ค๋ ๋ฏํ ๋ชจ์ต์ ๋ณด์ด๊ธฐ ๋๋ฌธ์ ์ง์ด์ก๋ค๊ณ ํ๋ค. ๊ณผ์ 1. ์ฒซ ๋ฒ์งธ ๋ฐ๋ณต๋ฌธ์์ ์ฒซ๋ฒ์งธ ์์์ ๋ ๋ฒ์งธ ์์๋ฅผ ๋น๊ตํ๋ค. ๋ง์ฝ ์ฒซ ๋ฒ์งธ ์์๊ฐ ๋ ํฌ๋ฉด ๊ตํ. ๋ ๋ฒ์งธ ์์์ ์ธ ๋ฒ์งธ ์์๋ฅผ ๋น๊ตํ ๋๋ฒ์งธ๊ฐ ํฌ๋ฉด ๊ตํ. ์ด๋ ๊ฒ ํด์ n-1๋ฒ์ฌ ์์๊น์ง ๋น๊ตํ๋ฉด ๊ฐ์ฅ ํฐ ์๋ n์ ๊ฐ์๊ฒ๋๋ค. 2. ๊ทธ๋ผ n์ ๊ฐ์ฅ ํฐ ์์ด๋๊น, ๋ค์ n-2์์๊น์ง ๋น๊ต๋ฅผ ๋ฐ๋ณต. ๊ทธ๋ผ ๋ ๋ฒ์งธ๋ก ํฐ ์๊ฐ n-1๋ฒ์ ๊ฐ๊ฒ ๋๋ค. ์ด๋ ๊ฒ ๋ฐ๋ณตํ๋ฉด ๋ชจ๋ ์๊ฐ ์ ๋ ฌ๋๋ค. ๊ตฌํ ์ฝ๋(Java) import java.util..
-
[Algorithm] ์ ํ์ ๋ ฌ(Selection Sort)๐ปProgramming/Algorithm 2024. 3. 26. 21:39
์ ํ์ ๋ ฌ์ด๋? ์ ๋ ฌ๋์ง ์์ ๋ฐ์ดํฐ๋ค์ ๋ํด ๊ฐ์ฅ ์์ ๋ฐ์ดํฐ๋ฅผ ์ฐพ์ ๊ฐ์ฅ ์์ ๋ฐ์ดํฐ์ ๊ตํํจ์ผ๋ก์จ ์ ๋ ฌํ๋ ์ ๋ ฌ ๋ฐฉ๋ฒ์ด๋ค. ์ ํ ์ ๋ ฌ์ ๊ณผ์ ์ ๊ฐ์ ์๋ฆฌ๋ก ์ค๋ฆ์ฐจ์ ์ ๋ ฌ์ด ๋๋ค. 1. ํ์ฌ์ ์ธ๋ฑ์ค๋ฅผ minIndex์ ๋ฃ์ด์ค๋ค. 2. ๊ทธ ๋ค์ ์ธ๋ฑ์ค์์ for๋ฌธ์ ๋๋ ค ๋ง์ฝ์ ๋ค๋ฅธ ์ธ๋ฑ์ค์ ๊ฐ์ด ๋ ์๋ค๋ฉด ๋ฐ๊ฟ์ค๋ค. ์ด๋ ๊ฒ ๋ง์ง๋ง๊น์ง ๋๋ฉด minIndex์ ์ธ๋ฑ์ค ๊ฐ์ ๊ฐ์ฅ ์์ ๊ฐ์ ๊ฐ์ง ์ธ๋ฑ์ค์ผ ๊ฒ์ด๋ค. ๋ง์ง๋ง ์ธ๋ฑ์ค๋ ์ด๋ฏธ ๊ทธ ์์ ์ธ๋ฑ์ค๋ฅผ ํตํด ๊ต์ฒด๊ฐ ๋์ด ๊ฐ์ฅ ํฐ ์์ผ ๊ฒ์ด๋ฏ๋ก for๋ฌธ์ n-1๋ฒ๊น์ง๋ง ๋๋ฉด ๋๋ค. ๊ตฌํ ์ฝ๋ import java.util.Scanner; public class Main { private int[] solution(int n, int[] list) { for..
-
[Algorithm] ์ฐ์ ๋ถ๋ถ์์ด๐ปProgramming/Algorithm 2024. 3. 5. 18:24
๋ฌธ์ N๊ฐ์ ์๋ก ์ด๋ฃจ์ด์ง ์์ด์ด ์ฃผ์ด์ง๋๋ค. ์ด ์์ด์์ ์ฐ์๋ถ๋ถ์์ด์ ํฉ์ด ํน์ ์ซ์ M์ด ๋๋ ๊ฒฝ์ฐ๊ฐ ๋ช ๋ฒ ์๋์ง ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์ธ์. ๋ง์ฝ N=8, M=6์ด๊ณ ์์ด์ด ๋ค์๊ณผ ๊ฐ๋ค๋ฉด 1 2 1 3 1 1 1 2 ํฉ์ด 6์ด ๋๋ ์ฐ์๋ถ๋ถ์์ด์ {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}๋ก ์ด 3๊ฐ์ง์ ๋๋ค. ๋ ์ด์ค for๋ฌธ์ ๋๋ฉด์ ํ์ดํ๋ฉด ์ฝ๊ฒ ์ง๋ง ๊ทธ๋ ๊ฒ ๋์์ ๊ฒฝ์ฐ ์๊ฐ๋ณต์ก๋๊ฐ O(N^2)๊ฐ ๋๊ธฐ ๋๋ฌธ์ ๋ง์ฝ N์ด 0~100000000 M๋ 0~1000000์ ๋ ๋๋ ๊ฒฝ์ฐ์๋ ์์ฒญ๋ ํฌ๊ธฐ๊ฐ ๋์ด๋ฒ๋ฆฐ๋ค. ๊ทธ๋์ ์ ๋ฒ์ ๋ฐฐ์ ๋ ์ฌ๋ผ์ด๋ฉ ์๋์ฐ(https://suucong.tistory.com/74)์๊ณ ๋ฆฌ์ฆ๊ณผ ํฌํฌ์ธํฐ(https://suucong.tistory.com/7..