끄적끄적
파이썬 11주차 - 간단한 자료구조 문제와 동적 계획법 본문
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 [공부노트]
'코테준비 > 백준' 카테고리의 다른 글
백준 [2493] 탑 (0) | 2022.04.18 |
---|---|
백준 [2504] 괄호의 값 c++, python - stack (0) | 2022.04.18 |
파이썬 스터디 10주차 - 간단한 수학, 문자열, 정렬, 이분탐색 (0) | 2021.11.04 |
백준 [21736] 헌내기는 친구가 필요해 (0) | 2021.05.24 |
백준 [1004] 어린 왕자 (0) | 2021.05.24 |