알고리즘 풀이 · 초급

격자판 최대합 풀이: 행·열·대각선 합을 어떻게 비교할까요?

··설명 약 8분·작성: 해비·블로그 소개

읽기 전에 알아두면 좋아요

아래 개념이 익숙하면 본문을 바로 읽으세요. 낯선 개념만 링크에서 복습하면 됩니다.

개념과 예제는 실행하지 않아도 읽을 수 있습니다. 내 컴퓨터·터미널에서 직접 실행하는 과정은 선택 실습입니다.

과정 위치와 선택 복습 안내

과정 위치: 완전탐색과 격자 · 문제

과정 위치는 이 글이 속한 묶음입니다. 이 단계의 모든 개념을 먼저 읽을 필요는 없습니다. 위에 연결한 개념 중 낯선 내용만 복습하세요. 문제의 조건·상태·갱신 순서는 익숙한 언어로 설명하면 됩니다.

JavaScript로 문법·실행 복습하기 (선택)

개념 글의 코드는 JavaScript 예시입니다. 문제 화면에서는 JavaScript·Python·Java·C++·C# 중 익숙한 언어의 함수를 작성하세요. 본문의 Node.js 입출력 예시는 로컬 실행을 위한 별도 안내입니다.

격자판 최대합 문제에서 어떤 합들을 비교해야 하나요?

정사각형 격자의 행·열·두 대각선 중 합이 가장 큰 값을 구하는 문제입니다. 2차원 배열·인덱스·합계의 기본을 준비하고, 아래 입력·반환 계약을 확인해 직접 풀어보세요.

적용 조건·범위: 문제 자료: 「자바스크립트 알고리즘 문제풀이」 자료 중 「섹션 2. 1, 2차원 탐색.pdf」 6쪽의 ‘격자판 최대합’과 같은 섹션의 「6. 격자판 최대합.txt」를 기준으로 문제 조건·예제를 정리했습니다. 확인한 PDF·TXT에는 저자명과 공식 강의·온라인 채점 URL이 기재되어 있지 않아 특정 저자나 강의로 단정하지 않았습니다. 아래 해설과 Node.js 표준 입출력 코드는 해당 자료의 풀이를 바탕으로 정리·보완한 것입니다.

본문 근거: Node.js 공식 fs.readFileSync 문서 · Microsoft의 Get-Content 문서

문제·입출력·제약

N×N 격자판에서 행 N개, 열 N개, 두 대각선의 합을 구하고 그중 최댓값 하나를 출력합니다. 전체 격자의 합이나 임의의 부분 영역의 합을 구하는 문제는 아닙니다.

  • 입력: 첫 줄에 자연수 N, 이어지는 N줄에 각 행의 자연수 N개가 공백으로 주어집니다.
  • 출력: 행·열·두 대각선의 합 중 최댓값을 한 줄로 출력합니다.
  • 크기: 1 ≤ N ≤ 50
  • 칸의 값: 100 이하의 자연수

문제 자료: 「자바스크립트 알고리즘 문제풀이」 자료 중 「섹션 2. 1, 2차원 탐색.pdf」 6쪽의 ‘격자판 최대합’과 같은 섹션의 「6. 격자판 최대합.txt」를 기준으로 문제 조건·예제를 정리했습니다. 확인한 PDF·TXT에는 저자명과 공식 강의·온라인 채점 URL이 기재되어 있지 않아 특정 저자나 강의로 단정하지 않았습니다. 아래 해설과 Node.js 표준 입출력 코드는 해당 자료의 풀이를 바탕으로 정리·보완한 것입니다.

원본 예제 입력

5
10 13 10 12 15
12 39 30 23 11
11 25 50 53 15
19 27 29 37 27
19 13 30 13 19

원본 예제 출력

155

목차

코드를 보기 전에 다음 세 가지를 종이에 적어 보세요.

  1. 한 행의 합을 구할 때 고정되는 인덱스는 무엇인가요?
  2. 한 열의 합을 구할 때는 두 인덱스의 역할이 어떻게 달라지나요?
  3. 오른쪽 위에서 시작하는 대각선의 열 번호는 행이 1씩 증가할 때 어떻게 변하나요?

