알고리즘 연습하기

🎯 팰린드롬

상당히 어려운 부분이었다. 우선적으로 이야기하자면 팰린드롬은 어떤 문자가 뒤집어도 대칭이 유지되는 것을 의미한다. 예를들어 ‘A’, ‘AA’, ‘ABCBA’가 팰린드롬에 해당된다.

👉 관련 문제 확인하기 : BOJ - 팰린드롬?

이것을 구현하기 위해서는 2차원 DP배열을 활용해야 한다. 순서는 상관이 없지만 i 인덱스를 문자열의 시작점, j 인덱스를 문자열의 종점이라고 둔다면 DP[i][j]는 문자열의 i번째부터 j번째까지의 팰린드롬 유무를 확인하는 작업이라고 생각하면 편하다.

여기서 주의해야할 점은 문자의 길이가 1일 때, 문자의 길이가 2일 때, 그리고 이상일 때, 총 3가지로 분류해서 DP배열에 값을 넣는 작업을 해주면 된다.

문자의 길이가 1일 때: 팰린드롬이 무조건 가능하다.
문자의 길이가 2일 때: 두글자 모두 동일한 경우에만 팰린드롬이 가능하다.
문자의 길이가 3일 때: 첫글자, 마지막 글자가 같은 경우에, 그리고 그 두 글자를 제외한 안에 있는 문자가 팰린드롬이 가능한 경우에 가능하다.

위 작업의 코드는 아래와 같다.

const stringArr = input.split('');
let board = Array.from({ length: N + 1 }, () => Array(N + 1).fill(0));

// 문자의 길이가 1일 때
for (let i = 1; i <= N; i += 1) {
  board[i][i] = 1;
}

// 문자의 길이가 2일 때
for (let i = 1; i < N; i += 1) {
  if (stringArr[i] === stringArr[i + 1]) {
    board[i][i + 1] = 1;
  }
}

// 문자의 길이가 3이상일 때
for (let i = 3; i <= N; i += 1) {
  for (let j = 1; j <= N - i + 1; j += 1) {
    let k = j + i - 1;

    if (stringArr[j] === stringArr[k]) {
      if (board[j + 1][k - 1]) board[j][k] = 1;
    }
  }
}

🎯 팰린드롬의 분할

👉 문제 확인하기: BOJ - 팰린드롬 분할

이론적인 위 내용을 이해했다면 이 문제를 해결할 수 있다. 이 문제… 사실 정말 너무 어려웠다. 팰린드롬을 제작하는 것까지는 위 코드를 그대로 가져와서 사용해도 되었으나 문제는 그 다음부터였다. 팰린드롬으로 여러개가 분할될 수 있는데 그 중에서 팰린드롬으로 분할되었을 때의 총 개수가 가장 작은 것으로 나눠야 하는 문제였다.

이때는 새로운 1차원 배열인 dp가 필요하다. 우선적으로 이 배열은 문자의 개수만큼 칸이 나누어져있고 첫번째 배열 값만을 제외하고 모든 값은 Infinity로 저장이 된다. 이후에는 만약 board 2차원 배열의 값이 1인 경우 dp 배열의 값과 이전 인덱스의 값 +1한 값 중에서 작은 값을 선택해주면 된다. 이론적으로 설명하면 어려우니 코드로 살펴보자.

let dp = Array(N).fill(0);

for (let i = 1; i < N; i += 1) {
  for (let j = 1; j <= i; j += 1) {
    if (board[j][i]) dp[i] = Math.min(dp[i], dp[j - 1] + 1);
  }
}

🎯 팰린드롬
🎯 팰린드롬의 분할