알고리즘!/Dynamic Programming33 [C/C++] 백준 14003: 가장 긴 증가하는 부분 수열 5 (Backtrace) https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 풀이! 이 문제에서 가장 긴 증가하는 부분 수열의 길이를 구하는 알고리즘의 동작방식은 12015: 가장 긴 증가하는 부분 수열 2와 같다. 12015 문제와 다른 점은 이 문제는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력해야한다. 그렇기 때문에 경로를 저장하고 나중에 이 경로를 다시 찾아야한다. 먼저 가장 긴 증가하는 부분 수열의 길이를 구하는 방법은 아.. 2023. 10. 21. [C/C++] 백준 10942: 팰린드롬? (DP) https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이? 먼저 펠린드롬이란 거꾸로 읽어도 제대로 읽는 것과 같은 문장을 뜻한다. 이 문제에서는 각 질문에 대하여 팰린드롬인지 아닌지를 답해야 하는데 질문의 개수가 10^6이고 수열의 크기가 최대 2000이기 때문에 사실상 각 질문마다 팰린드롬인지 확인을 한다면 시간복잡도가 O(NM)이 되기 떄문에 시간안에 풀 수 없다. 그렇기 때문에 각 수가 팰린드롬인지 아닌지를 새로운 배열에 저장해가며 풀어야만 시간 내의 해결이 가능하다. 다만 각 질.. 2023. 10. 21. [C/C++] 백준 7579: 앱 (Kanpsack-DP) https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 이 문제도 무게(weight)와 가치(value)이 존재하는 전형적인 배낭(Knapsack) 문제이다. 배낭 문제를 해결하는 방법은 용량/비용을 이용하여 backtracking을 하는 방법도 있지만 가장 널리 쓰이고 구현하기 쉬운 Dynamic Programming이 대표적이다. 이 문제 역시 Dynamic Programming을 이용하여 문제를 해결했다. Kanpsack 알고리즘! 배낭 문제를 DP로 .. 2023. 10. 20. [C/C++] 백준 9252: LCS 2 (Backtrace) https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이? 문제에서도 친절히 적혀있다싶이 LCS(Longest Common Subseuqence)를 구하면 되는데 이는 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. LCS 길이 알고리즘 무식하게 모든 경우의 수를 따지면서 풀 경우 문자열의 길이가 n,m(n>arr1>>arr2; int n=arr1.length(),m=arr2.leng.. 2023. 10. 18. 이전 1 2 3 4 ··· 9 다음