예제의 세 번째 행의 합을 먼저 구한 뒤, 두 대각선도 비교해야 답이 결정되는지 확인해 보세요.

직접 풀어보기

먼저 선택한 언어의 입력·반환 계약에 맞춰 작성해 보세요. 힌트 받기와 정답과 비교하기는 코드를 실행하지 않는 AI 분석입니다. 해답·해설은 아래에서 필요할 때 펼칠 수 있습니다.

0 / 6,000바이트

N과 N×N 자연수를 읽어 행·열·두 대각선 합의 최댓값을 십진 문자열로 반환합니다. 입력 예시 전체를 문자열 input으로 전달하고 출력 문자열을 반환합니다. solve(input)를 호출합니다. 표준 입력·출력 코드는 추가하지 않습니다. LF·CRLF·끝 줄바꿈 없음에 같은 결과를 반환합니다. Tab은 다음 항목으로 이동합니다. 입력 영역 오른쪽 아래를 끌어 높이를 조절할 수 있습니다.

비밀키·개인정보는 입력하지 마세요. 코드는 이 페이지에만 유지됩니다.

해답·해설 보기
JavaScript 해답
function solve(input) {
    const tokens = input.trim().split(/\s+/).map(Number);
    const n = tokens[0];
    const grid = Array.from({ length: n }, (_, row) => tokens.slice(1 + row * n, 1 + (row + 1) * n));
    let maxSum = 0;
    let mainDiagonal = 0;
    let antiDiagonal = 0;
    for (let i = 0; i < n; i++) {
        let rowSum = 0;
        let columnSum = 0;
        for (let j = 0; j < n; j++) {
            rowSum += grid[i][j];
            columnSum += grid[j][i];
        }
        maxSum = Math.max(maxSum, rowSum, columnSum);
        mainDiagonal += grid[i][i];
        antiDiagonal += grid[i][n - 1 - i];
    }
    return String(Math.max(maxSum, mainDiagonal, antiDiagonal));
}

N과 N×N 자연수를 읽어 행·열·두 대각선 합의 최댓값을 십진 문자열로 반환합니다. 입력 예시 전체를 문자열 input으로 전달하고 출력 문자열을 반환합니다. solve(input)를 호출합니다. 표준 입력·출력 코드는 추가하지 않습니다. LF·CRLF·끝 줄바꿈 없음에 같은 결과를 반환합니다.

접근 과정

1. 행과 열을 같은 바깥 반복문에서 계산합니다

바깥 인덱스가 row일 때 grid[row][column]은 row번 행을 따라 움직입니다. 반대로 grid[column][row]는 row번 열을 위에서 아래로 확인합니다. 안쪽 반복문이 끝나면 행 합 하나와 열 합 하나가 완성됩니다.

행·열의 합 변수는 바깥 반복문을 시작할 때마다 0으로 초기화합니다. 이전 행의 합이 다음 행의 합에 섞이면 비교 대상 자체가 달라집니다. 계산을 마친 두 합만 현재 최댓값과 비교합니다.

2. 대각선 두 개를 별도로 누적합니다

왼쪽 위에서 오른쪽 아래로 가는 주대각선은 행과 열이 같은 grid[index][index]입니다. 오른쪽 위에서 왼쪽 아래로 가는 부대각선은 grid[index][size – index – 1]입니다. 마지막 열 번호가 size – 1이므로, 행 번호가 커질수록 열 번호를 줄입니다.

원본 풀이에서 유지한 점과 개선한 점

원본 TXT도 행·열을 함께 계산하고 대각선을 별도 반복문으로 처리합니다. 이 접근을 그대로 유지했습니다. 다만 원본의 let sum1=sum2=0은 sum2를 let으로 선언하지 않아 엄격 모드에서 오류가 날 수 있습니다. 최종 코드에서는 rowSum·columnSum과 두 대각선 합을 각각 선언하고, 변수 이름으로 역할을 드러냈습니다. 배열을 직접 넣던 실행부는 PDF 입력 형식에 맞는 표준 입력 처리로 바꿨습니다.

