안녕하세요! 이번 글에서는 “가장 큰 정사각형 찾기” 문제를 JavaScript로 해결하는 방법을 자세히 알아보겠습니다. 이 문제는 동적 프로그래밍(Dynamic Programming) 접근 방식을 활용하여 효율적으로 해결할 수 있습니다. 실제 기업의 코딩 테스트에서 자주 출제되는 유형이므로, 이 문제를 통해 동적 프로그래밍의 개념을 확고히 하고, 실전에서의 활용 방법에 대해 알아보도록 하겠습니다.
문제 설명
주어진 2차원 배열 matrix가 있을 때, ‘1’로 이루어진 가장 큰 정사각형의 변의 길이를 구하는 문제입니다. 예를 들어, 아래와 같은 입력 행렬이 주어진다면:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0위 행렬에서 가장 큰 정사각형의 변의 길이는 2입니다. 즉, ‘1’로 이루어진 최대 크기는 2×2입니다.
문제 해결 접근
이 문제는 여러 가지 방법으로 접근할 수 있지만, 동적 프로그래밍을 사용하는 것이 가장 효율적입니다. 동적 프로그래밍을 사용하면 이전에 계산한 값을 재사용하여 불필요한 계산을 줄일 수 있습니다. 다음은 이 문제를 해결하기 위한 단계별 접근 방법입니다.
1단계: 동적 프로그래밍 테이블 설정
먼저, 기존 행렬과 동일한 크기의 2차원 배열인 dp를 생성합니다. 이 배열은 각 위치에 ‘1’로 이루어진 정사각형의 최대 변의 길이를 저장할 것입니다.
2단계: 경계 조건 처리
행렬의 첫 번째 행과 첫 번째 열은 경계 조건으로 설정합니다. 이 경우, 해당 위치가 ‘1’이라면 최대 정사각형의 변 길이는 1입니다. 만약 ‘0’이라면 어디에도 정사각형이 존재하지 않으므로 0으로 설정합니다.
3단계: DP 배열 채우기
이후, 행렬을 순회하면서 각 위치의 값에 따라 DP 배열을 업데이트합니다. 현재 위치 matrix[i][j]가 ‘1’이라면, 해당 위치에서 정사각형의 변의 길이를 다음과 같이 구합니다:
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;여기서 Math.min() 함수는 위쪽, 왼쪽, 그리고 왼쪽 대각선에서 최소값을 구하는 함수입니다. 이 최소값은 정사각형을 만들기 위해 필요한 최소한의 길이를 나타냅니다.
4단계: 결과 처리
마지막으로, DP 배열에서 가장 큰 값을 찾으면 그 값이 정사각형의 변의 길이가 됩니다.
알고리즘 구현
이제 앞서 설명한 접근 방식을 바탕으로 실제 알고리즘을 JavaScript로 구현해보겠습니다.
function maximalSquare(matrix) {
if (matrix.length === 0) return 0;
const rows = matrix.length;
const cols = matrix[0].length;
const dp = Array.from({ length: rows }, () => Array(cols).fill(0));
let maxSide = 0;
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (matrix[i][j] === '1') {
if (i === 0 || j === 0) {
dp[i][j] = 1; // 첫 번째 열이나 행일 경우는 1
} else {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
}
maxSide = Math.max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide; // 정사각형의 넓이 반환
}성능 및 복잡도 분석
이 알고리즘의 시간 복잡도는 O(m*n)이며, 공간 복잡도는 O(m*n)입니다. 여기서 m은 행렬의 행 수, n은 열 수입니다. DP 배열을 사용하기 때문에 공간이 추가로 필요하지만, 이를 최적화하여 O(n)으로 줄일 수 있습니다.
최적화: 공간 복잡도 감소
경우에 따라 DP 배열의 공간 복잡도를 O(n)으로 줄일 수 있습니다. 이전 DP 배열을 저장하기 위해 두 개의 배열을 사용할 수 있으며, 현재 상태를 업데이트할 때는 이전 상태만 필요합니다.
function maximalSquare(matrix) {
if (matrix.length === 0) return 0;
const rows = matrix.length;
const cols = matrix[0].length;
let dp = Array(cols).fill(0);
let maxSide = 0, prev = 0;
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
let temp = dp[j]; // 이전 값을 저장
if (matrix[i][j] === '1') {
if (i === 0 || j === 0) {
dp[j] = 1;
} else {
dp[j] = Math.min(dp[j], dp[j-1], prev) + 1;
}
maxSide = Math.max(maxSide, dp[j]);
} else {
dp[j] = 0; // '0'일 경우 0 설정
}
prev = temp; // 이전 값을 업데이트
}
}
return maxSide * maxSide; // 정사각형의 넓이 반환
}마치며
오늘은 자바스크립트 코딩테스트에서 자주 등장하는 “가장 큰 정사각형 찾기” 문제를 동적 프로그래밍을 통해 해결하는 방법을 알아보았습니다. 이 문제는 동적 프로그래밍의 기본 개념을 이해하는 데 도움을 주며, 실전에서의 코드 작성 능력을 향상시키는 데 큰 도움이 될 것입니다. 다양한 문제를 풀어보며 알고리즘과 데이터 구조에 대한 이해도를 높이는 것도 잊지 마세요!
앞으로 더 많은 알고리즘 문제를 다룰 예정이니 많은 관심 부탁드립니다. 감사합니다!