알고리즘16 벨만포드 https://www.acmicpc.net/problem/1865 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main_1865_belman .. 2018. 9. 11. 최장 증가 수열 (LIS : Longest Increasing Subsequence) 1. 수열을 받는 A배열 2. LIS를 저장하는 L배열3. 순서를 저장하는 P배열 * O(NlogN) 로직1. LIS(L배열) 마지막 값보다 수열(A배열) 값이 크면 LIS 뒤에 추가2. 값이 작거나 같다면1) 같으면 continue;2) 작으면 lower bound를 이용하여 위치교환 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Stack; import java.util.StringTokenizer; public class Main { .. 2018. 7. 19. 에라토스 테네스의 체 작은 소수부터 목표값까지 곱해주면서 제거 for (int i = 2; i 2018. 7. 18. 최소 공통 조상(LCA : Lowest Common Ancestor) 1. 트리 깊이를 구할 K값을 구함 2. 깊이를 저장할 배열 depth3. 깊이에 따른 조상값을 저장할 배열 par4. 간선정보 저장5. 완전탐색(bfs 등)을 통하여 depth, par 배열 갱신6. 조상배열(par) 을 깊이에 따라 갱신 par[i][j] = par[i-1][par[i-1][j]];7. 문제에 따른 lca(a, b)수행1) a를 depth가 더 깊도록 swap2) a, b의 높이 차이 계산 diff3) diff를 2진법으로 변환하여 a값을 갱신4) a 와 b의 값이 동일하면 a를 return5) 다르면 K보다 1개 작은 차수부터 부모차수까지 이동하면서 값 갱신6) a의 부모 (par[0][a]) 값이 lca import java.io.BufferedReader; import java... 2018. 7. 18. 이전 1 2 3 4 다음