알고리즘
-
최단 경로 찾기 알고리즘 (다익스트라 / 플로이드 워셜) (python)Knowledge/Algorithm 2023. 7. 5. 15:38
최단 경로를 찾는 알고리즘 중 대표적인 두가지로는 다익스트라 알고리즘과 플로이드 워셜 알고리즘이 있습니다. 다익스트라 알고리즘 - 개념 다익스트라 알고리즘은 출발 노드에서 특정 노드로 가는 최단 경로를 구할 때 사용할 수 있는 알고리즘입니다. 출발 노드부터 시작해 그 노드에서 갈 수 있는 모든 방문하지 않은 노드를 방문 비용이 낮은 것 부터 확인하며 최단 거리 테이블을 갱신해 나가는 방식으로 최단 경로를 구해 나가며, 방문 비용이 낮은 것을 확인하기 위해 heap을 사용하는 것이 특징입니다. 다익스트라 알고리즘의 시간 복잡도는 최대 간선의 개수를 E, 노드의 개수를 V 라고 했을 때 O(ElogV) 입니다. - 구현 다익스트라 알고리즘 구현은 대표적인 유형인 백준 최소비용 구하기 문제를 예시로 풀며 진행..
-
백준 15988 1,2,3 더하기 3 동적계획법 활용 풀이 ( Java )Problem Solving/Java 2019. 11. 1. 20:15
15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 import java.io.*; public class Main { static int LIMIT = 1000000; static long MOD = 1000000009L; public static void main(String[] args) throws IOException { Buffere..
-
백준 1699 제곱수의 합 동적계획법 활용 풀이 ( Java )Problem Solving/Java 2019. 11. 1. 15:54
1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 import ..
-
백준 1912 연속합 동적계획법 활용 풀이 ( Java )Problem Solving/Java 2019. 11. 1. 12:55
1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br ..
-
백준 14002 가장 긴 증가하는 부분 수열 4 동적계획법 활용 풀이 ( Java )Problem Solving/Java 2019. 11. 1. 11:45
14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 백준 11053 가장 긴 증가하는 부분 수열 동적계획법 활용 풀이 (Java) 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열.. takeknowledge.tistory.com..
-
백준 11053 가장 긴 증가하는 부분 수열 동적계획법 활용 풀이 (Java)Problem Solving/Java 2019. 11. 1. 10:14
11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 import java.io.*; public class Main { public stati..
-
백준 2193 이친수 동적계획법 활용 2가지 풀이 ( Java )Problem Solving/Java 2019. 11. 1. 10:08
2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되 www.acmicpc.net - 2차원 배열 활용 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 ..
-
백준 16194 카드 구매하기2 동적계획법 활용 2가지 풀이 ( Java )Problem Solving/Java 2019. 10. 25. 21:50
16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net - Bottom-up 방식 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 import java.io.*; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRe..