2022/11/07 - 분할정복

1. 분할정복

백준의 색종이 만들기와 같이 조건에 성립하면, 조건에 맞게 분할하여 풀이하는 문제에 일정한 패턴이 있었다. 문제를 한번이라도 풀어봤으면 간단하게 풀 수 있는 문제였지만, 안풀었을 때는 생각이 생각보다 많이 걸렸었던 문제라 정리를 하려고 한다.

const something=() =>{}
const isIt=() =>{}
const recur =(size,x,y)=>{
	for(let i=0;i<size;i++){
		for(let j=0;j<size;j++){
			something()
		}
	}
	if(!isIt()){
			recur(size/n, x,y)
			recur(size/n, x+size/n,y)
			//....
			recur(size/n, x+size*(n-1)/n, x+size*(n-1)/n)
	}
}

Arguments로 size와 x, y를 가진다. size는 지속적으로 작아지고, x는 분할한 위치 시작점을 정한다. 그리고 처음 위치부터 끝 위치까지 돌면서 조건(something)이 맞지 않으면, 그 범위 내에서 재귀 함수를 실행하는 것을 부분적으로 나눠서 사용한다.

2. split & to Number

string.split(" ").map(str=>+str)

이전에 이 방법으로 흔히 string을 number로 변환을 하였는데 생각보다 가독성이 안좋다고 생각을 했는데, 개선하는 방법이 다음과 같이 있었다.