[프로그래머스] LV.4 짝수 행 세기

KG·2021년 6월 25일
DPLv.4combination알고리즘프로그래머스
0

알고리즘

목록 보기
59/61
post-thumbnail

문제

모든 수가 0 또는 1로 이루어진 2차원 배열 a가 주어집니다. 다음 조건을 모두 만족하는 2차원 배열 b의 경우의 수를 (1e7 + 19)로 나눈 나머지를 return 하도록 solution 함수를 완성해주세요.

  • b의 모든 원소는 0 아니면 1입니다.
  • a의 행/열의 개수와 b의 행/열의 개수가 같습니다. (= a와 b의 크기가 같습니다.)
  • i = 1, 2, ..., (a의 열의 개수)에 대해서 a의 i번째 열과 b의 i번째 열에 들어 있는 1의 개수가 같습니다.
  • b의 각 행에 들어 있는 1의 개수가 짝수입니다. (0도 짝수입니다.)

제한

  • a의 행의 개수는 1 이상 300 이하입니다.
    • a의 각 행의 길이는 1 이상 300 이하로 모두 동일합니다.

입출력 예시

aresult
[[0,1,0],[1,1,1],[1,1,0],[0,1,1]]6
[[1,0,0],[1,0,0]]0
[[1,0,0,1,1],[0,0,0,0,0],[1,1,0,0,0],[0,0,0,0,1]]72

풀이

Lv.4에 랭크된 문제 중에서도 난이도가 비교적 상당히 높은 문제인 것 같다. 이를 반증하듯이 2021년 6월 25일자를 기준으로 약 100여명의 사람만이 해당 문제를 해결했다. 물론 월간 코드 챌린지 시즌 1에 기출된 문제이기에 Lv.4에서 등재된 지 오래 지나지 않은 문제이기에 접근성이 더 떨어졌을 순 있겠지만, 그럼에도 불구하고 상당한 난이도를 자랑한다. 하나씩 살펴보며 풀이 과정을 파헤쳐보자.

1) A배열 1의 개수

먼저 가장 간단하게 구할 수 있는 것부터 구하고 넘어가도록 하자. 문제 조건에 의하면 우리가 만들어야할 배열 B는 주어진 배열 A와 그 크기가 완전히 동일하다. 그리고 배열 B는 i번째 A열에 들어있는 1의 개수와 동일한 개수의 1을 가지며, 이때 각 행에 들어있는 1의 개수는 짝수를 유지해야 한다. 매우 까다로운 조건이 아닐 수 없는데, 조건의 핵심이 되는 부분은 1의 개수이다. 따라서 일단 배열 A 각 열(col)에 들어있는 1의 개수를 세어주도록 하자.

// A와 B는 서로 크기가 동일하므로 공통 row/col 값으로 접근
const row = a.length;
const col = a[0].length;

// 각 열에 들어있는 1의 개수를 저장할 배열
const numOfOne = new Array(col).fill(0);

for(let i = 0; i < row; i++) {
  for(let j = 0; j < col; j++) {
    if (a[i][j] === 1) {
      numOfOne[j]++;
    }
  }
}

2) 조합(Combination)과 파스칼의 법칙

또 하나 비교적 간단하게 구현할 수 있는 함수를 미리 구현해주도록 하자. 바로 경우의 수를 구하는 함수인데 우리는 조합의 경우를 구하는 함수가 필요하다. 자바스크립트로 조합을 구하는 법을 이전 포스트에서 살펴본 적 있다. 해당 포스트에서는 조합으로 구성 가능한 모든 경우의 수를 구하는 방법이었지만, 우리는 단순히 구성 가능한 개수만 알면 된다.

해당 방법을 통해 구성 원소의 개수를 체크해도 그 값을 구할 수 있겠지만, 주어진 배열 A의 최대 행의 개수가 300이기 때문에, 300Cr을 구하는 과정에서 r은 1부터 300까지 위치할 수 있기 때문에 너무 많은 계산을 요구하게 된다. 따라서 시간초과가 발생할 수 밖에 없다.

