분할 정복

해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다.

분할 정복 알고리즘은 보통 재귀 함수를 통해 구현이 가능하다.
조건문을 통해 case를 나누고, 그 안에서 재귀 함수를 사용하는 방식이다.

출처: https://janghw.tistory.com/entry/알고리즘-Divide-and-Conquer-분할정복

색종이 만들기[Baekjoon - 2630]

문제

https://www.acmicpc.net/problem/2630

코드

const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
const n = +input[0];
const paper = input.slice(1).map(v => v.split(" ").map(vv => +vv));
let paper_count = [0, 0]
function cut(n, x, y) {
    let count = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            count += paper[x + i][y + j]
        }
    }
    if (count === n * n) {
        paper_count[1]++;
    } else if (count === 0) {
        paper_count[0]++;
    } else {
        n = n / 2;
        cut(n, x, y);
        cut(n, x + n, y);
        cut(n, x, y + n);
        cut(n, x + n, y + n);
    }
}
cut(n, 0, 0)
paper_count.map(cnt => console.log(cnt))

풀이

파란색 색종이는 '1', 하얀색 색종이는 '0'으로 표시되고 있다.
따라서 색종이가 한개만 쓰일 경우 2가지 case로 나눌 수 있다.

색종이가 한개만 쓰이는 경우

1. 흰 색종이만 사용
   모두 0을 가지고 있기 때문에 count===0
2. 파란 색종이만 사용
   모두 1을 가지고 있기 때문에 couont===색종이의 크기^2

그 외의 경우 (else)

색종이를 가로, 세로로 1/2씩 나눈다.
n=n/2
이후 4등분된 색종이를 재귀 함수를 통해 색종이를 구분하는 단계를 거친다.

행렬 곱셈[Baekjoon - 2740]

문제

https://www.acmicpc.net/problem/2740

코드

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

const input = [];
rl.on('line', (line) => {
    // 입력 관리
    input.push(line.split(' ').map((el) => parseInt(el)));
}).on('close', () => {
    // 구현
    const N = input[0][0];
    const M = input[N + 1][0];
    const K = input[N + 1][1];

    const A = [];
    const B = [];

    for (i = 1; i <= N; i++) {
        A.push(input[i]);
    }

    for (i = N + 2; i <= N + M + 1; i++) {
        B.push(input[i]);
    }

    for (let i = 0; i < N; i++) {
        let result = []
        for (let j = 0; j < K; j++) {
            let sum = []
            for (let k = 0; k < M; k++) {
                sum.push(A[i][k] * B[k][j])
            }
            result.push(sum.reduce((acc, cur) => acc + cur))
        }
        console.log(result.join(" "))
    }
    process.exit();
});

풀이

여기서 가장 중요한 핵심 포인트는 sum.push(A[i][k] * B[k][j])부분이다.
A와 B를 하나씩 원소별로 곱하면서 나온 결과를 순차적으로 출력해준다.