2 - S 질문 있습니다. - 인프런 | 커뮤니티 질문&답변

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

2-S

2 - S 질문 있습니다.

해결된 질문

작성

안녕하세요.

강의를 듣고 힌트를 얻어서 어찌저찌 백준에서역시 통과를 하게 되었습니다.

그런데, 이해가 안되는 부분이 하나 있어서 질문을 하고싶습니다.

제가 다이나믹 테이블의 선언을 처음에는 코드의 38번째 줄에서 하였습니다.

그 이유는 결국 시작을 어디에서 하던지 간에 다이나믹 테이블의 값은 똑같다고 생각해서이기 때문입니다.

하지만 다이나믹 테이블의 선언을 루프 외부, 38번째 줄을 하니 문제가 틀리고, 내부, 40번째 줄을 하니 테스트를 통과 했습니다.

그렇다는 말은 DFS 진입지점에 따라 다이나믹 테이블의 값이 변한다는 말인데, 하나밖에 없는 테스트 케이스로는 왜 변하는지 원인을 찾을 수 가 없습니다.

어떤 케이스, 어떤 반례에서 다이나믹 테이블을 루프 밖으로 꺼냈을때 DFS의 진입지점마다 다이나믹 테이블의 값이 변하게 되나요?

https://www.acmicpc.net/source/share/aa38ef94ed944749bfc167ca340deca4

1줄 요약: 다이나믹 테이블의 선언을 38번째 줄에 해도 돌아갈것 같은데 안돌아가고 40번째 줄에 하면 돌아가는데 이유를 모르겠음.

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 ㅎㅎ

반례는 다음과 같습니다.

12 13

2 1

3 2

4 3

5 4

1 5

6 5

7 6

8 7

9 8

5 9

10 9

11 10

12 11

DP위에만 선언 :

-1 -1 11 10 9 8 7 6 5 4 3 2 1

Segmentation fault

아래에 선언 :

-1 -1 11 10 9 8 7 6 5 4 3 2 1

-1 1 -1 11 10 9 7 6 5 4 3 2 1

-1 2 1 -1 11 10 7 6 5 4 3 2 1

-1 3 2 1 -1 11 7 6 5 4 3 2 1

-1 4 3 2 1 -1 7 6 5 4 3 2 1

-1 4 3 2 1 5 -1 11 10 9 3 2 1

-1 4 3 2 1 6 1 -1 11 10 3 2 1

-1 4 3 2 1 7 2 1 -1 11 3 2 1

-1 4 3 2 1 8 3 2 1 -1 3 2 1

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 1

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

1 2 3 4 5 6 7 8 9

참고로 디버깅 코드는 다음과 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<vector<int>> Tree;

int DFS(const Tree& tree, vector<int>& dpTable, vector<int>& visited, int startIndex) {
	int result = 0;
	visited[startIndex] = 1;
	if (tree[startIndex].empty()) {
		return 1;
	}

	for (const auto& elem : tree[startIndex]) {
		if (visited[elem] == 0) {
			if (dpTable[elem] == -1) {
				visited[elem] = 1;
				dpTable[elem] = DFS(tree, dpTable, visited, elem);
			}
			result += dpTable[elem];
		}
	}
	return result + 1;
}

int main(void) {
	int comAmount, testAmount;
	cin >> comAmount >> testAmount;
	Tree tree(comAmount + 1);
	for (int i = 0; i < testAmount; ++i) {
		int first;
		int second;
		cin >> first >> second;
		tree[second].push_back(first);
	}
	
	Tree results(comAmount + 1);
	//vector<int> dpTable(comAmount + 1, -1); 
	for (int i = 1; i <= comAmount; ++i) {
		vector<int> dpTable(comAmount + 1, -1);
		vector<int> visited(comAmount + 1, 0);
		results[DFS(tree, dpTable, visited, i)].push_back(i);
		for(int j : dpTable)cout << j << " ";
		cout << '\n';
	}

	vector<int> answer;
	for (int i = results.size() - 1; i >= 0; --i) {
		if (results[i].size()) {
			answer = results[i];
			break;
		}
	}

	std::sort(answer.begin(), answer.end());

	for (int elem : answer) {
		cout << elem << " ";
	}

	return 0;
}

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

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

감사합니다.

강사 큰돌 올림.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다. kimmistral님.

우선, 질문 주신 내용은 Dynamic Programming(DP)에서 테이블(또는 배열)의 초기화와 범위가 어떻게 최종 결과에 영향을 미치는지에 대한 문제입니다. 이 문제의 핵심은 다이나믹 테이블의 초기화와 상태의 재사용에 있습니다.

다이나믹 테이블 초기화 위치: 코드 38번째 줄과 40번째 줄의 차이가 결과에 영향을 미친다는 것은, 각 호출에 대해 사용되는 이전 상태(값)이 재사용되거나 새롭게 계산된다는 것을 나타냅니다. 즉, 루프 내부에서 테이블을 초기화하면 각 DFS 별도로 독립된 환경을 마련하여 새로운 상태로 계산됩니다. 반면에 외부에서 초기화하면 이전 상태가 잔존하며, 예상치 못한 값이 남아있어 올바른 결과를 주지 못할 수 있습니다.
모든 경우에 대한 캐시: 예를 들어 어떤 문제는 처음부터 끝까지 완전히 다른 상태에서 새롭게 DP 테이블을 구성해야 하지만, 부분적 재활용이 가능하다면 적절한 범위 내에서 DP를 재사용할 수 있습니다. 그러나 초기화를 잘못하거나 재사용 범위가 맞지 않으면, 잘못된 결과를 초래할 수 있습니다.

관련된 문제와 유사한 사례들을 통해 더 깊이 있는 이해를 도울 수 있는 링크를 제공드립니다:

7-H 문제 다른방식 풀이 질문 - 여기에서는 여러 테스트케이스의 처리와 DP 배열 초기화 문제를 어떻게 해결할 수 있는지에 대한 논의가 있습니다.

결론적으로, DP의 특성상 초기화와 상태 관리는 매우 중요한 요소이며, 문제에 따라 다르게 정의된 범위를 유지하거나 새롭게 초기화하는 방식이 잘 적용되어야 올바른 결과가 나옵니다. 이 점을 염두에 두고 다시 코드를 검토하시면 도움이 될 것 같습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

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

2 - S 질문 있습니다.