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
11657. 타임머신 전형적인 벨만-포드 알고리즘 문제다. 음수 가중치가 있을 때, 한 점으로부터 다른 점들까지의 거리를 구한다. 음수 사이클을 판별할 때도 사용된다. 이 문제는 int를 사용할 경우 오버플로우가 발생해 출력 초과로 틀리게 되므로, long long 자료형을 사용해야 한다. #include #include #include #define UNREACHABLE LLONG_MAX using namespace std; struct Edge { int s; int e; int w; }; int main(int argc, char* argv[]) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M; cin >> N ..
1197. 최소 스패닝 트리 최소 신장 트리(MST)를 구하는 기본적인 문제이다. MST는 머리, 손, 발, 몸통이 따로 있다고 할 때, 말 그대로 키(신장)가 가장 작도록 모든 노드를 연결하는 트리다. N개의 노드가 있을 때, MST의 간선 개수는 항상 N - 1이 된다. 유니온-파인드를 필수적으로 활용해 크루스칼 알고리즘을 이용한다. 가중치의 오름차순으로 정렬된 간선 리스트를 만든다. 연결된 간선 개수가 N - 1이 될때까지 반복한다. 간선 리스트에서 간선을 하나씩 꺼내, 대표 노드가 같지 않을 때(싸이클이 생기지 않을 때)만 union으로 대표 노드끼리 연결한다. #include #include #include #include #include using namespace std; int findRe..