다행히 우리가 필요한 것은 단순히 경우의 수이다. 왜 개수가 필요한 지는 밑에서 조금 더 자세히 다루겠지만 살짝 언급하자면, 우리는 문제 조건에 의해 하나의 열에 존재하는 1의 개수를 가지고 몇 개의 행을 짝수개의 1을 가진 행으로 만들 수 있는지 계산할 필요가 있다. 이때 주어진 행의 개수 중에서 선택하는 조합의 경우의 수를 사용해야 하기 때문에 조합을 구하는 식이 필요하다.

조합을 효율적으로 구하기 위해 우리는 파스칼의 법칙을 적용할 수 있다. 파스칼에 법칙에 따르면 다음이 성립한다.

  • nCr = n-1Cr + n-1Cr-1

이 같은 공식이 성립하는 것은 알고리즘의 영역에서 다루는 것은 부적절하다고 생각하기에 패스하려 한다. (사실 수학을 못하기 때문에) 관련 공식을 증명하는 다른 포스트 글이 많으니 궁금하다면 그 쪽을 참고해 봄이 좋을 듯 하다.

파스칼의 법칙으로 조합의 경우의 수를 구하는 것이 더 빠른 이유는, 해당 법칙이 일종의 DP 알고리즘 처럼 동작하기 때문이다. nCr을 구하기 위해서 n-1과 r-1의 값에 접근하고 있음을 볼 수 있는데 이는 모두 이전에 구한 값이 되기 때문에 이미 구한 값을 활용하여 새로운 값을 구하는 DP 알고리즘의 매커니즘과 동일하다고 할 수 있다.

우리는 이 파스칼의 법칙을 통해 주어진 배열 A의 행(row)에 대해 모든 조합을 찾아줄 것이다. 즉 모든 행에 대해 조합의 경우의 수를 저장할 것이다. 가령 배열 A가 4개의 행을 가지고 있다면 다음과 같다.

  • 1행 : 1C1
  • 2행 : 2C1, 2C2
  • 3행 : 3C1, 3C2, 3C3
  • 4행 : 4C1, 4C2, 4C3, 4C4

이처럼 각 행에 대해 모든 조합을 구해주는 이유는 밑의 풀이에서 조금 더 자세히 살펴볼 것이다. 의문이 드는 사람들을 위해 간단히 설명하자면, 우리는 현재 열을 기준으로 1의 개수를 체크하고, 1의 개수에 따라 짝수개를 가지는 행, 그리고 홀수개를 가지는 행을 구분지어 계산을 진행할 것이다.

이때 1의 개수는 최소 1부터 행의 개수와 동일할 수 있고, 이 중에서 몇 개의 행을 선택해야 하는지는 이전 결과에 따라 계속 변동되는 값이기 때문에 모든 행에 대해 조합의 경우의 수를 구해주는 것이다.

이때 각 조합의 수를 2차원 배열 형태로 만들어주자. 이는 일종의 DP 배열이기도 하면서, 4C2의 값을 구하기 위해 해당 배열에 DP[4][2]로 접근할 수 있도록 만들어주기 위해서이다. 위에서 선보인 파스칼의 법칙 공식을 점화식 삼아 다음과 같이 구현할 수 있다. 이때 문제 조건에 의해 경우의 수는 항상 1e7 + 19로 나눈 너머지가 되어야 하는 것에 주의하자.

const MOD = 1e7 + 19;

// row+1 크기의 행과 열을 가진 2차원 배열 생성
// 초기값은 0으로 지정
// row+1은 점화식에서 row-1 값을 이용하기 때문에
// outOfIndexError를 피하기 위한 방법
const combis = new Array(row+1).fill().map(_ => new Array(row+1).fill(0));

// 0개 중에 0개를 택하는 방법으로 이 값을 1로 지정
// 점화식을 그대로 적용하기 위해 이 값을 1로 지정하는 것
combis[0][0] = 1;

