분할정복3 [백준/2263/C] 트리의 순회 이 문제에 착안해야할 점은, 중위순회를 돈다면, L-------- M R------- (L은 M기준 왼쪽 트리, R은 M기준 오른쪽 트리)의 배열이 될 것이고,후위순회를 돈다면 L-------- R------ M이 될 것이다. 각 순회의 결과로 얻을 수 있는 부분은, 후위 순회는 지금 당장의 M이 무엇인지를 알아낼 수 있고, 중위 순회는 M의 위치를 탐색해서 L과 R트리의 크기를 알아낼 수 있다는 점이다. 그렇게 알아낸 결과로 왼쪽트리와 오른쪽트리에 대해서 재귀를 해주면 해결. #include int in[100000], post[100000]; int size;int search(int k, int left, int right) { for (int i = left; i 0) pref.. 2025. 6. 29. [백준/1030/C] 프랙탈 평면 이 문제에서 제시된 N과 s를 곧이곧대로 적용해서 프랙탈전체를 구현하기엔 메모리가 많이 부족할 것이다.((8^10)^2의 배열을 상상해보았는가.. 나는 못해보았다) 그래서 가장 중요한 힌트는 R1 R2 C1 C2의 범위인데 R2-R1, C2-C1이 문제에서 49보다 작은 수로 주어지기 때문에, 프랙탈 전체를 구현하기보다는 각 위치의 원소가 1인지 0인지만 판단하면 되는 문제이다. 자 그럼 판단 알고리즘은 어떻게 구현할 수 있을까? 우선 구현된 프랙탈 전체에 들어왔다고 생각해보자 그러면 만약에 전체 프랙탈의 크기를 size라고 할때 각 블록의 사이즈는 size/N일 것이고, 그 블록의 사이즈를 기준으로 한 원소의 위치 cx, cy는 원래의 x, y값에서 size/N을 나눈 값일 것이다. 그러면 그 cx c.. 2025. 6. 23. [백준/2630/C] 색종이 만들기 만약 색종이의 모든 부분이 같으면 그 색상의 카운트를 추가해주고 아니라면 분할정복으로 반복하도록 만드는 재귀알고리즘을 짜면된다.#include int paper[128][128];int white=0, blue=0;void divide(int x, int y, int N){ if (N==0) return; int par=0; for(int i=x; i 2025. 5. 27. 이전 1 다음 반응형