알고리즘 문제 풀이(프로그래머스 - 올바른 괄호의 갯수)

프로그래머스 LEVEL 4(올바른 괄호의 갯수)

• 사용 언어 : javascript

• 해결 날짜 : 2023-05-16

• 해결 방법 :

  • 카탈란 수, dp를 활용해 문제 해결
    • 1개의 괄호쌍으로 만들 수 있는 올바른 괄호는 ()
    • 2개의 괄호쌍으로 만들 수 있는 올바른 괄호는 ()(), (())
    • 이미 한 쌍의 괄호가 존재한다고 가정했을 때, 3개의 괄호쌍으로 만들 수 있는 올바른 괄호는
      • () 안에 2쌍의 괄호 * 밖에 0쌍의 괄호 (C2 * C0)
      • () 안에 1쌍의 괄호 * 밖에 1쌍의 괄호 (C1 * C1)
      • () 안에 0쌍의 괄호 * 밖에 2쌍의 괄호 (C0 * C2)
    • 이를 통해 dp[n] = dp[0] * dp[n - 1] + dp[1] * dp[n - 2] + … + dp[n - 1] * dp[0]의 점화식을 가진다는 것을 알 수 있음

• 회고 :

  • x

• 코드

  function solution(n) {
    const dp = Array.from({ length: n + 1 }, () => 0);
    dp[0] = dp[1] = 1;
  
    for (let i = 2; i <= n; i++) {
      for (let j = 0; j <= i - 1; j++) {
        dp[i] += dp[j] * dp[i - j - 1];
      }
    }
  
    return dp[n];
  }
  

• 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges