올바른 괄호의 갯수

올바른 괄호의 갯수

문제 보기

레벨 1도 겨우겨우 풀고 있는데 무슨 객기로 레벨 4 문제에 도전했는지 지금도 잘 모르겠다. 결론적으로 풀긴 풀었는데 내가 푼 방법은 굉장히 무식한 방법이었고 풀고 나서 다른 사람의 풀이를 보고 엄청난 걸 발견해서 블로그에 옮겨적는다.

문제

문제 설명

올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환하는 함수 solution을 완성해 주세요.

입출력 예

n	result
2	2
3	5

입출력 예 설명

입출력 예 #1 2개의 괄호쌍으로 [ "(())", "()()" ]의 2가지를 만들 수 있습니다. 입출력 예 #2 3개의 괄호쌍으로 [ "((()))", "(()())", "(())()", "()(())", "()()()" ]의 5가지를 만들 수 있습니다.

나의 풀이 1 - 재귀호출 이용(실패)

괄호의 규칙성은 발견을 했다. 다음과 같았다. 예를 들어 괄호쌍이 3개인 문제를 푸는 함수를 p(3) 이라고 한다면 아래 네 가지 경우를 모두 더하면 된다.

1. (p(2))
2. p(2)+p(1)
3. p(1)+p(2)
4. p(1)+p(1)+p(1)

하지만 이 방법에는 문제가 있었다. p(4)를 전개해본 걸 보면 알 수 있는데, 각 경우의 수에 중복이 발생한다.

p(4)

(((()))) = ( [ "((()))", "(()())", "(())()", "()(())", "()()()" ] )
=
(((()))) ((()())) ((())()) (()(())) (()()()) = 5

() ((())) = () + [ "((()))", "(()())", "(())()", "()(())", "()()()" ]
=
()((())) ()(()()) ()(())() ()()(()) ()()()() = 5
                  ~~~~~~~~a         ~~~~~~~~b

(()) (()) = (()) + ["(())", "()()"] | ()() + ["(())","()()"]
=
(())(()) (())()() ()()(()) ()()()() = 4
                           ~~~~~~~~a

((())) () = [ "((()))", "(()())", "(())()", "()(())", "()()()" ] + ()
=
((()))() (()())() (())()() ()(())() ()()()() = 5
                           ~~~~~~~~a~~~~~~~~b

이 중복되는 것들의 규칙성을 도저히 발견할 수 없었다.

나의 풀이 2 - 괄호를 전부 만들어보기

그래서 다른 방법을 찾아보았다. 괄호를 실제로 만들어보는 것이다. 괄호 짝의 숫자가 기하급수적으로 폭증하는 성질이라면 이 해법은 실패할 것이었다. 하지만 시도해보는 수밖에 없었다.

const parens = new Set();

function finder(s, n, o, c) {
  if (o === n && c === n) {
    parens.add(s);
    return;
  }

  if (o > n || c > n) return;

  finder(s + "(", n, o + 1, c);
  if (c < o) {
    finder(s + ")", n, o, c + 1);
  }
}

function solution(n) {
  finder("", n, 0, 0);
  return parens.size;
}

아이디어는 이렇다.

1. 내 바로 뒤의 괄호는 열리거나 닫힌다.
2. 열린 괄호와 닫힌 괄호의 수는 정확히 n개로 같아야 한다 (open == close == n)
3. 열린 괄호나 닫힌 괄호 모두 n개를 초과할 수는 없다.
4. 내 앞의 열린 괄호 수가 내 앞의 닫힌 괄호 수보다 적을 때만 괄호를 닫을 수 있다.

이 중 2번이 종료조건으로, 해당 종료조건을 만족하는 괄호 문자열 s를 Set에 저장한다. Set은 중복을 허용하지 않는 저장소이므로 자연적으로 중복이 제거된다.

이제 모든 괄호쌍을 순회하고 나서 Set의 크기를 반환하면 된다.

이 해법은 테스트를 통과했다.

정석적 풀이 - 카탈란 수

문제를 해결하신 분 중에 “카탈란 수”를 언급하신 분이 있어서 Bing Chat에 물어보았다.

Bing chat 답변

카탈란 수는 조합론에서 이진 트리의 수나 괄호 구조의 수 등을 셀 때 등장하는 수열입니다. n번째 카탈란 수는 C_n으로 표기하며, 다음과 같은 공식으로 정의할 수 있습니다.

\[C_n = \\frac{1}{n+1}\\binom{2n}{n} = \\frac{(2n)!}{(n+1)!n!}\]

카탈란 수는 다양한 조합론적 문제에 적용될 수 있으며, 그 예시는 다음과 같습니다.

• n쌍의 괄호로 만들 수 있는 올바른 괄호 구조의 개수
• n+1개의 항에 괄호를 씌우는 모든 경우의 수
• n+2각형을 n개의 삼각형으로 나누는 방법의 수
• 길이가 2n인 모든 뒤크 단어의 개수
• n개의 자식을 가진 노드가 n개인 정 이진 트리의 개수

카탈란 수는 18세기에 몽골의 수학자 명안도가 최초로 발견하였으며, 유럽에서는 오일러와 카탈랑이 각각 재발견하였습니다¹².

출처: Bing과의 대화, 2023. 4. 29. (1) 카탈랑 수 - 나무위키. https://bing.com/search?q=%ec%b9%b4%ed%83%88%eb%9e%80+%ec%88%98. (2) 카탈랑 수 - 위키백과, 우리 모두의 백과사전. https://ko.wikipedia.org/wiki/%EC%B9%B4%ED%83%88%EB%9E%91_%EC%88%98. (3) [더플러스수학] 카탈란 수 - 일반항(2) :: 더플러스수학. https://plusthemath.tistory.com/444. (4) 카탈란 수(Catalan number) : 네이버 블로그. https://m.blog.naver.com/pyw0564/221523147108.

