320x100 Blog189 [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. [CLASS 4]백준 11660번 - 구간 합 구하기 5 11660번 : 구간 합 구하기 5 연산을 딱 한번만 시킨다면 그냥 for문으로 돌아도 상관 없겠지만 연산 횟수 M이 많을 수 있기 때문에 시간을 단축하기 위해 DP로 짜야 한다. 그리고 이 문제는 좀 짜증나는게 dp테이블의 크기를 딱 n으로 만든다면 입력한 인덱스와 1차이가 나는 문제 때문에 머리가 아파진다. 그래서 dp테이블은 1 큰 크기로 만드는게 정신건강에 좋다. 내 코드: # dawitblog.tistory.com from sys import stdin input = stdin.readline n,m = map(int,input().split()) mat = [list(map(int,input().split())) for _ in range(n)] dp = [[0]*(n+1) for _ in r.. 2021. 3. 14. [CLASS 4]백준 5639번 - 이진 검색 트리 5639번 : 이진 검색 트리 트리를 그냥 주는게 아니라 전위 순회한 결괏값을 주기 때문에 처음에 나는 먼저 트리를 구현->후위 순회를 하는 코드를 작성했다. 내 코드(python 시간 초과): # dawitblog.tistory.com import sys sys.setrecursionlimit(20000) input = sys.stdin.readline # 노드 class Node: def __init__(self,val): self.val = val self.lchild = None self.rchild = None # 트리 class Tree: def __init__(self): self.root = None # 트리에 노드 추가 def add(self,val): if(self.root == Non.. 2021. 3. 12. 이전 1 ··· 12 13 14 15 16 17 18 ··· 48 다음
