14500 테트로미노 문제를 풀던중 한가지 문제를 마주하였다.
바로 배열의 초기화에대한것.
자바에서 초기화는 다음과 같다.
boolean[][] visited = new boolean[N][M];이 함수를 보고 여태 한 생각은 처음 메모리공간이 O(1)시간 만에 디폴드값으로 할당되는줄알았다. (부끄럽게도)
하지만 테트로미노를 풀던 중,
- 전역으로 정의된 visited
static boolean[][] visited;
visited = new boolean[N][M];
for (int i = 0; i < N; i++) { // 500
for (int j = 0; j < M; j++) { // 500
visited[i][j] = true;
dfs(i, j, 1, map[i][j]);
visited[i][j] = false;
}
}- 지역함수의 파라미터로 정의된 visited
for (int i = 0; i < N; i++) { // 500
for (int j = 0; j < M; j++) { // 500
boolean[][] visited = new boolean[N][M];
visited[i][j] = true;
dfs(i, j, 1, map[i][j], visited);
}
}
private static void dfs(int x, int y, int cnt, int sum, boolean[][] visited) {
if (cnt == 4){
max = Math.max(max, sum);
return;
}
for (int d = 0; d < 4; d++) { // 4
int nx = x + dx[d];
int ny = y + dy[d];
if (!isRange(nx, ny)) continue;
if (!visited[nx][ny]) {
visited[nx][ny] = true;
dfs(nx, ny, cnt + 1, sum + map[nx][ny], visited);
visited[nx][ny] = false;
}
}
}2번 코드에서 시간초과가 나는것을 마주했다.
그래서 두 차이점을 chatgpt로 알아본 결과..
네, 맞습니다.
boolean[][] visited = new boolean[N][M]을 선언하면 내부적으로 다음과 같은 초기화 작업이 이루어집니다:1. 초기화 동작
- Java에서 배열은 선언과 동시에 기본값으로 초기화됩니다.
boolean[][] visited = new boolean[N][M];의 경우:
visited는 2차원 배열이므로, 내부적으로N * M개의boolean값을 생성하고, 모두 기본값false로 초기화합니다.내부 동작:
- 메모리 공간 할당:
- O(N×M)의 메모리 공간이 할당됩니다.
- 초기화:
- 각 배열 요소를 기본값
false로 설정하며 O(N×M) 시간이 소요됩니다.
2. 왜 초기화가 필요한가?
Java는 안전한 초기값을 보장하기 위해 배열 선언 시 초기화를 자동으로 수행합니다.
이는:
- 선언된 변수에 알 수 없는 값(garbage value)가 남아있는 것을 방지합니다.
boolean은 기본값이false,int는0,Object는null등으로 초기화됩니다.
3. 초기화 비용의 영향
- 배열 크기가 클수록 초기화 작업에 소요되는 시간이 늘어납니다.
- 예를 들어, (N = 500), (M = 500)이라면 (250,000)번의 기본값 설정이 이루어집니다.
- 반복적으로 선언한다면 이 초기화 작업이 누적되어 성능에 영향을 미칠 수 있습니다.
4. 최적화 방법
- 전역 변수 사용:
visited[][]를 한 번 선언하여 모든 탐색에 재사용하면, 배열 초기화 작업을 반복적으로 수행할 필요가 없습니다.- 탐색마다
visited[x][y]값을true/false로 변경하면서 활용합니다.- 배열 초기화 최소화:
- 필요할 때만 특정 영역을 초기화하거나,
Arrays.fill()을 이용해 특정 행만 초기화합니다.
5. 결론
- 선언만으로도 O(N×M)번의 초기화 작업이 이루어지며, 이는 코드 실행 시간에 영향을 미칠 수 있습니다.
- 배열을 반복적으로 생성하기보다는 전역으로 선언해 재사용하거나, 필요에 따라 부분 초기화를 수행하면 효율성을 높일 수 있습니다.
결론적으로 초기화를 할때 배열의 크기만큼 작업이 이루어진다는것이다.
따라서 O(1)이 아닌 O(N * M)만큼의 실행시간이 걸린다. 알고리즘을 풀때는 전역변수를 주로 사용하는것이 이와같은 이유인것같다.
Software Developer