[DFS] 테트로미노 - 백준 14500번
풀이Permalink
1) DFS 로 풀 수 있는것들Permalink
-
상하좌우 인접한 블럭으로 이동하면서 최댓값을 구함
const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, -1, 1}; for(int i = 0; i < 4; i++){ int nx = x + dx[i]; int ny = y + dy[i]; }
-
주의) 방문한 블럭으로 다시 돌아갈 수 없음
if(prev_x == nx && prev_y == ny) { continue; }
2) DFS 로 못 푸는 것Permalink
void makeWOOShape(int x, int y, int answer) {
// 전제 : 맵의 범위를 넘어가지 않는 선에서
// 'ㅜ' 모양 만들기
// 'ㅏ' 모양 만들기
// 'ㅓ' 모양 만들기
// 'ㅗ' 모양 만들기
}
참고: https://velog.io/@christer10/알고리즘-백준-14500-테트로미노
실수 (시간 초과)Permalink
vector<vector<int>>&
와 같이 참조를 사용할 때와 복사본을 사용할 때의 성능 차이는 큰 영향을 미칠 수 있습니다. 이 차이는 주로 두 가지 이유로 발생합니다:
1. 메모리 사용과 복사 비용Permalink
- 참조 (vector<vector<int>>\&):
- 메모리 사용: 참조를 사용하면 원본 객체를 직접 참조하므로 추가적인 메모리를 사용하지 않습니다.
- 성능: 객체의 복사 없이 직접 접근하므로 메모리 복사와 관련된 비용이 없습니다. 이는 특히 큰 데이터 구조체에서 성능을 크게 향상시킬 수 있습니다.
- 복사본 (vector<vector<int>>):
- 메모리 사용: 복사본을 사용하면 원본 객체의 복사본이 생성되므로 메모리 사용이 증가합니다.
- 성능: 데이터 복사에 따른 추가 비용이 발생합니다. 특히 큰 데이터 구조체에서는 이 복사 비용이 상당할 수 있습니다.
2. 함수 호출 시 성능 차이Permalink
- 참조를 사용할 때:
- 시간 복잡도: 참조를 사용하면 함수 호출 시 데이터 복사 비용이 없으므로 함수의 실행 시간이 단축됩니다. 함수 내에서 데이터 변경이 필요할 경우, 원본 데이터가 직접 수정됩니다.
- 효율성: 대규모 데이터 처리에서 성능 향상을 제공합니다.
- 복사본을 사용할 때:
- 시간 복잡도: 함수 호출 시 객체의 복사본이 생성되므로, 객체가 클 경우 복사 비용이 시간 복잡도에 추가됩니다.
- 효율성: 데이터 구조체가 클수록 성능 저하가 커집니다.
예제와 성능 차이Permalink
간단한 예를 통해 성능 차이를 살펴보겠습니다:
#include <iostream>
#include <vector>
#include <chrono>
using namespace std;
// 참조를 사용하는 함수
void processReference(vector<vector<int>>& mat) {
for (int i = 0; i < mat.size(); ++i) {
for (int j = 0; j < mat[i].size(); ++j) {
mat[i][j] += 1;
}
}
}
// 복사본을 사용하는 함수
void processCopy(vector<vector<int>> mat) {
for (int i = 0; i < mat.size(); ++i) {
for (int j = 0; j < mat[i].size(); ++j) {
mat[i][j] += 1;
}
}
}
int main() {
int n = 1000;
int m = 1000;
vector<vector<int>> matrix(n, vector<int>(m, 0));
auto start = chrono::high_resolution_clock::now();
processReference(matrix);
auto end = chrono::high_resolution_clock::now();
cout << "Reference time: "
<< chrono::duration_cast<chrono::microseconds>(end - start).count()
<< " microseconds" << endl;
start = chrono::high_resolution_clock::now();
processCopy(matrix);
end = chrono::high_resolution_clock::now();
cout << "Copy time: "
<< chrono::duration_cast<chrono::microseconds>(end - start).count()
<< " microseconds" << endl;
return 0;
}
이 코드에서 processReference는 참조를 사용하고, processCopy는 복사본을 사용합니다. processReference가 더 빠르게 실행되는 것을 확인할 수 있을 것입니다.
결론Permalink
참조 (vector<vector<int>>\&)는 데이터 복사 비용이 없으므로 성능상 우수합니다.
복사본 (vector<vector<int>>)은 데이터 복사에 따른 성능 저하가 발생할 수 있습니다.
따라서, 성능을 고려할 때 대규모 데이터 처리에서는 참조를 사용하는 것이 일반적으로 더 효율적입니다.
코드Permalink
https://github.com/KimGyeongLock/CodingTest/blob/main/14500.cpp