알고리즘!76 [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++ ] 백준 2467: 용액 (두 포인터) https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 맨 처음에는 bruteforce하게 문제 접근하여 각 경우마다 안되는 경우를 계산하여 시간복잡도가 O(n^2/4)짜리 알고리즘을 짰지만 시간초과가 나왔다. 그 후 이 문제를 "두 포인터"를 이용해 풀었다. 두 포인터란? 두 포인터/ 투 포인터는 말 그대로 두 개의 포인터를 이용해 문제를 해결하는 알고리즘이다. 즉, 2개의 포인터를 구간의 길이를 가변적으로 잡아가며 특정 조건을 만족하는 구간 .. 2023. 10. 20. [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. 이전 1 2 3 4 ··· 19 다음
