11강 과제 : 블루트포스 최적화

⊙ 블루트포스로 풀이한 코드의 문제점을 알고 최적화할 수 있다.
⊙ 코드 내에서 어떤 부분이 불필요한 연산인지 골라낼 수 있다.

코드스니펫

[기존 코드]

int solution2(int n)
{
	int answer = 0;
	for (int a = 1; a <= 100; a++)
	{
		for (int b = 1; b <= 100; b++)
		{
			for (int c = 1; c <= 100; c++)
			{
				if (a + b * b + c * c * c == n)
				{
					answer++;
				}
			}
		}
	}

	return answer;
}

[최적화 코드]

int solution2_modify(int n)
{
	int answer = 0;
	for (int a = 1; a <= n - 2; a++)
	{
		for (int b = 1; b*b < n-a; b++)
		{
			int remaining = n - a - b * b;
			if (remaining <= 0) break;

			int c = cbrt(remaining);
			if (c * c * c == remaining) answer++;
		}
	}

	return answer;
}

 

 

과제 내용

수업 시간 중 블루트포스로 풀이한 문제가 하나 있었는데 아래와 같다.

Q. 정수 n(1≤n≤100)이 주어질 때, 다음 식을 만족하는 (a, b, c)의 개수를 구하라. 단, a, b, c는 1이상 100 이하인 자연수로 가정하고 a, b, c가 중복될 수 있음.

a + b^2 + c^3 = n

 

이 문제를 풀기 위해 a, b, c를 전부 탐색하여 풀이하면 이를 블루트포스라고 한다. 나도 이 문제를 보자마자 정말 이렇게 풀어도 괜찮나 싶은 생각이 들 정도로 아주 간단한 코드가 생각났었다. 그 코드가 바로 아래의 코드이다.

int solution2(int n)
{
	int answer = 0;
	for (int a = 1; a <= 100; a++)
	{
		for (int b = 1; b <= 100; b++)
		{
			for (int c = 1; c <= 100; c++)
			{
				if (a + b * b + c * c * c == n)
				{
					answer++;
				}
			}
		}
	}

	return answer;
}

문제에서 a, b, c는 1~100인 자연수라고 지정해 주었기 때문에 그 정도면 전부 다 돌아도 괜찮지 않을까 생각이 들었다. 그래서 1~100까지 모든 경우의 수를 빼먹지 않고 탐색하여 정답을 구하였다.

 

하지만 n이 1~100이라는 착한 범위가 주어져서 그렇지 n이 10,000처럼 큰 수라면 문제가 발생한다. 블루트포스로 풀이한 코드의 시간복잡도는 O(N^3)이므로 10,000^3=12^12(1조)는 정말 엄청난 숫자이다. 이런 경우 블루트포스로 풀이할 수 없는 문제가 되는 것이다.

 

그렇다면 블루트포스로 풀이하지 않고 큰 수를 커버할 수 있는 코드는 무엇인지 수정해보자.

 

---

 

블루트포스 최적화

최적화를 위해서는 일단 불필요한 탐색을 줄여야 한다고 생각했다.

내가 생각한 불필요한 탐색은 이렇다.

 

반복문 하나 줄이기

현재는 반복문이 3겹으로 되어 있어 시간 복잡도가 O(N^3)이다. 하지만 가장 안쪽의 c를 결정하는 반복문은 없어도 되기 때문에 O(N^2)로 시간 복잡도를 줄일 수 있다.

 

반복문으로 c를 찾는 방법이 아닌 n과 반복문으로 결정된 a와 b를 이용해 c를 구하는 방법이다.

c는 정수인 n-a-b*b의 세제곱근이다. n-a-b*b의 세제곱근이 정수라는 것은 n-a-b*b=c*c*c라는 뜻이다.

for (int b = 1; b*b < n-a; b++)
{
	int remaining = n - a - b * b;
	if (remaining <= 0) break;

	int c = cbrt(remaining);
	if (c * c * c == remaining) answer++;
}

세 제곱근을 구하기 위해서 cbrt()라는 함수를 사용하는데 이 함수의 반환값은 정수가 아니라면 실제 세제곱근의 가장 가까운 double 값을 반환하게 되고 int인 c에 저장될 때 정수로 저장되면서 소수 부분이 버려져 다른 수가 되게 된다. 예를 들어 27의 경우 결과값 3이 나와 3*3*3하면 27이 그대로 나오지만 28의 경우 약 3.037이 나오기 때문에 c에 3이 저장되면서 c*c*c는 28이 아닌 27이 나오게 된다.
따라서 c*c*c=remaining일 경우에만 answer을 카운트해주면 된다.

 

n을 넘어가는 순간 그만보기

a, b, c를 결정하는 순간 모두 계산을 하다 n을 넘어가면 더이상 볼 필요가 없어진다.

for (int a = 1; a <= n - 2; a++)
{
	for (int b = 1; b*b < n-a; b++)
	{
		int remaining = n - a - b * b;
		if (remaining <= 0) break;

		int c = cbrt(remaining);
		if (c * c * c == remaining) answer++;
	}
}

a는 b와 c가 1일 경우 가장 커질 수 있을 것이라고 생각해서 n-2까지만 반복 하도록 하였다. 기존에는 n이 20이어도 a가 100까지 모두 돌았다면 이제는 n에 따라 반복횟수가 달라지며 a가 n을 넘어서까지 도는 일은 없을 것이다. a부터 n을 넘어버리면 b나 c가 들어갈 자리는 없을 테니까.

 

다음으로 b도 마찬가지로 a+b*b만으로 n을 넘어버린다면 더이상 보지 않도록 반복문의 조건을 조정해주었다. 반복의 조건을 b*b<n-a인 것으로 하여 b*b에 a를 더하더라도 c자리가 남아있을 때만 반복하도록 한다.

 

마지막으로 c는 n-a-b*b를 remaining에 저장하여 값을 확인해주는데 이미 c가 들어갈 자리가 없이 나머지가 0보다 작거나 같으면 반복을 종료하도록 하였다.

 

이렇게 a, b, c모두 n을 넘어가 볼 필요가 없는 부분은 반복을 돌지 않도록 하여 최적화하였다.

---

 

배운 내용 정리

• 블루트포스로 풀이한 코드의 경우 n의 크기가 크지 않을 때만 사용할 수 있다.
• 만약 n이 크다면 필요없는 연산을 덜어내 최적화 과정이 필요하다.