LIS (4) 썸네일형 리스트형 [백준] 2352 반도체 설계 (JAVA) 풀이 LIS문제를 더풀어보고 DP문제를 더 풀어보자고 생각을해 문제들을 찾아보다가 이문제를 발견하였고 처음보았을때는 LIS를 그냥 적용하면 될것 같아 쉽네~ 이러고 했는데 시간초과까지는 아니지만 너무 오래 걸려서 풀렸다. 그래서 다른 방법이 있나 하고 찾아 보았고 해답은 바이너리 서치와 LIS 를 섞어서 푸는 것이였다. 기존의 LIS방식은 시간복잡도가 O(N*N)이였는데 이번에 풀은 방식의 시간복잡도는 O(NlogN)이다. 전체적인 큰틀은 다음과 같다. 1. 배열탐색하면서 가장큰수를 계속 뒤에 이어붙인다 2. 중간에 끼어들수 있는수는 이분탐색을 이용해, 적절한 위치에 있던 수와 교체한다. 3. 배열을 탐색하면서 맨앞요소보다 작은 요소가 새익면 맨앞요소를 교체한다. 처음에는 두번째와 세번째가 이해가 잘 되.. [백준] 2565 전깃줄 (JAVA) 풀이 이 문제는 가만히 생각하다 보니 복잡하지만 풀이가 보였다. 풀이 방법은 일단 문제에서 주어진 입력값을 전부 받고 그다음 가장 많이 겹치는 순으로 선을 제거해 겹쳐저있는 선들의 수를 계산 해나갔다. 그러나 이 방식으로 하면 시간도 오래걸리고 결론적으로 문제에서 틀렸다고 나오기도 하였다. (배열범위를 벗어났다고 나오지만...) 그래서 구글링을 하였고 역시 내가 생각한 풀이 방법보다 훨씬 깔끔했다. 나는 처음에는 문제에서 하라는대로 전선을 전부 이은후 하나씩 제거 해나갔는데 다른 사람들의 코드는 전부 연결한후 LIS방식으로 지우는 것이 아닌 최대 몇개까지 이을수있는것인가.를 구하고 전체에서 방금 구한수를 빼서 정답을 도출했다. 즉 전체집합에서 여집합을 빼서 구했다. 앞으로는 조금 유연하게 보도록 노력해야.. [백준]11055 가장 큰 증가 부분 수열 (java) 풀이 이 문제는 전형적인 LIS문제중 하나이다. 문제는 크게 어려울것이 없이 기준값이 정해지면 인덱스의 처음부터 마지막까지 돌아가면서 만약 증가하는 부분수열을 만족한다면 DP에 저장하면 된다. 그렇게 기준값을 끝까지 돌리고 난후 DP에 저장되어있는 수들중 가장큰수를 출력하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(ne.. [백준] 11053 가장 긴 증가하는 부분수열 (JAVA) 풀이 위의 문제는 대표적인 LIS문제로 dp를 이용해 푸는 문제이다. 만약 LIS알고리즘을 돌렸을때 특정 인덱스에서 현재의 값(seq)이 이전 인덱스의 값(seq)보다 크다면 이전 인덱스에서 만족하는 부분수열은 자연스럽게 만족하므로 현재위치의 dp는 특정인덱스의 dp에 +1을 하면 된다. (이전 인덱스의 수 또한 포함하므로.) 유사한 문제로 포도주문제나 계단오르기 가 있다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N; static Integer[] seq; stat.. 이전 1 다음