// 1Cr 부터 시작
for (let i = 1; i <= row; i++) {
  // j는 nCr에서 r을 의미
  for (let j = 0; j <= i; j++) {
    // r이 0이라면 항상 1
    if (j === 0) combis[i][j] = 1;
    // n == r 이면 항상 1
    else if (i === j) combis[i][j] = 1;
    // 그 외의 경우 파스칼의 법칙 적용
    else combis[i][j] = (combis[i-1][j-1] + combis[i-1][j]) % MOD
  }
}

따라서 우리는 combis를 통해 원하는 조합의 수에 접근할 수 있다. 만약 4번째 행에서 2개를 고르는 조합의 경우의수는 combis[4][2]로 접근하는 것과 동일하다.

3) 짝수행과 홀수행

본격적으로 문제풀이에 들어가기 앞서 용어를 한 번 정립하고 넘어가도록 하자. 문제에서 요구하는 답은 배열 A와 동일한 크기를 가지며 이때 각 행에 들어있는 1의 개수가 모두 짝수이면서 두 배열의 열에 들어있는 1의 개수는 동일해야 한다. 따라서 다음 두 용어를 정립하도록 하자.

  • 짝수행 : 행에 존재하는 1의 개수가 짝수개인 경우
  • 홀수행 : 행에 존재하는 1의 개수가 홀수개인 경우

4) 열과 짝수행의 관계

문제 조건에 의하면 두 배열에 동일한 순서의 열에는 1의 개수가 똑같이 존재해야 한다. 이를 위해 우리는 위에서 numOfOne 배열을 구해주었다. 이때 우리는 첫 번째 열부터 차례대로 접근해보면 열과 짝수행이 가지는 상관관계를 파악할 수 있다. 문제에서 주어진 첫 번째 입출력 예시를 살펴보자. 다음과 같이 A 배열이 주어졌다. 여기서 1열만 살펴보도록 하자.

A1열2열3열
1행0
2행1
3행1
4행0

1열만 고려했을 때 우리는 4개 행에 대해 짝수행인지 홀수행인지 판단을 내릴 수 있다. 0이 있다면 이는 짝수행이고, 1이라면 홀수행이다. 왜냐하면 문제 조건에 의해 1이 존재하지 않는 경우도 짝수로 간주한다고 했기 때문이다. 따라서 지금의 상황에서는 2개의 짝수행이 존재한다.

우리는 이 정보를 가지고 A와 똑같은 크기를 가진 배열 B를 만들어야 한다. 이때 배열 B는 크기가 동일하기 때문에 1열에 있는 1의 개수만 동일하게 유지한 채 만들 수 있다. 즉 이는 4개의 행 중에서 1의 개수인 2개를 선택 하는 것과 동일한 조합이며 4C2로 나타낼 수 있다. 그리고 이는 우리가 위에서 구한 combis[4][2]로 접근할 수 있음을 의미한다. 즉 첫 번째 열만 고려했을때 만들 수 있는 짝수행은 총 6개가 됨을 알 수 있다.

그렇다면 두 번째 열은 어떨까? 두 번째 열은 첫 번째와는 달리 그 이전의 정보를 가져와서 짝수행의 개수를 계산해야 함을 알 수 있다. 우리는 이 같은 매커니즘을 보통 DP 알고리즘에서 많이 보았다. 이전에 구한 값을 활용하여 다음 값을 계산하는 것은 전형적인 DP 알고리즘이다. 따라서 해당 문제의 최종 풀이는 DP 알고리즘을 적용해 풀어보도록 하자.

5) DP 배열 선언 및 초기화

위에서 살펴본 매커니즘을 기반으로 해 먼저 DP 배열부터 정의해보자. 우리가 필요한 정보는 열에 대한 정보, 그리고 행의 개수에 따른 짝수행의 개수이다. 이들의 상관관계를 고려해 다음과 같이 DP 배열을 정의할 수 있다.

  • DP[i][j] = x : 첫 번째 열부터 i번째 열(col)까지 j개의 짝수행(row)을 가진 배열의 경우의 수

만들어진 배열이 짝수행을 만족하는지 아닌지를 검사하기 위한 기본 전제는 항상 첫 번째 열부터 차례로 계산되어야 한다는 점이다. 따라서 DP 배열에서 열은 항상 첫 번째 열을 기준으로 시작하는 것으로 정의할 수 있다.

