Notice
Recent Posts
Recent Comments
Link
«   2025/03   »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31
Tags
more
Archives
Today
Total
관리 메뉴

끄적끄적

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

코테준비/백준

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

alstj_성공 2021. 11. 15. 23:27

1. 괄호 (9012)

 

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

 

9012번: 괄호

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고

www.acmicpc.net

 

*stack 구현시 list 사용

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

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

 

 

2. 카드2 (2164)

 

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

 

2164번: 카드2

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가

www.acmicpc.net

 

시간초과 코드

 

정답 코드

 

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

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

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

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

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

 

3. 정수 삼각형 (1932)

 

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

 

1932번: 정수 삼각형

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

www.acmicpc.net

 

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

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

www.acmicpc.net

 

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 [공부노트]