최근 추가 240605

: 분할 정복이고, 재귀를 통해 접근하는 것은 맞았지만,
놓친 부분이 있다.

• 처음 들어가자마자 4분할로 나눠가면서 하기보다는
  모든 원소가 1이라고 한다면, 굳이 4분할로 나눠서 진행할 필요가 없다.
  -> 오히려 4분할 진행하게 되면, 메모리부족 문제가 발생한다.

• 위의 설명에 유의하면서 코드 작성하면 된다.
  : 분할 정복하기 전에, 굳이 분할정복을 해야하는건가? 생각을 하고 진행하자.

이렇게 접근??

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>

#include <tuple>
#include <map>
#include <stack>

#include <queue>
vector<vector<string>> v;
string gogo(int _y , int _x , int _size)
{
	if (_size == 1)
	{
		//cout << v[_y][_x];
		return v[_y][_x];
	}

	cout << '(';
	string s1 = gogo(_y, _x, _size / 2);
	string s2 = gogo(_y, _x + _size / 2, _size / 2);
	string s3 = gogo(_y + _size / 2, _x, _size / 2);
	string s4 = gogo(_y + _size / 2,
		_x + _size / 2, _size / 2);

	//if(s1 == s2 == s3 == s4)
	//{
	//
	//}
	//else
	//{
	//	cout << s1 << s2 << s3 << s4;
	//}

	cout << ')';
	

}

int main()
{
	int n;
	cin >> n;

	v.resize(n, vector<string>(n));

	for (int i = 0; i < n; ++i)
	{
		string s;
		cin >> s;
		for (int j = 0; j < n; ++j)
		{
			v[i][j] = s[j];
		}
	}

	gogo(0, 0, n);

	// 4등분으로 잘게잘게 진행
	// 그러다가 범위차이가 1이 발생할 때 리턴 처리

	// 그런데 가장 작은 범위 처리 후에도 
	// 4등분 재귀 돌리는 함수 쪽에서도 
	// 비교를 해야 한다. 
	// 아래처럼 4개씩 받는 씩으로 가자. 
	// 하나라도 상하좌우 4쌍이 모두 동일해야 압축 가능.

	// string s1 = go()
	// string s2 = go()
	// string s3 = go()

	// 변경되는 인자의 정보는 시작되는 x,y 인덱스 
	// 사이즈??? 


}

최근 풀이

: 240314 : 일단 못풀었고,
강의 수강 후 다시 도전.
https://rightbellboy.tistory.com/142

재귀를 언제 사용할까?

1. 똑같은 로직을 가지고 있다.
2. 그러나 매개변수만 달라져야 할 경우.

go(4) -> go(3) -> go(2) -> go(1)

• 해당 문제의 경우, 전체 8x8 에서 4등분으로 나누자.
  그런데 또 4등분으로 나눈다. 또 또~~
  -> 그런데 달라지는 부분은 있다. 등분하면서 의 size가 축소되고 있다.
  -> 시작하는 인덱스와 끝나는 인덱스도 달라지고 있다.

• 그런데 4등분하는 로직은 모두 동일하기 때문에
  결론적으로 재귀를 통해 문제를 접근해야 겠다는 생각을 할 수 있어야 한다.

어떻게 풀 건데?

go() 함수 내부에서 4등분을 반복하는 것이기 때문에
go() -> go() 4번을 호출하자.
그런데 startIndex, endIndex , size 인데 endIndex의 경우는 startIndex 와 size 만으로 처리할 수 있다..
startIndex 는 여기서의 경우 x, y 좌표 두개를 사용해야 한다.

• 재귀함수는 기저사례? 가 필요한다. 더 이상 호출되지 않도록 조건 처리해야 함.

헷갈리는 게

• 초록색 부분을 보면, 0,0,0,0 이 나왔는데 여기서 바로 출력하는 것이 아니라,
  0,0,0,0 이 4개가 동일한지 확인을 또 해야 한다.
  이거를 어떻게 처리할 건가에 대해 생각해보자.

• 완료 소스 코드는 이건데 직접 하자.
  https://www.acmicpc.net/source/share/f833f244536f48fa960ea96f9b5a35fb

• 아래 내용은 보지 말자.

---

변경 231202

• 참고 자료.
  https://yabmoons.tistory.com/450

접근하기.

: 영역을 분할 하고, 정복하는 방식으로 생각하는 것이 직관적임.

• 시작 정점을 기준으로 해서 코드를 작성하면 이와 같음.

• 코드 표현
  dfs(int x ,int y , int size)
  {
  // 조선식은 일단 모름.

  dfs(x, y, size / 2); // 초록색 부분.
  dfs(x + size / 2, y, size / 2); // 빨간색 부분.
  dfs(x, y + size / 2, size / 2); // 주황색 부분.
  dfs(x + size / 2, y + size / 2, size / 2); // 파란색 부분.

}

조건식에 대해서

언제 분할해야 할까? 분할 안해도 됨? 을 생각하자.

: 왼상 , 우상 , 왼하, 우하 로 인접한 정점에 대해서 동일한 값이라면
동일한 값 한개로 나타내면 됨.

