알고리즘19 [분할 정복] c++ 개념 및 1992 쿼드 트리 구현 목차 재귀함수를 하게되면 분할 정복을 만나게 된다.. 이참에 분할 정복을 정리하려고 한다. 분할 정복 정의 1. 분할 원래 문제를 분할하여 비슷한 유형의 더 작은 하위 문제로 분할이 가능할 때 까지 나눈다. 2. 정복 각 하위 문제를 재귀적으로 해결한다. 이때 기저 사례를 잘 만들어야 무한 루프에 빠지지 않는다. 3.결합 분할한 문제들을 통합하여 문제의 답을 얻는다. 장단점 분할 정복은 top-down 방식으로 재귀 호출의 장단점과 같다. 분할 정복 대표문제 1992 쿼드 트리 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번.. 2024. 4. 8. [코딩 테스트] C++ 코테용 문자열 팁 목차 c++을 하다보면 문자열이 까다롭게 느껴진다.. 그래서 정리해 보았다. split이 필요한 경우 #include #include #include using namespace std; vectorv; void split(string input, string delimiter) { long long int pos; string token; //string::npos 문자열을 찾지 못했을 경우 while ((pos = input.find(delimiter)) != string::npos) { token = input.substr(0, pos); // 잘라내기 v.push_back(token); // token 추가 input.erase(0, pos + delimiter.length()); //빼낸 것 지.. 2024. 3. 28. [알고리즘] 순열과 조합 c++ 구현 목차 c++로 순열과 조합을 어떻게 구현하는지에 대해 알아보자 stl로 구현한 순열 #include #include #include using namespace std; int main() { vector v; v.push_back(1); v.push_back(2); v.push_back(3); sort(v.begin(), v.end()); //순열을 만들때는 정렬을 해주어야함 do { for (int i : v) cout 2024. 3. 24. [투 포인터] c++구현 및 백준 2003 예제 설명 목차 투 포인터 알고리즘 정의 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 정렬되어있는 두 리스트의 합집합에도 사용됨. 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 합니다. 대표 예제 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 투 포인터 알고리즘 설명 크게 4가지 절차를 알면됩니다. 목표값보다 작으면 종착점을 증가시킨다. 목표값보다 .. 2024. 2. 28. 이전 1 2 3 4 5 다음 728x90
