catalan number
-
Catalan NumberAlgorithm with C/ETC 2020. 9. 8. 23:47
1. 문제 1부터 n 까지의 정수가 차례로 스택에 push 된다. push 가 이루어지는 중간에, 또는 모든 숫자들이 push된 이 후에 언제든지 임의로 숫자들을 pop 할 수 있다. 이렇게 pop 된 숫자들을 차례로 나열한 수열을 catalan number 라 한다. 예를 들어, n이 4 라면 1,2,3,4 가 차례로 push 된다. 1,2,3,4 모두 push 된 뒤, 네 번 pop 하면 4,3,2,1 이라는 수열이 만들어 진다. 반면에 1,2 가 push 된 뒤, 두 번 pop을 하고, 나머지 3,4 가 push 된 뒤 또 두 번 pop을 하면 2,1,4,3 이라는 수열이 만들어 진다. 따라서, 앞서 말한 대로 4,3,2,1 과 2,1,4,3 은 둘 다 catalan number 이다. 하지만 ..