본문 바로가기

분류 전체보기411

[백준] 11053번 : 가장 긴 증가하는 부분 수열 – JAVA [자바] https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 문제 풀이 백준 11053번 가장 긴 증가하는 부분 수열은 DP 문제, 그중에서도 LIS를 이용해서 푸는 문제이다. LIS를 공부하고 싶으면 밑에 있는 링크를 참고하면 되겠다. ※참고※ https://propercoding.tistory.com/41 [알고리즘] LIS (최장 증가 부분 수열) 목차 LIS란? LI.. 2022. 3. 31.
[알고리즘] LIS (최장 증가 부분 수열) 목차 LIS란? LIS는 Longest Increasing Subsequence의 약자이다. 말 그대로 최장 증가 부분 수열, 또는 가장 긴 증가하는 부분 수열이라고 불린다. LIS는 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 알고리즘이다. 다만, 오름차순으로 정렬된 부분 수열이 연속적이거나, 유일할 필요는 없다. 풀이 방법으로는 DP를 활용한 방법과 이진 탐색을 활용한 방법이 있다. DP를 활용하면 조금 더 단순하지만 시간 복잡도가 O(n^2)이고 이진 탐색을 활용하면 조금 더 복잡하지만 시간 복잡도는 O(n logn)이다. 이번 글에서는 DP를 활용한 LIS만 살펴보도록 하겠다. LIS 접근 방법 & 예시 예시를 한번 보겠다. 수열 arr = {10, 20, 10, 30, 20, .. 2022. 3. 31.
[백준] 11060번 : 점프 점프 – JAVA [자바] https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 문제 문제 풀이 백준 11060번 점프 점프는 DP를 이용해서 푸는 실버 2 난이도의 백준 문제이다. DP를 조금 더 공부하고 싶으면 밑에 있는 링크를 참고하면 되겠다. https://propercoding.tistory.com/entry/알고리즘-다이나믹-프로그래밍-Dynamic-Programming [알고리즘] 다이나믹 프로그래밍 (Dynamic Programming) 목차 다이나믹.. 2022. 3. 30.
[백준] 14495번 : 피보나치 비스무리한 수열 – JAVA [자바] https://www.acmicpc.net/problem/14495 14495번: 피보나치 비스무리한 수열 피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다. 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ... 자연수 n을 입력받아 n번째 피보 www.acmicpc.net 문제 문제 풀이 백준 14495번 피보나치 비스무리한 수열은 DP를 이용해서 푸는 문제이다. DP 이론을 조금 더 공부하고 싶으면 밑에 있는 링크를 참고하면 되겠다. https://propercoding.tistory.com/entry/알고리즘-다이나믹-프로그래밍-Dynamic-Programming [.. 2022. 3. 29.
반응형

티스토리툴바