C++_코딩테스트/분할정복(Divide and Conquer)2 [백준 1629번/C++] 분할 정복 곱셈 처음 이 문제를 봤을 때 분할 정복으로 나눌 방법을 찾지 못해서 DC함수를 만들고 반복문 안에서 DC함수를 불러왔다. DC함수 안에서는 계속 곱한 수의 나머지에 A를 곱하고 %C를 한.. 작은 수에서는 괜찮았는데 아무래도 A, B, C 모두 최대 21억이다보니 long long으로 받아도 안됐었다. 그래서 반복문은 포기, B를 계속 2로 나눠서 수를 낮추는 방법으로 했다. 여기서 계속 %C를 해주는 것을 모듈러 연산이라고 하는데, 모듈러 연산: 정수들 간의 산술 연산을 특정 모듈로 나눈 나머지를 구하는 연산 으로, 결과를 0부터 모듈 값까지 범위로 제한한다. 이를 통해 오버플로를 방지할 수 있다. 답 #include #include #include using namespace std; int DC(int.. 2024. 2. 4. [백준 1992번/C++] 분할 정복 쿼드 트리 -> 처음에는 size를 매개변수로 넘길 생각을 못하고 그냥 0, 0에서 +2씩 추가하면서 모든 트리를 탐색하려고 했는데, 그것은 분할 정복의 방법이 아니며 불필요한 탐색을 할 가능성이 있어 고민을 하다 인터넷에서 힌트를 얻었다. 1. 더 작은 배열로 쪼개질 때 괄호가 생성됨 -> 쪼개지지 않으면 괄호를 출력할 필요가 없으므로 진위 확인 후 시작점과 같지 않으면 괄호를 출력하게 함 2. 입력 시 위의 사진과 같이 한 줄의 string형으로 들어오기 때문에, 한 원소씩 바로 받을 수 없고 string으로 받은 후 그 string의 원소를 쿼드트리에 다시 집어넣어야 한다. 답 #include #include #include using namespace std; vector Quad(64, vector(64).. 2024. 2. 4. 이전 1 다음
