(전공복습) 데이터과학 4. 시각화
차례
백준(BOJ) 1099 알 수 없는 문장 파이썬(Python)
DP 문제.
처음엔 길이가 짧아서 완전탐색해도 되지 않을까 했지만, 그건 TLE이고, 겹치는 문제를 DP로 해결할 수 있다.
결국 주어진 문장의 i번째 인덱스에서 word를 대입했을 때의 결과는 항상 같으므로, 이 부분을 메모이제이션하면 된다.
조금 더 나아가면 i번째 인덱스에서 j번째 인덱스까지의 최적의 경우는 항상 같으므로 그 부분을 메모이제이션하면 더 빨리 풀 수 있다.
여기서는 그렇게 안 해도 풀릴 것 같아서 그냥 첫 번째 방법을 선택했다.
#!python
from sys import stdin
from functools import cache
input = stdin.readline
INF = float('inf')
exp = input().rstrip()
n = int(input())
# 큰 의미는 없지만 굳이 중복되는 단어를 남겨둘 필요 없으므로 set으로
words = set(input().rstrip() for _ in range(n))
m = len(exp)
# 문자열 a의 순서를 바꾸어 b를 만들 수 있는지의 여부
def is_same(a, b):
da = dict(zip(a, [0] * len(a)))
db = dict(zip(b, [0] * len(b)))
for i in a:
da[i] += 1
for i in b:
db[i] += 1
return da == db
# cache 데코레이터를 이용해서 메모이제이션
# solve(i, word)는 exp[i:]의 비용 중 word를 사용한 경우의 최소값
# 이때, is_same(exp[i:i+len(word)], word)임이 보장된다
@cache
def solve(i, word):
l = len(word)
cost = sum(exp[i+j] != word[j] for j in range(l))
i += l
# 문장이 끝났으면 그대로 비용 반환
if i == m:
return cost
# 아닌 경우 문장의 나머지 부분 비용의 최소값을 구한 뒤 더해서 반환
new_cost = INF
for word in words:
if i + len(word) > m or not is_same(word, exp[i:i+len(word)]):
continue
new_cost = min(cost + solve(i, word), new_cost)
return new_cost
# 각 단어로 시작하는 경우에 대해 비용의 최소값 반환
ans = INF
for word in words:
if len(word) > m or not is_same(word, exp[:len(word)]):
continue
ans = min(ans, solve(0, word))
# ans == INF라면 가능한 경우가 없으므로 -1 출력
print(ans if ans != INF else -1)
2024
맨 위로 이동 ↑2023
백준(BOJ) 2045 마방진 / 3192 매직 스퀘어 파이썬(Python)
문제 링크 문제 링크
세그먼트 트리
개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...
벨만-포드 알고리즘
개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...
다익스트라 알고리즘
개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...