풀이29 [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. [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 5 ··· 8 다음
