Java9 [백준] BOJ11053 가장 긴 증가하는 부분 수열 - LIS 알고리즘 LIS 알고리즘 - O(N^2) i 를 인덱스 1부터 시작하고, 그 때 j를 0부터 i-1 까지 보면서 최장증가수열을 구하는 알고리즘이다. dp[i] 값을 구하기 위해 이전(0...i-1) 배열값을 모두 다 보아야만 하기 때문에 N^2 의 시간이 걸린다. # 초기값 dp 배열은 1로 초기화 i는 index 1부터 시작해서 N-1까지 진행하고, 그 때마다 j 는 0…i-1 만큼 반복한다. j i arr[] 10 20 10 30 20 50 dp[] 1 1 1 1 1 1 # i = 1 1. j = 0 arr 값을 체크해서 arr[j] < arr[i] 이면, 증가 추세이므로 dp[i] = dp[j] + 1 해준다. j i arr[] 10 20 10 30 20 50 dp[] 1 2 1 1 1 1 # i = 2 1.. 2021. 12. 30. [백준] BOJ1197 최소 스패닝 트리 https://www.acmicpc.net/submit/1197/10143933 크루스칼 알고리즘을 이용하여 해결한 "최소 스패닝 트리" 문제이다. 문제에서 음수 데이터가 주어지고 있지만,크루스칼 알고리즘은 간선의 가중치가 작은것부터 차례대로 검사하며 골라가는 방식이기 때문에음수/양수 가중치에 모두 사용이 가능하다. import java.io.BufferedReader; import java.io.FileInputStream; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.StringTokenizer; public class Main { static int[] pa.. 2018. 9. 16. [백준] BOJ1922 네트워크 연결 - MST(최소신장트리) - 크루스칼 알고리즘 MST (Minimum Spanning Tree) - Kruskal 알고리즘 MST 란 모든 노드를 최소 비용으로 연결하는 알고리즘인데, 아래의 조건을 만족해야 한다. 1) 싸이클이 없어야 하고 2) 모든 노드가 연결되어야 한다. 이 때, a 노드에서 b 노드로 연결되어 있고, b 노드에서 c 노드로 연결되어 있다면, a 노드에서 c 노드로 연결되어 있다고 할 수 있다. Kruskal 알고리즘- 준비 // 간선을 가중치 기준으로 오름차순 정렬한다. // 모든 점을 하나의 트리로 설정한다. (Union & Find 기법 사용) - 시작 // 가중치가 작은 간선부터 하나씩 본다. // 해당 간선을 그래프에 추가할 때 싸이클이 생기지 않는다면 해당 간선을 그래프에 추가한다. 백준 BOJ1922 문제를 풀기 위.. 2018. 9. 16. [백준] BOJ1766 - 문제집 문제 출처 https://www.acmicpc.net/problem/1766 해당 문제는 위상정렬을 이용하여 풀 수 있는 문제. 문제간에는 우선순위가 있어서 먼저 푸는것이 좋은 문제의 경우 먼저 풀어야(방문) 한다. 단, 풀 수 있는 문제가 여러개인 경우 (indegree가 0 인 문제가 여러개인 경우) 문제 번호가 낮은 것이 더 쉬운 문제이므로 먼저 풀어야(방문) 한다. // 위상정렬 4 // Priority Queue 사용 import java.io.BufferedReader; import java.io.FileInputStream; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Comparator; imp.. 2018. 9. 9. 이전 1 2 3 다음
