분할 정복(Divide and Conquer)

1629 곱셈(3/28)
a를 b번 곱하게 되면 O(N)의 시간이 거리게 되지만
a ^ b/2 * a ^ b/2 로 곱하게 된다면 시간은 O(2 * logN)의 시간이 걸린다

1) 자료형은 long long으로 한다
2) 지수 b가 0일 경우, 1일 경우, 짝수일 경우, 홀수 일 경우 나누어 푼다

 

2630 색종이 만들기(3/28)
4등분을 하므로 4분면을 재귀함수로 색이 같은 지 검사해준다
1) 색이 모두 같으면 그 색상의 count를 올려준다
2) 색이 다르면 그 부분를 4개 영역으로 나누어 재귀함수로 검사 해준다 
? return;

@https://sossoon.tistory.com/16

 

1992 쿼드 트리(3/28)

4등분을 하여 재귀함수를 호출한다

1) 색이 같으면 그 색을 출력한다
2) 색이 다르면 그 부분을 4등분으로 재귀호출하고 재귀호출하기 전 '(' 를 재귀호출 후 ')' 를 출력한다
3) 입력 값이 배열 형식으로 들어오지 않음을 주의한다
@ ' '(띄어쓰기)가 없이 입력이 들어오므로 string을 이용해 배열로 바꿔준다 

cin >> N;

	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < s.length(); j++)
			image[i][j] = s[j] - '0';
	}

 

1780 종이의 개수(3/29)
9등분을 하여 재귀함수를 호출한다

1) 숫자가 모두 같으면 그 숫자의 count를 올려준다
2) 숫자가 다르면 그 부분들을 9개 영역으로 나누어 재귀함수로 검사 해준다 -> 9개 재귀함수 필요

 

1074 Z(3/29)
https://donggoolosori.github.io/2020/09/22/boj-1074-Z/

 

2447 별 찍기 10(3/29)
https://cryptosalamander.tistory.com/38

 

2339 석판 자르기(3/30)

 

2104 부분배열 고르기

6549 히스토그램에서 가장 큰 직사각형