lis
-
BOJ) 전깃줄 (2565 번)알고리즘/백준 2021. 1. 26. 19:18
전깃줄 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net A와 B 두 전봇대가 주어지고, 두 전봇대를 잇는 전기줄의 정보가 주어진다. 이 때, 전깃줄이 교차하는 경우를 없애기 위해 전깃줄을 제거해야 하는데, 가장 최소한의 전깃줄을 제거해서 교차하는 경우가 되게 만드는 문제다. 교차하는 가장 최소한의 전깃줄을 제거한다는 것은 전체 전깃줄에서 가장 올바르게 연결된 전깃줄 수를 빼주는 것과 성립한다. 전체 전깃줄 (n) - 가장 많이 올바르게 연결된 전깃줄 = 불필요하게 교차된 전깃줄의 최소값 여기서 가장 많이 올바르게 연..
-
BOJ) 가장 긴 바이토닉 부분 수열 (11054 번)알고리즘/백준 2021. 1. 7. 16:11
가장 긴 바이토닉 부분 수열 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 바이토닉 부분 수열은 요소들의 증감이 변곡점을 하나 이하로 가진 부분 수열이다. 즉, {1, 3, 5, 6, 4} 혹은 {1,2} 혹은 {7,3,5}와 같은 수열들이 바이토닉 수열이라 할 수 있다. 이 문제를 풀기 위해서는 LIS, LDS에 대한 개념이 있어야한다고 한다. LIS => Longest Increasing Subsequence (최장 증가 부분 수열) LDS => Longest Decreasing Subsequence (최장 감소 부분 수열)..
-
BOJ) 가장 긴 증가하는 부분 수열 (LIS, Longest Increasing Subsequence)알고리즘/백준 2020. 7. 27. 23:51
가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 어제 푼 가장 큰 증가하는 부분수열 (BIS)와 유사한 문제다. 다른 점이 있다면, 최대 값을 구하는 것이 아니라 최대 길이를 구하는 것이다. 그래서, Math.max를 통해 값을 증가 시켰던 것과 달리, Math.max를 통해 카운트를 증가시켜준다. 먼저, 자신만 존재하는 부분 수열에 대해서 dp[n]에 1을 저장한다. 이후, 탐색을 통해 자신보다 큰..