320x100 PS84 [CLASS 4]백준 9251번 - LCS 9251번 : LCS 다른 방법이 딱히 떠오르지 않는다면 DP로 접근하는게 좋은 것 같다. 이 문제를 풀 때 두 단계가 있다고 하면, 먼저 이 문제가 DP로 풀린다는 것을 알기 전과 후로 나눌 수 있을 것 같다. 이전에도 이와 비슷한 문제를 푼 적이 있었는데, 그때는 연속된 수열만 취급하는 문제였기 때문에 좀더 풀기 쉬웠다. 그러나 이 문제는 연속되지 않아도(서로 떨어져 있어도) 취급하기 때문에 조금 더 어렵다. 내 코드: # dawitblog.tistory.com # 입력 s1 = input() s2 = input() l1 = len(s1) l2 = len(s2) # dp 테이블 dp = [[0]*(l2+1) for _ in range(l1+1)] for i in range(l1): for j in r.. 2021. 3. 22. [CLASS 4]백준 1916번 - 최소비용 구하기 1916번 : 최소비용 구하기 문제를 딱 봐도 다익스트라를 이용하여 푸는 문제인 것을 알 수 있다. 다익스트라 알고리즘은 한 점에서 시작해서 각각의 점까지 가는데 드는 최소비용(시간,돈,...)을 구하는데 쓰이기 때문이다. 내 코드: # dawitblog.tistory.com from sys import stdin input = stdin.readline import heapq l = int(input()) # 연결 정보를 저장할 리스트 nodes = [[] for _ in range(l+1)] # 연결 정보 저장 for _ in range(int(input())): n,m,c = map(int,input().split()) nodes[n].append((m,c)) start, end = map(int,.. 2021. 3. 21. [CLASS 4]백준 1753번 - 최단경로 1753번 : 최단경로 오랜만에 보는 다익스트라 문제이다. 기본적인 다익스트라를 구현할 수 있다면 해결할 수 있다. 다익스트라에서 시작점에서 가장 가까운 점을 선택할 때 우선순위 큐를 이용하면 효율적으로 선택할 수 있다. 우선순위 큐는 파이썬의 내장모듈 heapq를 사용하면 최소 힙을 바로 사용할 수 있어 편리하다. 내 코드: # dawitblog.tistory.com from sys import stdin import heapq input = stdin.readline # 입력 V, E = map(int,input().split()) nodes = [[] for _ in range(V+1)] # 시작점 start = int(input()) for _ in range(E): u,v,w = map(int,.. 2021. 3. 16. [CLASS 4]백준 16953번 - A → B 16953번 : A → B 이전에 이 문제와 비슷한 문제를 푼 적이 있었는데, 그 문제가 더 어려웠던 것 같다. 이 문제는 일단 수가 무조건 증가하기 떄문에 해당 수를 넘기면 그 수에 대해서는 검사하지 않아도 된다. 내 코드: # dawitblog.tistory.com from collections import deque a,b = map(int,input().split()) queue = deque([(a,0)]) while queue: temp,count = queue.popleft() n = temp * 2 m = temp * 10 + 1 if n == b or m == b: print(count+2) exit() if n < b: queue.append((n,count+1)) if m < b: q.. 2021. 3. 15. 이전 1 ··· 4 5 6 7 8 9 10 ··· 21 다음