• 여기서는 8칸이 모두 동일한 값이기 때문에 0임.
  

• 여기서는 0011 인데..
  

• 여기서는 0000 이 아니라 동일한 값이 0이므로, 0으로 표현 할 수 있음.
  

• 즉, 사각형 사이즈를 넓혀 나갈때 모든 범위의 검사를 해야 함.

• 분할을 해서 16칸을 확인하자.
  : 모두 동일하네? -> 굳이 분할할 필요 없음.
  

• 분할을 했는데. 16칸의 값이 다르므로, 이 때는 분할 하자.
  

---

아래로 진행하면 메모리 초과 발생함. : 업데이트 됨.

관련 문제

• 1780번. 종이의 개수
  https://velog.io/@kwt0124/1780%EB%B2%88.-%EC%A2%85%EC%9D%B4%EC%9D%98-%EA%B0%9C%EC%88%98

😧분할 정복 어떻게 접근할 것인가?

• 1. 인자로 시작되는 인덱스 (2차원 이라면 , yx값)을 보내고,
• 2. 사이즈도 인자로 보내주자
• 1번과 2번을 통해 재귀 함수안에서 호출을 시도함.
• 3. 체크하는 함수를 만들자.
     : 보내주는 3개의 인자를 통해서 for문을 만들자.
• 4. 반드시 최종 처리하는 함수 다음에 반환을 해야함.

for(int i = y; i < y + size; ++i)
{
for(int j = x; j < s + size; ++j)
시작되는 값을 : x,y 사용하고, 끝나는 부분을 size로 돌리는 방식으로
접근 하자.

알고리즘 분류

: 분할 정복

풀이전략

: 주 관심사는 가장 작은 인접한 4개의 원소를 어떻게 할것이냐?!

• 해당 사각형의 면적에 해당하는 1,2,3,4사분면 사각형에 접근을 해야 함.
  1) 사각형을 쪼개가면서, 어떠한 순간에 4개의 원소를 탐색할지에 대한
  조건을 걸어야 함.
  2) 첫번째 사각형을 타겟으로 한다면 이때, 총 4개의 가장 작은 원소를
  탐색해야 하므로, for문을 어떻게 돌릴지를 결정해야 함.
  : 좌상단 끝점과 우하단 끝점을 이용해 진행했음
  

코드

#include <iostream>
using namespace std;
#include <vector>
#include <string>

//언제나 2의 제곱수 
string divide(vector<vector<string>>&v,  int sY, int sX, int range)
{
	if (range == 2)
	{
		string w = "";
		for (int i = sY; i < sY + range; ++i)
		{
			for (int j = sX; j < sX + range; ++j)
			{
				w += v[i][j];
			}
		}

		if(w[0] == '0' && w[1] == '0' 
			&& w[2] == '0' && w[3] == '0')
		{
			return "0";
		}
		else if (w[0] == '1' && w[1] == '1'
			&& w[2] == '1' && w[3] == '1')
		{
			return "1";
		}
		string w2 = "(" + w + ")";
		return w2;
	}
	string word = "";
	word += divide(v, sY, sX, range / 2);
	word += divide(v, sY, sX + range / 2 , range / 2);
	word += divide(v, sY + range / 2 , sX, range / 2);
	word += divide(v, sY + range / 2 ,
		sX + range / 2, range / 2);

	//word가 모두 0이거나 1일 경우
	if (word[0] == '0' && word[1] == '0' &&
		word[2] == '0' && word[3] == '0')
	{
		return "0";
	}
	else if (word[0] == '1' && word[1] == '1' &&
		word[2] == '1' && word[3] == '1')
	{
		return "1";
	}

	// 중복되지 않으면 괄호 작업을 해야 함. 
	string word2 = "(" + word + ")";
	return word2;
}


// 문제 이해를 못함...
int main()
{
	// 일단 항상 정사각형임.
	// 8 by 8

	// 범위를 왼쪽윗부분 ~ 오른쪽 아랫부분ㅇ 인덱스를 기준으로
	// 4칸씩 나뉘어서 진행하자. 
	// 00 ~ 77  -> 4 , 4 씩 분할.
	// 00 ~ 33 // 04 ~ 37 // 40 ~ 73 // 44 ~ 77

	// 1,2의 인덱스는 시작 인덱스값. 
	// 3번은 돌릴 범위
	//go(y, x, size / 2)
	//go(y , x + size / 2, size / 2)
	//go(y+ size / 2, x, size / 2)
	//go(y + size / 2, x + size / 2 , size / 2)

	
	int n;
	cin >> n;

	vector<vector<string>>v(n, vector<string>(n));
	for (int i = 0; i < n; ++i)
	{
		string s;
		cin >> s;
		for (int j = 0; j < n; ++j)
		{
			v[i][j] = s[j];
		}
	}
	// 출력용
	//for (int i = 0; i < n; ++i)
	//{
	//	for (int j = 0; j < n; ++j)
	//	{
	//		cout << v[i][j] << " ";
	//	}
	//	cout << endl;
	//}

	string res = divide(v, 0, 0, n);
	cout << res;
}