알고리즘9 [백준] 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. [백준] BOJ1699 제곱수의 합 DP 문제https://www.acmicpc.net/problem/1699 특정수를 제곱수의 합으로 나타낼 때, 그 항의 최소 개수를 구하는 문제이다.즉 12 를 제곱수(1, 4, 9, 16, ...)의 합으로 구하는 방법은 아래와 같이 여러개가 존재한다.1) 9 + 1 + 1 + 1 (4항)2) 4 + 4 + 4 (3항)3) 4 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 (9항) 즉, 12 를 표현하는 항의 최소 개수는 3항 임을 알 수 있다.여기서 조심해야 할 점은, 사용할 수 있는 제곱근 중 가장 큰 수 ( = 9) 를 사용하는 1번 방법이 항상 좋은 것은 아니다.그렇기 때문에, dp를 이용하여 풀어나간다. dp 배열은 i 값을 제곱근의 합으로 나타냈을 때 가장 최소값을 가진다. **.. 2018. 11. 4. [백준] BOJ2211네트워크 복구 https://www.acmicpc.net/problem/2211 네트워크 복구라는 문제인데 해당 문제를 풀기 위해 아래 2가지 알고리즘을 사용했다. 1) 다익스트라 2) 프림 import java.io.BufferedReader; import java.io.FileInputStream; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.Queue; import java.util.StringTokenizer; p.. 2018. 9. 25. [백준] 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. 이전 1 2 3 다음