이때 첫 번째 열부터 i까지 범위에 따라 여러 개의 짝수행이 나올 수 있다. 마지막 열까지 도달하지 않는다면 짝수행의 개수는 계속 계산 도중에 달라질 수 있기 때문이다. 하지만 문제 조건에 의해 짝수행은 항상 A 배열의 행의 개수와 동일해야 한다. 따라서 최종적으로 리턴해야할 값은 DP[col][row]가 됨을 알 수 있다. 해당 값이 만약 0이라면 이는 문제 조건을 만족하는 배열을 만들 수 없음을 의미한다.

앞에서도 살펴보았듯이 DP 배열의 가장 처음이 되는 값은 직접 계산해 줄 수 있다. 바로 0의 개수만큼의 짝수행을 가지고 있을 것이다. 해당값을 직접 계산해서 초기화 하면, 이후 DP 알고리즘을 적용할 때 이전 값을 가져와 이후 값을 계산할 수 있다. 따라서 다음과 같이 DP 배열을 선언하고 첫 번째 열에 대해 초기화해주자.

// col+1, row+1 크기로 선언하는 이유는
// 배열의 인덱스가 항상 0부터 시작하기 때문이다.
// 배열 인덱스와 1번째 열의 일치성을 위해 각각의 크기를 1씩 늘려 초기화한다
// 물론 이 부분을 고려하지 않고 직접 계산해도 상관없다
const DP = new Array(col+1).fill().map(_ => new Array(row+1).fill(0));

// DP[1]은 1번째 열부터 1번째 열까지 범위를 의미, 즉 첫 번째 열 그 자체이다.
// numOfOne은 0부터 col-1 범위로 인덱스0이 곧 1번째 열을 의미 (위 DP 배열처럼 인덱스와 차수를 일치시켜 풀어도 된다. 다만 반복문에서도 그 위치를 신경써주자)
// 전체 행의 개수 - 1의 개수 = 0의 개수 = 1열에서 짝수행의 개수
// 그리고 이는 곧 (전체행 C 0의 개수)로 combis를 통해 접근 가능
DP[1][row-numOfOne[0]] = combis[row][row-numOfOne[0]];

6) 점화식 및 DP 알고리즘 적용

그렇다면 DP 알고리즘을 적용하기 위한 점화식을 찾아보자. DP[i][j] 배열에서 기준이 되고 있는 것은 항상 짝수행이다. 즉 우리는 기존 짝수행의 개수를 통해 다음 열에서 만들어 질 짝수행을 계산할 수 있다.

n번째 열에 대해 짝수행을 구하고 있다고 가정해보자. 현재 우리가 구하고자 하는 값은 DP[n][rows]가 될 것 이다. 이때 rows의 범위는 항상 0부터 A 배열의 행의 개수까지가 될 것이다. 왜냐하면 짝수행의 개수가 한 개도 존재하지 않을 수 있기 때문이다. 그리고 현재 열에 존재하는 1의 개수는 numOfOne[n]으로 접근할 수 있을 것이다.

이때 n번째 열에서 n-1 번째 열에 있는 짝수행에 접근할 수 있다. 그리고 현재 열에 있는 1의 개수에 따라 새로운 짝수행과 홀수행이 만들어질 것이다. 현재 존재하는 1의 개수를 k개(= numOfOne[n])라고 했을때 k개의 1은 항상 기존 행에 추가되어야 한다. 이때 기존행이 짝수이냐 홀수이냐에 따라 다음과 같은 규칙이 발생한다.

  1. 기존 짝수행에 1이 추가되는 경우 ➡ 홀수행
  2. 기존 홀수행에 1이 추가되는 경우 ➡ 짝수행

