[Jacoste] 알고리즘 공부

tamagoyakii·2023년 1월 13일
0

Jacoste

목록 보기
6/9
post-thumbnail

<땅따먹기>는 가로가 4로 제한돼있는 이차원 배열에서 한 칸씩 밟고 내려갈 때 밟는 값의 합이 최대인 경우를 구하는 문제다. 처음에는 DFS로 접근하여 재귀로 문제를 풀었다.

function solution(land) {
    const rec = (row, col, sum) => {
        let ret = 0;
        if (row === land.length) return sum;
        for (let i = 0; i < 4; i++) {
            if (i === col) continue;
            ret = Math.max(ret, rec(row + 1, i, sum + land[row][i]));
        }
        return ret;
    }
    return rec(0, -1, 0);
}

코드가 실행은 됐지만 테스트를 돌렸을 때는 런타임 에러가 났다... 스택 오버플로우가 날 수 있기 때문에 다른 방법으로 접근해야 한다는 소리를 듣고 다시 풀어봤다.

동적 계획법(Dynamic Programming)

DP는 큰 문제를 작은 문제로 나누어 그 결과를 저장하면서 문제를 풀어나가는 방법이다.

const land = [[4, 3, 2, 1],
			[2, 2, 2, 1],
        	[6, 6, 6, 4],
        	[8, 7, 6, 5]]

위와 같은 land가 주어진다고 했을 때의 경우를 살펴보자. 배열을 내려가면서 구할 수 있는 최댓값을 구해야 하기 때문에, reduce() 메서드를 사용했다.

function solution(land) {
	return land.reduce((acc, cur) => cur.map((el, i) => el + Math.max(...acc)));
}

이 때 acc는 다음과 같이 증가할 것이다.

[4, 3, 2, 1]
[6, 6, 6, 5]
[12, 12, 12, 10]
[20, 19, 18, 17]

이때 curel에 더해지는 최댓값은 자신과 같은 인덱스에 있는 값이면 안 되기 때문에 filter()를 추가해 줬다.

function solution(land) {
    return Math.max(...land.reduce((acc, cur) => cur.map((el, i) => el + Math.max(...acc.filter((_, j) => j !== i)))));
}

사실 두 달 전쯤 풀었어야 하는 문제인데, 다들 푸는 방법을 생각해낼 수 없어서 포기하고 넘어갔었다. 두고 온 문제들을 풀어보자는 각오로 이번에 다시 시도해 봤는데, 나뿐만 아니라 모두들 생각보다 쉽게 풀었다. 우리는 확실히 성장하는 중이다!!!

0개의 댓글