투_포인터

[C++] 백준 22862번 가장 긴 짝수 연속한 부분 수열 (large)

22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 투 포인터 문제. 투 포인터라는 점을 알 수 있다면 쉽게 풀 수 있는 문제. 나는 BaaaaaaaaaaarkingDog 님의 0x14강 - 투 포인터 문제집인 것을 알 수 있어서 바로 투 포인터로 풀었다. 문제 풀이 다음과 같은 조건으로 풀었다. 각 포인터인 L이 왼쪽, R이 오른쪽이라 할 때, 현재 R이 짝수면 R을 한 번 더 움직인다. 현재 R이 홀수이지만, 홀수의 삭제가 가능하다면 R을 한 번 더 움직인다. 위 두 조건에 해당하지 않으면 다음과 같은 조건으로 확인한다. R이 L보다 우측에 ..

[C++]백준 1806번 부분합

투 포인터 문제. 바로 이전에 풀었던 2230번 수 고르기 문제와 비슷한 유형의 문제이다. 정렬하지 않고 푸는 투 포인터 문제이다. 문제풀이 연속된 수들의 합 중에서 길이가 가장 짧은 것을 구하면 된다. 나같은 경우에는, front, tail(lo, hi)를 둘 다 0으로 초기화 시켜놓고 front부터 tail까지에 속하는 모든 원소의 합을 통해서 조건을 만들었다. 반복문은 front > numCnt >> minSum; int input; for (int i = 1; i > input; numVec.push_back(input); } int front = 0; int tail = 0; int curSum = numVec[0]; while (front = minSum) { ans = min(ans, tai..

[C++] 백준 2230번 수 고르기

투 포인터 문제. 투 포인터 문제를 오랜만에 풀었는데 틀렸다. 틀린 이유 위주로 정리하겠다. 문제 풀이 수열의 길이는 최대 100,000이다. 만일 한 index마다 끝까지 탐사하게 될 경우 시간 복잡도가 100,000 x 100,000이 되므로 10,000,000,000번의 연산을 하게된다. 이는 시간 초과가 발생할 것이다. 따라서 다른 방법을 생각했는데, 투 포인터 방법이 생각났다. 투 포인터는 한 줄의 배열이 있을 때 두 개의 포인터를 두어서, 포인터를 front, tail (혹은 lo, hi)로 두어서 포인터만 이동시키면서 푸는 방식이다. 이 문제는 최소의 차이를 구해야 하므로 정렬 시킨 후 투 포인터로 탐색해서 풀면 된다. 주의할 점은 고르는 두 수가 같은 수일수도 있다. A[i]를 두 번 고르..

[C++] 백준 2003번 수들의 합 2

처음에 DP라고 생각하고 풀어서 맞췄다. 알고보니 투 포인터 문제였다. 투 포인터가 무엇인지 몰랐는데 이 문제가 대표적인 투 포인터 문제라고 한다. 투 포인터란? 1차원 배열에서 두 개의 포인터를 가지고 조작하면서 원하는 값을 얻는 알고리즘이다. 이 때 배열의 모든 원소는 자연수여야만 투 포인터 알고리즘이 가능하다. 문제 접근방식 처음 내 풀이는 DP로 풀었다. 시간 제한을 보아도 DP밖에 방법이 떠오르지 않았다. 동적 계획법 Bottom Up 방식을 사용해서 문제를 풀었다. 그리고 각 자리수가 증가할 때마다 해당 다음 번째 수에 있는 값을 더해 나간다고 생각하고 풀었다. 예시 입력을 예로들면, dp가 결과값을 담는 배열이고 num이 각 값을 담는 배열이라 할 때 N = 10, M = 5이고 원소가 1 ..