728x90 반응형 Dynamic Programming16 2022.02.09 [백준] C# LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-S.. 2022. 2. 9. 2022.02.09 [백준] C# 전깃줄 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 최소한의 겹쳐진 전깃줄을 제거하여 전부 겹치지 않게 만들라고 하는 문제이다. 이 문제를 반대로 생각하면 겹치지 않은 전깃줄의 최장증가수열을 찾은 뒤 전체 전깃줄의 수에서 빼면 제거해야하는 최소한의 전깃줄의 갯수를 구할 수 있다. 주어진 배열을 arr배열에 담고 최장 증가수열의 길이를 담을 count배열을 만들어 전체에 1을 설정해준다.(자기 자신만 있어도 최장 증가수열은 1이기 때문) 그리고 이중f.. 2022. 2. 9. 2022.02.08 [백준] C# 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 주어진 배열을 arr에 담고 배열의 각 인덱스에서의 최대 연속합을 sum배열에 담아서 해결했습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60.. 2022. 2. 8. 2022.02.08 [백준] C# 가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 이 문제는 1~n까지의 LIS를 구해서 upper배열에 저장하고 반대로 n~1까지 LIS를 구해서 lower배열에 저장했다. num의 배열에 순서대로 하면 최장 증가수열이고, 반대로 하면 최장 감소 수열이기 때문이다. 그리고 upper[i] + lower[i] -1 (-1을 해주는 이유는 i가 겹치기 때문)을 해주어 답을 구했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 .. 2022. 2. 8. 이전 1 2 3 4 다음 728x90 반응형