해설과 정답의 근거

각 행과 각 열의 모든 칸을 빠짐없이 더하면 후보 2N개를 얻습니다. 여기에 주대각선과 부대각선의 합을 더하면 문제에서 요구한 비교 대상이 모두 포함됩니다. 완성된 후보가 생길 때마다 최댓값을 갱신하므로 마지막 값이 정답입니다.

홀수 크기에서 가운데 칸은 두 대각선에 속합니다. 두 합은 서로 다른 후보이므로 각 대각선에 한 번씩 포함하는 것이 맞습니다. N=1에서도 행·열·두 대각선이 모두 같은 칸의 값을 가지며, 네 합을 더하는 것이 아니라 최댓값만 선택합니다.

Node.js가 설치된 환경에서 다음 전체 코드를 solution.cjs로, 위 원본 예제 입력을 input.txt로 저장하세요. 두 파일은 같은 폴더에 UTF-8로 저장하고, 터미널에서도 그 폴더를 여세요. 별도 패키지는 필요하지 않습니다.

실행 환경 확인

node --version

버전 번호가 출력되면 아래에서 사용하는 터미널에 맞는 명령 하나를 실행하세요. 예상 출력은 모두 155입니다.

macOS·Linux의 Bash 또는 zsh / Windows 명령 프롬프트

node solution.cjs < input.txt

Windows PowerShell

Get-Content -LiteralPath .\input.txt -Raw -Encoding UTF8 | node .\solution.cjs

PowerShell에서는 위의 파이프 방식으로 파일 내용을 전달합니다. Bash·명령 프롬프트용 입력 리디렉션 명령을 그대로 붙여 넣지 마세요. 파일을 찾지 못하면 현재 폴더와 파일 확장자를 확인하고, solution.cjs.txt처럼 저장되지 않았는지 점검하세요.

solution.cjs · 전체 코드

const fs = require("fs");

const input = fs.readFileSync(0, "utf8").trim().split(/\s+/).map(Number);
const size = input[0];
const grid = Array.from({ length: size }, (_, row) => {
  const start = 1 + row * size;
  return input.slice(start, start + size);
});

let maxSum = 0;

for (let row = 0; row < size; row += 1) {
  let rowSum = 0;
  let columnSum = 0;

  for (let column = 0; column < size; column += 1) {
    rowSum += grid[row][column];
    columnSum += grid[column][row];
  }

  maxSum = Math.max(maxSum, rowSum, columnSum);
}

let mainDiagonalSum = 0;
let antiDiagonalSum = 0;

for (let index = 0; index < size; index += 1) {
  mainDiagonalSum += grid[index][index];
  antiDiagonalSum += grid[index][size - index - 1];
}

maxSum = Math.max(maxSum, mainDiagonalSum, antiDiagonalSum);
console.log(maxSum);

/\s+/로 공백·탭·줄바꿈을 나누므로 LF와 CRLF 입력을 모두 처리합니다. 모든 칸이 자연수이므로 최댓값의 시작값은 0으로 둘 수 있습니다. 입력을 이차원 배열로 바꾼 뒤에는 같은 격자로 행·열·대각선을 계산합니다.

입력 API 근거: Node.js 공식 fs.readFileSync 문서는 파일 디스크립터와 문자 인코딩 인수를 지원합니다. PowerShell 파일 읽기는 Microsoft의 Get-Content 문서를 참고하세요. 문제 조건·예제는 위에 밝힌 자료를 따릅니다.

예제 추적

원본 예제의 합은 다음과 같습니다. 행과 열은 위에서 아래, 왼쪽에서 오른쪽 순서입니다.

  • 행 합: 60, 115, 154, 139, 94
  • 열 합: 71, 117, 149, 138, 87
  • 주대각선: 10 + 39 + 50 + 37 + 19 = 155
  • 부대각선: 15 + 23 + 50 + 27 + 19 = 134

행·열의 최대합은 154이고, 두 대각선까지 비교하면 155로 갱신됩니다. 따라서 원본 예상 출력은 155입니다.

경계값과 시간·공간 복잡도

