283. Move Zeroes 빠른 투 포인터 문제다. l, r 둘 중 하나의 이동 속도가 다른 하나보다 빠른 투 포인터다. 보통 r을 순차적으로 증가시키고, l은 조건에 따라 당겨오는 방식이다. 조건을 만족하는 최소 구간을 찾을 때 유용하다. #include #include #include using namespace std; class Solution { public: void moveZeroes(vector& nums) { for (int z = 0, i = 0; i < nums.size(); ++i) if (nums[i] != 0) swap(nums[z++], nums[i]); } };

2003. 수들의 합 2 전형적인 전진 투 포인터 문제다. l, r이 모두 0부터 시작하는 투 포인터다. 현재 값이 목표 값보다 크면 l을 하나씩 당겨주고, 작으면 r을 하나씩 늘려주는 방식이다. 조건을 만족하는 가장 빠른 구간을 찾거나, 조건을 만족하는 구간의 개수를 찾을 때 유용하다. l, r이 모두 n에 도달할 때까지 반복하고, 항상 l ≤ r이므로 r이 n에 도달한 이후에는 l만 증가시켜주는 로직이 들어가야 한다. #include #include using namespace std; int TwoPointers(vector& v, int M) { int answer = 0; size_t n = v.size(); int l = 0, r = 0, sum = v[0]; while (l < n || r ..

12891. DNA 비밀번호 구간의 길이가 정해져 있다면, 일단 슬라이딩 윈도우를 생각해 볼 필요가 있다. 문자 개수 조건을 확인할 때 별도의 맵을 사용해서 조건보다 큰지 확인할 수도 있지만, 조건 맵에서 하나씩 빼고 더하면서 0보다 큰 수가 있는지 확인해줘도 된다. #include #include #include using namespace std; int SlidingWindow(string& DNA, int P, unordered_map& umap) { auto check = [&umap]() { for (auto& pr : umap) if (0 < pr.second) return false; return true; }; int answer = 0; for (int i = 0; i < P; ++i)..

21921. 블로그 앞에서부터 차례대로 정해진 구간의 합을 구하는 전형적인 슬라이딩 윈도우 문제다. 구간의 길이가 가변적인 투 포인터와 달리, 구간의 길이가 고정적이다. #include #include #include using namespace std; pair SlidingWindow(vector& v, int w) { int window = 0; map mp; for (int i = 0; i < w; ++i) window += v[i]; ++mp[window]; for (int i = w; i < v.size(); ++i) { window += v[i] - v[i - w]; ++mp[window]; } return *mp.rbegin(); } int main(int argc, char* argv[]..

11441. 합 구하기 전형적인 DP를 이용한 누적 합이다. 이 문제에선 \n 대신 endl을 쓰면 시간 초과가 발생한다. #include #include using namespace std; int main(int argc, char* argv[]) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; vector v(N + 1, 0); for (int i = 1; i > v[i]; v[i] += v[i - 1]; } int M; cin >> M; while (M--) { int s, e; cin >> s >> e; cout

재귀로 조합을 만들 때 핵심은 시작점과 레벨이다. 시작점부터 for문을 돌며 현재 레벨에 하나씩 찍어보고, 다음 시작점과 레벨 + 1을 전달해 탐색을 계속한다. 또한 앞에서 뒷방향으로 진행하며 앞의 내용을 유지해야하므로, 탐색에서 같은 결과 배열을 사용한다. #include #include #include using namespace std; void rCombination(int start, int depth, vector& comb, vector& v) { if (comb.size()