파이썬 11주차 - 간단한 자료구조 문제와 동적 계획법

1. 괄호 (9012)

 

출처 : https://www.acmicpc.net/problem/9012

9012번: 괄호

 

*stack 구현시 list 사용

input으로 받아진 문자열 s를 바로 list로 집어넣어준다.

그 다음, sum 변수를 두어 증가/감소 시켜주며 비교해나가면 된다.

 

 

2. 카드2 (2164)

 

출처 : https://www.acmicpc.net/problem/2164

2164번: 카드2

 

시간초과 코드

 

정답 코드

 

*python에서 queue 구현시 stack과 마찬가지로 list 사용

list를 사용해서 구현했더니 시간초과가 났다.

그래서 시간복잡도를 줄이기 위해 deque를 사용하였다.

python에서 deque를 사용하기 위해서는 from collections import deque 를 써줘야한다.

popleft()는 맨 왼쪽의 원소를 pop하는 함수이고, append()는 오른쪽에 원소를 추가해주는 함수이다.

 

3. 정수 삼각형 (1932)

 

출처 : https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

import sys
read = sys.stdin.readline

n = int(read())
cache = [list(map(int, read().split())) for _ in range(n)]

for i in range(1, n):
    for j in range(i+1):
        if j == 0:
            cache[i][j] += cache[i-1][0]
        elif j == (i):
            cache[i][j] += cache[i-1][-1]
        else:
            cache[i][j] += max(cache[i-1][j-1], cache[i-1][j])
print(max(cache[-1]))

 

4. LCS (9251)

 

출처 : https://www.acmicpc.net/problem/9251

9251번: LCS

 

import sys 
S1 = sys.stdin.readline().strip().upper() 
S2 = sys.stdin.readline().strip().upper() 
len1 = len(S1) 
len2 = len(S2) 
matrix = [[0] * (len2 + 1) for _ in range(len1 + 1)] 
for i in range(1, len1 + 1): 
	for j in range(1, len2 + 1): 
    	if S1[i - 1] == S2[j - 1]: 
        	matrix[i][j] = matrix[i - 1][j - 1] + 1 
        else: matrix[i][j] = max(matrix[i - 1][j], matrix[i][j - 1]) 
        
print(matrix[-1][-1])

출처: https://suri78.tistory.com/11 [공부노트]