카탈란 수 공식은 다음과 같습니다.

\[C_n = \\frac{1}{n+1}\\binom{2n}{n} = \\frac{(2n)!}{(n+1)!n!}\]

이 공식을 자바스크립트 코드로 구현하려면, 다음과 같은 방법을 사용할 수 있습니다.

• 팩토리얼 함수를 정의합니다. 예를 들어, 다음과 같이 재귀적으로 구현할 수 있습니다.

function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

• 이항 계수 함수를 정의합니다. 예를 들어, 다음과 같이 팩토리얼 함수를 이용하여 구현할 수 있습니다.

function binomial(n, k) {
  return factorial(n) / (factorial(k) * factorial(n - k));
}

• 카탈란 수 함수를 정의합니다. 예를 들어, 다음과 같이 이항 계수 함수를 이용하여 구현할 수 있습니다.

function catalan(n) {
  return binomial(2 * n, n) / (n + 1);
}

• 카탈란 수 함수를 호출하여 원하는 결과를 얻습니다. 예를 들어, 다음과 같이 콘솔에 출력할 수 있습니다.

console.log(catalan(3)); // 5
console.log(catalan(4)); // 14
console.log(catalan(5)); // 42

출처: Bing과의 대화, 2023. 4. 29. (1) Program for nth Catalan Number - GeeksforGeeks. https://www.geeksforgeeks.org/program-nth-catalan-number/. (2) math.js | an extensive math library for JavaScript and Node.js. https://mathjs.org/docs/reference/functions/catalan.html. (3) Catalan number - Wikipedia. https://en.wikipedia.org/wiki/Catalan_number. (4) JavaScript || How To Calculate Nth Catalan Number Using Vanilla JavaScript – My …. https://www.programmingnotes.org/5873/javascript-how-to-calculate-nth-catalan-number/.

같은 내용을 ChatGPT한테 물어보니까 훨씬 간단한 해법을 제시해 주었다.

ChatGPT 답변

Q: Make a catalan number algorithm in javascript.

A:

Sure, here’s an algorithm to calculate the nth Catalan number in JavaScript:

function catalan(n) {
  if (n <= 1) {
    return 1;
  }

  let result = 0;

  for (let i = 0; i < n; i++) {
    result += catalan(i) * catalan(n - i - 1);
  }

  return result;
}

Here’s how to use the function:

console.log(catalan(0)); // Output: 1
console.log(catalan(1)); // Output: 1
console.log(catalan(2)); // Output: 2
console.log(catalan(3)); // Output: 5
console.log(catalan(4)); // Output: 14

The algorithm uses recursion to calculate the Catalan number. It uses a for loop to iterate over all possible left and right subtrees, and then multiplies the number of left and right subtrees to get the total number of binary search trees.

답변을 보니 트리 순회법에도 응용되는가보다.

아직 카탈란 수 알고리즘이 어떻게 유도됐는지는 모른다. 아마 Bing chat이 제시한 해법이 내가 공식을 유도하기엔 더 편할 것 같다.

번외: 메모이제이션

위의 알고리즘에서 catalan(n) 함수는 momoization이 가능하다.

const cache = new Map();
function catalan(n) {
  if (n <= 1) {
    return 1;
  }

  if (cache.has(n)) return cache.get(n);

  let result = 0;

  for (let i = 0; i < n; i++) {
    result += catalan(i) * catalan(n - i - 1);
  }

  cache.set(n, result);

  return result;
}

메모이제이션 로직은 함수 안에 넣어도 되고 함수의 wrapper에서 해도 된다. 보통은 wrapper를 사용하고 FP 라이브러리들은 LRU cache 기반의 memoize() 함수를 제공한다. 메모이제이션을 하면 시간복잡도가 한 단계 완화될 것이다.

역시 ChatGPT에게 물어보니, 답을 해 준다. 심지어 메모이제이션 버전 함수까지 만들어 준다.

Q: Calculate Big O for this algorithm. Also if I use memoization for catalan(n), calculate Big O again.

A:

The time complexity of the given algorithm to calculate the nth Catalan number is O(4^n/n^(3/2)), which is exponential.

The reason for this is that for every value of n, the algorithm recursively calculates the Catalan number by iterating over all possible left and right subtrees, which leads to a lot of redundant calculations.

However, if we use memoization, we can significantly reduce the number of redundant calculations and improve the time complexity. Here’s the modified algorithm that uses memoization:

function catalanMemo(n, memo = {}) {
  if (n <= 1) {
    return 1;
  }

  if (memo[n]) {
    return memo[n];
  }

  let result = 0;

  for (let i = 0; i < n; i++) {
    result += catalanMemo(i, memo) * catalanMemo(n - i - 1, memo);
  }

  memo[n] = result;

  return result;
}

This version of the algorithm uses an additional parameter memo to store previously calculated values of Catalan numbers. Before performing any calculations, it checks whether the result for the given n is already stored in the memo. If it is, the algorithm returns the stored result instead of recalculating it.

With memoization, the time complexity of the algorithm becomes O(n^2), which is much more efficient than the original algorithm without memoization. This is because each calculation is performed only once and stored in the memo, reducing the number of redundant calculations.

즉 O(4^n/n^(3/2)) 라는 지수함수에서 O(n^2) 라는 2차함수로 시간복잡도가 완화된다.