TwoPointer

Algorithm/Baekjoon Online Judge
[Java] 백준 1509 (팰린드롬 분할) Gold 1
Problem : 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 Approach 주어진 문자열이 최소 몇 개의 팰린드롬 문자열로 구성되어 있는지를 구하는 문제이다. 팰린드롬 문자열 자체를 구하는 로직은 O(n^2) 의 시간복잡도를 가진다. 팰린드롬 문자열을 구하는 방법은 투포인터를 사용하였다. DP[i] 는 0 ~ i인덱스의 문자열이 몇 개의 최소 팰린드롬 문자열로 구성되는지..
→2021.04.16
Algorithm/Baekjoon Online Judge
[java] 백준 1644 (소수의 연속합) Gold 3
Problem : https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net Approach 한쪽에서 시작하는 투포인터를 활용한 문제였다. 주어진 수 N을 연속된 소수의 합으로 만드는 방법의 가짓수를 찾는 문제이다. 따라서, 일단 연속된 소수 수열을 구해야한다. 주어진 수 N이 소수라면 그 또한 방법 가짓수에 포함되기 때문에, 1 ~ N까지의 수들 중에서 소수를 모두 찾아야한다. 소수를 구하는 방법은 에라토스테네스의 체 방법을 사용하였다. 여기서는 해당 방법을 설명하진 않는다. start = 0, end = 0으로 시작한다. 에라토스테네스의 체를 활용하여 소수 수열을 구한다..
→2021.01.26
Algorithm/Baekjoon Online Judge
[java] 백준 1806 (부분합) Gold 4
Problem : https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net Approach 한쪽에서 시작하는 투포인터 문제이다. 연속된 수의 합이 S이상이 되는 것 중, 가장 짧은 길이를 찾는 문제이다. start와 end를 모두 배열의 처음부터 시작한다.(start = 0, end = 0) 나는 Index 처리 때문에 배열의 크기를 n+1로 지정해주었다. start와 end가 같다면, sum이 S이상이라면, 최소 길이는 1이다. 1보다 ..
→2021.01.25
Algorithm/Baekjoon Online Judge
[java] 백준 2470 (두 용액) Gold 5
Problem : https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net Approach 투포인터를 활용하여 풀었다. 주어진 용액들 중 두 용액을 합쳐 특성값이 0에 가장 가까운 혼합 용액을 만드는 문제이다. 주어진 용액들의 특성값은 중복값이 없다. 따라서 나는 우선 주어진 용액들의 특성값을 오름차순으로 정렬했다. 그런후 start = 0, end = length - 1로 정한 후,범위를 좁혀나가며 용액의 특성값들을 ..
→2021.01.24

• 이전
• 1
• 다음