인프런 커뮤니티 질문&답변

안녕하세요 kkim님 ㅎㅎ

		do{
			vector<int> v;
			for(int i = 0; i < 3; i++){
				if(scv[0] - atk[0] > 0 || scv[1] - atk[1] > 0 || scv[2] - atk[2] > 0){
					v.push_back(scv[i] - atk[i]);
				}else{
					cout << ret << '\n';
					// cout << scv[0] - atk[0] << " " << scv[1] - atk[1] << " " <<  scv[2] - atk[2] << '\n';
					return 0;
				}
			}
			v.push_back(ret);
			q.push(v);
		}while(next_permutation(&atk[0], &atk[0] + 3));

메모리 초과는 이부분에서 발생합니다.

중복된 정점 체크 X + 순열로 풀이 -> 계속된 vector<int> v의 생성 등으로 인해 메모리가 한정된 양보다 많이 사용하게 되는 것 같습니다.

순열로 하는 방법으로 풀이의 경우 이 문제의 경우 총 60 * 3 의 180의 상태를 가지고 N은 최대 20번이 필요하다고 대략적으로 계산해보면(실제로는 9, 3, 1 빼서 이것보다는 적습니다.)

kkim님의 코드는.. 6^20의 경우의 수 =3,656,158,440,062,976의 경우의 수를 갖게 됩니다.

매우 큰 숫자죠? ㅎㅎ

제가 처음 이 문제를 보고 어떻게 풀지 감은 잡았는데 그때 제 생각은 bfs가 한 level씩 진행되면 6의 제곱으로 경우의 수가 늘어날텐데 그런 경우에는 60 60 60이 인풋으로 들어왔을때 시간초과가 날 수도 있다고 생각했습니다

>> 6의 제곱은 맞지만 BFS의 특징은 뭐죠? 방문한 정점은 다시 방문하지 않는다라는 것입니다. 상태값의 최대값이 60 60 60 이면 최대값은 216000밖에 되지 않습니다. 그외의 정점은 방문하지 않으니까요. (다만 여기서 0을 포함하게 되므로 정확히는 61의 3제곱인 226981이 됩니다.)

예를 들어 x, y의 상태값의 범위가 0 ~ 2라고 한다면 이들의 모든 경우의 수는

0, 1, 2

0, 1, 2의 조합인

9가 되는 것을 생각하시면 됩니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다.
kkim360님, 메모리 초과와 시간 초과 문제에 대해 질문해주셨군요.

1. 메모리 초과가 발생하는 경우는 주로 다음과 같은 상황에서 발생합니다.

   • 사용하는 배열의 크기가 너무 크거나, 필요 이상으로 메모리를 많이 사용하는 경우
     
   • 재귀 호출이 깊어지면서 스택 메모리를 과도하게 사용하는 경우
     
   • 동적 할당한 메모리를 해제하지 않고, 누수가 발생하는 경우
     메모리 초과 문제의 원인을 해결하기 위해서는 먼저 코드 상에서 위와 같은 상황이 발생하지 않도록 검토해보시는 것이 좋습니다. 대용량 데이터 처리 시에는 메모리 사용량을 최적화하거나, 꼭 필요한 데이터만 메모리에 유지하는 식으로 접근할 필요가 있습니다.
     

2. BFS로 문제를 접근할 때 시간초과에 대한 걱정은 매우 유효합니다. BFS는 레벨 별로 진행되기 때문에, 경우의 수가 기하급수적으로 증가하는 문제에서는 시간 초과가 발생할 가능성이 큽니다. BFS로 문제를 접근할 때 시간초과를 방지하는 방법으로는:

   • 중복 계산을 방지하기 위한 방문 처리를 철저히 하는 것
     
   • 가능하다면 가지치기(Pruning)를 통해 탐색 공간을 줄이는 것
     
   • 더 효율적인 알고리즘을 고려하는 것
     문제의 특성과 입력 데이터의 크기를 고려하여 BFS의 사용이 적합한지 판단해야 하며, 경우에 따라서는 다른 알고리즘을 적용해야 할 수도 있습니다. 또한, 알고리즘의 시간 복잡도와 공간 복잡도를 미리 계산해보고, 예상되는 최악의 경우에도 요구사항을 만족하는지 확인하는 것이 중요합니다.
     

시간 초과와 메모리 초과 문제는 알고리즘 문제 해결에서 자주 마주치는 문제들입니다. 이러한 문제들을 해결하기 위해서는 다양한 예제와 문제를 풀어보면서 경험을 쌓는 것이 중요합니다. kkim360님께서는 문제를 해결하는 과정에서 점점 더 효율적인 방법을 찾아내실 수 있을 것입니다. 계속해서 도전해보시기를 바랍니다.