Lis5 [자바] 백준 12738 - 가장 긴 증가하는 부분 수열 3 (java) 문제 : boj12738 필요 알고리즘 개념 LIS (Longest Increasing Subsequence; 가장 긴 증가하는 부분 수열) LIS 알고리즘을 사용해 푸는 문제이다. 이분탐색, 매개변수 탐색법(parametric search) LIS 알고리즘 구현을 위해 가장 중요한건 이분탐색에서 그보다 큰 가장 작은 값 혹은 그보다 작은 가장 큰 값을 알 수 있는 매개변수 탐색법이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.. 2022. 8. 29. 백준 14002 자바 - 가장 긴 증가하는 부분 수열 4 (BOJ 14002 JAVA) 문제 : boj14002 가장 긴 증가하는 부분 수열의 길이 자체는 이분탐색을 활용한 LIS 알고리즘을 쓰면 얻을 수 있다. 하지만 LIS 알고리즘은 가장 긴 증가하는 부분 수열의 '길이'를 파악할 뿐이고, 이 문제에서는 가능한 수열 중 하나를 출력하는 방법도 찾아야 한다. LIS 알고리즘에 대한 설명은 생략하고, 가능한 수열을 찾는 방법에 대해 설명한다. 1. LIS 알고리즘에서 입력이 10 20 30 5 15 가 들어오면 어떻게 될까? 최종적으로 LIS의 길이인 '3'은 구해낼 수 있으나, 배열에는 다음과 같이 '5 15 30' 이라는 값이 들어가 있게 된다. 실제 정답은 '10 20 30'이므로 LIS 알고리즘 자체만 사용해서는 원하는 실제 수열을 출력할 수 없다. 2. 추가로 배열을 더 사용해서 .. 2021. 12. 21. 백준 14003 JAVA - 가장 긴 증가하는 부분 수열 5 (BOJ 14003 JAVA) 문제 : boj14003 8달전에 못풀고 키핑해뒀던 문제인데, 이번에도 못풀 뻔 했다가 겨우 풀었다. 확실히 플래는 아직 많이 까다롭다. 일단 가장 긴 증가하는 부분 수열의 길이 자체는 이분탐색을 활용한 LIS 알고리즘을 쓰면 얻을 수 있다. 하지만 LIS 알고리즘은 가장 긴 증가하는 부분 수열의 '길이'를 파악할 뿐이고, 이 문제에서는 가능한 수열 중 하나를 출력하는 방법도 찾아야 한다. LIS 알고리즘은 나름대로 잘 알려진 알고리즘이므로 제외하고, 수열 자체를 찾는 방법에 대해 써보겠다. 1. LIS 알고리즘에서 입력이 10 20 30 5 15 가 들어오면 어떻게 될까? 최종적으로 LIS의 길이인 '3'은 구해낼 수 있으나, 배열에는 다음과 같이 '5 15 30' 이라는 값이 들어가 있게 된다. 실제.. 2021. 12. 8. 백준 1365 자바 - 꼬인 전깃줄 (BOJ 1365 JAVA) 문제 : boj1365 이 단어를 제가 쓰게될줄은 몰랐는데.. 'Well-Known'한 문제이다. DP쪽엔 냅색류가 유명하듯, 이분탐색쪽도 뭔가 선 꼬인거에서 안꼬이게 최대치 이런 종류의 문제가 유명하다. 사실 이런 류의 문제를 접해보지 못했다면 아이디어를 떠올리기 힘들 수 있다. 아이디어는 어떨 때 꼬이는지를 확인해보면 된다. -> 간단히 순서대로 선을 이어줄 때, 직전에 들어왔던 입력값보다 작은 값이 입력되면 꼬이게 된다. 예를들어 아래와 같은 경우 좌측의 순서대로 우측에 매칭된 숫자는 1, 3, 4, 2가 된다. 이 때 꼬인 부분은 이전보다 작은 값이 들어온 [4, 2] 부분이 된다. 그럼여러 경우를 테스트 해보면, 위와 같이 서로 겹치지 않게(안꼬이게) 하려면 단순히 subsequence(1,3,.. 2021. 12. 1. 백준 13711 자바 - LCS 4 (BOJ 13711 JAVA) 문제 : https://www.acmicpc.net/problem/13711 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/13700/BOJ_13711.java [ 스포 주의 ] 직접 풀어보려면 풀이를 보면 안됩니다. 딱 한마디로 바로 풀이가 끝나는 문제라.. --- LCS 시리즈인척 하는 LIS 문제입니다. LCS ; Longest Common Subsequence LIS ; Longest Increasing Subsequence [오답] 1. 문제제목이 LCS라서 처음엔 LCS 알고리즘으로 풀었습니다. -> 답이야 나오겠지만 당연히 메모리초과 (10만x10만xsizeof(int)) 2. 어차피 N x N 배열이 필요없으므로 배열.. 2021. 11. 9. 이전 1 다음
