[프로그래머스] 올바른 괄호의 갯수 python

https://school.programmers.co.kr/learn/courses/30/lessons/12929

프로그래머스

 

이 문제 댕어려움..어이없음. 

AI 추천으로 푸는데,, 나 2레벨도 겨우하는데 4를 추천해주네;;;;; 

좀 더 개선했으면,, 푸는 시간, 시도 횟수 다 고려점 해줘랏!!

 

쨌든, 우선 이름 보고 만만하네, 괄호? easy하지 했다가,,ㅋㅋ

호되게 당하고 옴..

 

이걸 보고 카탈란 수를 떠올리라는데 어찌 떠올리누

카탈란 수란, 아래와 같은데

이거를 

 

• 올바른 괄호 문자열 개수
  • 주어진 n개의 괄호쌍으로 만들 수 있는 모든 올바른 괄호 문자열 개수
• BST(이진 탐색 트리)의 개수
  • n개의 노드로 만들 수 있는 서로 다른 이진 탐색 트리 개수
• 격자 경로 문제
  • 2n × 2n 격자에서 대각선 위로 올라가지 않는 경로의 개수
• 출입 경로 문제
  • 계단을 오르내리는 경우에서 특정 조건을 만족하는 경우의 수

문제들에 많이 쓴다니, 한번은 숙지해보자! 맨 밑에 구체적 예시도 적어둠

 

 

 

1. 재귀적으로 풀기(가장 효율 안좋음)

# C(0) = 1 C(1) = () 1 C(2) = C(0)(1) + C(1)(0) = 2
# C(3) = C(2)(0) + (1,1) + (0,2)
# 카탈란 수의 정의 = 0~n-1 까지 모든 수의 합 Ci*Cn-1-i
def solution(n):
    if n == 1 or n==0:
        return 1
        
    answer = 0
    for i in range(n):
        answer += solution(i) * solution(n-1-i)        
    
    return answer

 

 

 

2. DP로 풀기 (효율 좋음)

# C(0) = 1 C(1) = () 1 C(2) = C(0)(1) + C(1)(0) = 2
# C(3) = C(2)(0) + (1,1) + (0,2)
# 카탈란 수의 정의 = 0~n-1 까지 모든 수의 합 Ci*Cn-1-i
def solution(n):
    dp = [0] * (n+1)
    dp[0] = dp[1] = 1
    
    for i in range(2, n+1):
        for j in range(i):
            dp[i] += dp[j] * dp[i-1-j]
        
    
    return dp[n]

 

 

 

1️⃣ BST(이진 탐색 트리) 개수 문제

문제

길이가 n인 정렬된 배열 [1, 2, ..., n]을 사용하여 만들 수 있는 서로 다른 **이진 탐색 트리(BST)**의 개수를 구하시오.

예시 입력/출력

n가능한 BST 개수

1	1
2	2
3	5
4	14

예제 설명

• n=3일 때 만들 수 있는 이진 탐색 트리는 다음 5가지임.

 

 

---

2️⃣ 격자 경로 문제

문제

너는 n x n 크기의 격자에서 (0,0)에서 출발해 (n,n)까지 이동해야 한다.
단, 한 번 이동할 때마다 오른쪽(R) 또는 위(U)로만 이동할 수 있으며, 절대로 대각선 위로 올라가면 안 된다.
가능한 모든 이동 경로의 개수를 구하시오.

예시 입력/출력

n가능한 경로 개수

1	1
2	2
3	5
4	14

예제 설명

• n=3일 때 이동 가능한 경로는 다음과 같음.
  R R R U U U R R U R U U R R U U R U R R U U U R R U R U R U
  따라서 5가지 경로가 존재.

---

3️⃣ 출입 경로 문제

문제

한 마을에는 n명이 살고 있다.
모든 사람은 반드시 한 번 나가고 한 번 들어와야 하며,
아무도 나가기 전에 먼저 들어올 수 없다.
모든 사람이 나가고 들어오는 순서를 정하는 경우의 수를 구하시오.

예시 입력/출력

n가능한 출입 순서 개수

1	1
2	2
3	5
4	14

예제 설명

• n=3일 때 가능한 출입 경로 예시
  O O O I I I (순서: 나가고 -> 나가고 -> 나가고 -> 들어오고 -> 들어오고 -> 들어오고) O O I O I I O O I I O I O I O I O I O I O O I I
  여기서 O는 나가는 것(출구), I는 들어오는 것(입구)을 의미.
  즉, 5가지 방식으로 출입 가능.

---

4️⃣ 계단 오르내리기 문제

문제

한 사람이 2n개의 계단을 오르내려야 한다.
이 사람은 항상 1칸 올라가거나 1칸 내려가는 방식으로만 움직일 수 있다.
즉, 한 번 올라갔으면 언젠가는 내려와야 한다.
이 사람이 가능한 모든 계단 이동 경로의 개수를 구하시오.

예시 입력/출력

n가능한 이동 경로 개수

1	1
2	2
3	5
4	14

예제 설명

• n=3일 때 가능한 이동 방식:
  ↑ ↑ ↑ ↓ ↓ ↓ ↑ ↑ ↓ ↑ ↓ ↓ ↑ ↑ ↓ ↓ ↑ ↓ ↑ ↓ ↑ ↓ ↑ ↓ ↑ ↓ ↑ ↑ ↓ ↓
  총 5가지 방법으로 이동 가능.