우리가 구해야하는 것은 짝수행이 되는 경우이다. 따라서 이번 열에서 만들어지는 짝수행의 경우를 고려해야 한다. 따라서 2번의 규칙처럼 홀수행에 1을 추가함으로 짝수행을 만드는 경우로 점화식을 구성할 수 있을 것이다. 그런데 1번의 규칙을 거꾸로 생각해보자. 기존 짝수행에 1이 추가되어 홀수행이 된다는 것은 결국 기존 짝수행에 아무것도 추가하지 않는 경우 계속 짝수행을 유지한다는 것과도 같다. 여기서 아무것도 추가하지 않는 다는 것은 0이 추가된다는 것과 같다. 따라서 짝수행이 될 수 있는 과정을 다음과 같이 나타낼 수 있다.

  1. 현재 n번째 열에서 필요한 1의 개수는 총 numOfOne[n]개이다.
  2. 이 중에 k개의 1이 기존 짝수행에 추가된다고 가정해보자. 이는 문제의 기준을 짝수행으로 삼고 있기 때문이다.
  3. 이때 선택되지 못한 나머지 1(= numOfOne[n] - k)이 존재할 수 있다. 이 경우 홀수행에 1을 추가한다.
  4. 이때 선택받지 못한 짝수행은 그대로 짝수행을 유지한다.

그러나 우리는 줄곧 짝수행을 기준으로 삼아 짝수행만 취급했는데 어떻게 홀수행의 개수를 구할 수 있을까? 이는 매우 간단하다. 결국 만들어지는 B 배열 역시 기존 A 배열과 크기가 동일하기 때문에 두 배열의 행의 개수도 동일하다. 따라서 만약 총 row개의 행이 있다면 row - 짝수행이 곧 홀수행의 개수가 됨을 알 수 있다.

위에서 보인 4가지 과정을 압축하면 결국 다음과 같다.

  1. 기존의 짝수행 중에서 k개를 선택하는 경우의 수
  • 이는 곧 combis[rows][k]의 경우의 수와 같다.
  • rows는 짝수행의 개수이므로, 항상 0 ~ 전체 행의 개수 범위를 모두 탐색하며 구한다.
  • k의 범위는 0 ~ numOfOne[n] 사이에 있으므로 해당 범위를 모두 탐색하며 구한다.
  1. 기존 홀수행 중에서 k개의 1을 제외한 나머지 1을 선택하는 과정
  • 기존 홀수행의 개수는 전체 행의 개수 - 기본 짝수행 개수이다. 이를 oddRow라고 표현하자.
  • 따라서 기존 홀수행에서 나머지 1을 선택하는 경우의 수는 combis[oddRow][numOfOne[n]-k]로 구할 수 있다.
  • oddRow도 결국 행이므로 범위는 rows와 동일하다.

이를 종합해서 도출할 수 있는 점화식은 다음과 같다. 문제조건에 따라 MOD값을 사용해 모듈러 연산으로 값이 커지는 것을 방지해야 함을 항상 주의하자.

// curCol: 현재 탐색하고 있는 열, curRow: 현재 탐색하고 있는 행
// one: k개의 1

// 다음 열에서 만들어지는 짝수행의 개수
// 기존 짝수행에서 1의 선택을 받지 못한 경우 + 기존 홀수행에 추가되는 나머지 1의 개수
const next = (curRow - one) + (numOfOne[curCol] - one);

// 짝수행이 만들어 질 수 있는 경우의 수
// 기존 짝수행에서 k를 선택하는 경우의 수 x 홀수행에서 나머지 1을 선택하는 경우의 수
const cases = (combis[curRow][one] * combis[row-curRow][numOfOne[curCol]-one]) % MOD;

// 다음 열까지 짝수행의 개수 += (현재 열까지 짝수행의 개수 x 짝수행이 만들어질 수 있는 경우의 수)
// DP[curCol+1][next]에 해당하는 값이 여러번 등장할 수 있으므로 기존값과 함께 더해줌
DP[curCol+1][next] += (DP[curCol][curRow] * cases) % MOD;