N=1은 원본이 허용하는 최소 크기입니다. 이때 두 대각선 인덱스도 모두 0이며, 결과는 유일한 칸의 값입니다. 모든 값이 같거나 행·열·대각선의 최댓값이 동률이어도 합 하나만 출력하면 됩니다.

Node.js v24.19.0에서 원본 예제를 LF·CRLF로 각각 실행해 155를 확인했습니다. 최소 크기 N=1, 최대 크기 N=50, 동일값, 행·열·양대각선 최대 및 공백·탭 처리를 포함한 총 23개 검사가 모두 기대값과 일치했습니다. 경계값은 원본 예제와 구분한 구현 점검용 입력이며, 문제의 추가 조건이 아닙니다.

  • 시간 복잡도: 입력 변환과 행·열 누적이 O(N²), 대각선 누적이 O(N)이므로 전체 O(N²)입니다.
  • 공간 복잡도: 입력 토큰 배열과 격자 저장이 O(N²)입니다. 입력 저장을 제외한 합 계산용 변수는 O(1)입니다.
  • 최대 N=50에서 격자는 2,500칸이고, 행·열 누적의 안쪽 반복문은 2,500번 수행됩니다. 한 후보의 합은 최대 50×100=5,000으로 JavaScript Number의 정수 표현 범위 안에 있습니다.

추가 실행 확인: 2026년 10월 3일 Node.js v24.19.0·Linux Bash에서 게시된 전체 코드로 원본 예제 155, N=1·값 7인 입력의 7, N=50·모든 값 100인 입력의 5000을 확인했습니다. Windows 명령 프롬프트·PowerShell·macOS 실행은 이번 검토에서 직접 확인하지 않았습니다.

자가 확인

  • 행·열 누적 변수의 초기화가 왜 바깥 반복문 안에 있어야 하는지 설명할 수 있나요?
  • N=1에서 가운데 칸을 중복으로 더한 값이 답이 되지 않는 이유를 설명할 수 있나요?
  • 부대각선의 열 번호가 왜 size – index가 아닌 size – index – 1인지 확인했나요?

최댓값을 갱신하는 흐름을 더 연습하려면 보이는 학생 풀이를 참고할 수 있습니다. 이 글의 구현에는 이전 문제의 코드가 필요하지 않습니다.

글 소개·학습 준비·전체 목차

격자판 최대합은 각 행·각 열·두 대각선의 합을 따로 구한 뒤 가장 큰 합을 선택하면 됩니다. 이 글에서는 어떤 칸을 더해야 하는지 인덱스로 설명하고, 표준 입력을 받아 최대합을 출력하는 JavaScript 프로그램을 완성합니다. 배열의 인덱스와 이중 반복문을 알고 있으면 따라올 수 있습니다.

격자판에서 행·열·두 대각선의 합을 비교하는 격자판 최대합 표지

이 글이 도움이 되었나요?

조회 중

이어서 공부하기

체크포인트: 해설을 가리고 다시 풀고, 경계 입력을 하나 바꾸어 예상 결과와 실제 결과를 비교하세요. 같은 쌍을 두 번 세지 않는 이유와 모서리·대각선의 좌표를 설명하세요.

다음 추천 · 문제: 봉우리 풀이: 상하좌우 비교로 개수를 어떻게 셀까요?

같은 주제의 문제에 적용하며 방금 배운 개념을 확인합니다.

권장 순서는 학습 가이드와 같습니다. 다른 순서는 접힌 참고 목록에서 확인할 수 있습니다. 읽음 표시는 숙달이나 채점 결과가 아닙니다.

원래 과정 목록 순서 (선택)

읽음 기록

읽음 — / 전체 57개 · 필수 57개

읽음 기록 설정

읽음 기록은 이 브라우저에만 저장됩니다.

이 글을 쓴 해비

웹사이트를 제작·운영하고, 개인 서비스와 자동화·AI 도구를 만듭니다. 직접 만들며 배운 내용과 문제 해결 과정을 BlogFlow에 기록합니다.

새 글 받아보기

RSS 리더에서 BlogFlow의 새 글을 확인할 수 있습니다.

RSS 피드 구독하기

댓글 남기기