본문 바로가기

C++33

[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++] 백준 1509: 팰린드롬 분할 (DP) https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 팰린드롬? 이 문제는 어떤 문자열을 팰린드롬으로 분할할 때 분할의 개수의 최솟값을 구해야하는 문제이다. 팰린드롬인지 아닌지는 10942: 팰린드롬? 문제와 같이 어떤 수가 팰린드롬일 때 양쪽끝(맨 처음과 맨 끝)을 제외한 가운데 부분도 팰린드롬이라는 사실을 이용하여 시간복잡도를 줄이며 확인할 수 있다. 그 과정은 아래 포스팅을 참.. 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.

티스토리툴바