백준36 [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++] 백준 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. [C/C++] 백준 1644: 소수의 연속합 (에라토스테네스의 체 & 부분 합) https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이! 이 문제를 풀기 위한 과정은 크게 2가지로 나뉜다. 첫번째로는 1부터 n번째까지의 수들 중에서 소수들을 구해야하는 것이고 두번쨰로는 부분 합을 이용하여 연속된 소수의 합으로 주어진 자연수를 나타낼 수 있는 경우의 수를 구하는 과정이다. 첫번째 과정은 소수 판정을 위한 에라토스테네스의 체를 사용하면 되고 두번째는 부분 합을 이용하면 된다. 에라토스테네스의 체 에라토스네스의 체란? 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 만들어낸 소수를 찾는 방법으로 체로 치듯이 수를 걸러낸다고 하여 뒤에 '체'.. 2023. 10. 14. [C/C++] 백준 1806: 부분합 (누적 합 이용) https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이! 사실 문제 이름 자체도 부분합이고 문제 내용도 부분합이라서 "누적합"을 이용하여 문제를 풀어야겠다는 생각을 할 수 있었다. 부분 합(누적 합) 부분 합이란 배열의 시작부터 현재 위치까지의 원소의 합을 구해둔 배열이다. 이렇게 부분 합을 미리 구해 놓는다면 a번째 index부터 b번째 index까지의 합을 구할 때 O(b-a)의 시간이 걸릴 것을 psum[b]-psum[a-1].. 2023. 10. 14. 이전 1 2 3 4 ··· 9 다음