점화식을 구했으니 직접 반복문을 돌며 curCol/curRow/one 등의 범위를 탐색하며 정답을 구해주도록 하자. 이때 우리는 모든 범위를 탐색하는데 굳이 해당 범위를 계산하지 않아도 되는 경우가 생길 수 있다. 만약 기존 짝수행의 값이 0이라면 해당 짝수행을 가지고 있는 배열이 없다는 의미가 되므로 이 경우엔 계산하지 않고 넘아가도 된다. 또한 기존 짝수행의 개수가 one 보다 작다면, 2개 중에 3개를 선택하는 것과 같은 모순이 발생하므로 역시 계산하지 않고 넘어갈 수 있다.

// DP 배열의 크기가 col+1 이므로 1부터 시작
for (let curCol = 1; curCol <= col; curCol++) {
  // curRow는 짝수행을 의미, 0개일 수 있으므로 0부터 시작
  for (let curRow = 0; curRow <= row; curRow++) {
    // 짝수행을 가진 배열이 존재하지 않는 경우 계산 X
    if (!DP[curCol][curRow]) continue;
    
    // one은 위에서 살펴본 k를 의미 (몇 개의 1을 선택할 지)
    for (let one = 0; one <= numOfOne[curCol]; one++) {
      const next = (curRow - one) + (numOfOne[curCol] - one);
      
      // 다음 짝수행의 크기가 전체 행의 개수를 넘어가거나
      // 현재 짝수행이 선택된 1의 개수보다 작은 경우 계산 X
      if(next > row || curRow < one) continue;
      
      const cases = (combis[curRow][one] * combis[row-curRow][numOfOne[curCol]-one]) % MOD;
      
      DP[curCol+1][next] += (DP[curCol][curRow] * cases) % MOD;
    }
  }
}

// 1번째 열부터 col까지 row개의 짝수행을 가지고 있는 배열의 경우의 수
return DP[col][row];

7) 전체코드

혼자서 짱구를 굴려서는 도저히 풀 수 없던 난이도의 문제였다. 다시 회고하며 문제 풀이를 작성하면서도 또 다시 이해가 가지 않는 부분이 있어 글을 적으면서도 애를 먹은 부분도 있다. 단순히 DP 알고리즘을 적용해야 겠다는 생각을 떠올리는 것을 뛰어넘어 어떤 규칙을 찾아내 구현할 수 있을지에 대한 깊은 사고력이 요구되는 문제라고 생각한다. 주석을 제외한 전체 코드는 다음과 같다.

const MOD = 1e7 + 19;

function solution (a) {
  const row = a.length;
  const col = a[0].length;
  
  const combis = new Array(row+1).fill().map(_ => new Array(row+1).fill(0));
  combis[0][0] = 1;
  
  for (let i = 1; i <= row; i++) {
    for(let j = 0; j <= i; j++) {
      if (j === 0) combis[i][j] = 1;
      else if (i === j) combis[i][j] = 1;
      else combis[i][j] = (combis[i-1][j-1] + combis[i-1][j]) % MOD;
    }
  }
  
  const numOfOne = new Array(col).fill(0);
  
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (a[i][j]) numOfOne[j]++;
    }
  }
  
  const DP = new Array(col+1).fill().map(_ => new Array(row+1).fill(0));
  DP[1][row-numOfOne[0]] = combis[row][row-numOfOne[0]];
  
  for (let curCol = 1; curCol <= col; curCol++) {
    for (let curRow = 0; curRow <= row; curRow++) {
      if (!DP[curCol][curRow]) continue;
      
      for (let one = 0; one <= numOfOne[curCol]; one++) {
        const next = (curRow - one) + (numOfOne[curCol] - one);
        
        if (next > row || curRow < one) continue;
        
        const cases = (combis[curRow][one] * combis[row-curRow][numOfOne[curCol]-one]) % MOD;
        
        DP[curCol+1][next] += (DP[curCol][curRow] * cases) % MOD;
      }
    }
  }
  
  return DP[col][row];
}

출처

  1. https://programmers.co.kr/learn/courses/30/lessons/68647
  2. https://yabmoons.tistory.com/583
profile
KG
개발잘하고싶다
이전 포스트

[프로그래머스] LV.4 사칙연산

다음 포스트

[프로그래머스] LV.4 지형 편집

0개의 댓글