본문 바로가기
320x100

PS84

[CLASS 4]백준 1918번 - 후위 표기식 1918번 - 후위 표기식 단순하지만 머리어픈 그런 문제이다. 후위 표기식이 무엇인지 알고 있다면 설명은 그냥 읽지 않아도 된다. 그냥 중위 표기식을 후위 표기식으로 바꾸는 문제이다. 표기식 문제가 나오면 스택을 사용한다는 것은 알고 있어야 한다. 스택을 사용하여 풀 수 있으니 재귀로도 풀 수 있을 것이다. 만약 어떻게 구현해야 할지 전혀 모르는 상태에서 시작했는데 빠른 시간 내에 풀어냈다면 정말 머리 좋은 사람이라고 생각한다. 딱히 어떤 알고리즘을 사용하는 것은 아니고 괄호와 연산자의 우선순위를 이용해서 말 그대로 적절하게 전환하면 된다. 내 코드: # dawitblog.tistory.com/152 stack,ans = [],[] # 우선순위 정의 priority = { '*':0, '/':0, '+'.. 2021. 5. 6.
[CLASS 4]백준 1865번 - 웜홀 1865번 - 웜홀 벨만-포드 알고리즘을 처음 접해본 나에게는 힘든 문제였다. 음의 간선이 존재하는 문제 자체가 처음이었기에 많이 고민하다가 플로이드-와샬 알로리즘으로도 시도해보려 했으나 모종의 이유(?)로 실패하고 벨만-포드 알고리즘을 적용하여 풀었다. 내 코드: from sys import stdin input = stdin.readline INF = int(1e9) def bf(): for i in range(1,n+1): for now in range(1,n+1): for dest, cost in nodes[now]: if dist[dest] > dist[now] + cost: dist[dest] = dist[now] + cost if i == n: return True return False T.. 2021. 5. 5.
[CLASS 4]백준 1504번 - 특정한 최단 경로 1504번 - 특정한 최단 경로 다익스트라를 사용하는 문제이다. 그런데 경유지가 하나면 모르겠는데 2개여서 무조건 다익스트라를 여러번 사용해야 한다. 내 코드: # dawitblog.tistory.com/150 from heapq import heappop,heappush from sys import stdin input = stdin.readline INF = 1e9 n, m = map(int,input().split()) nodes = [[] for i in range(n+1)] for _ in range(m): a, b, d = map(int,input().split()) nodes[a].append((b,d)) nodes[b].append((a,d)) # 경유지 s1, s2 = map(int,in.. 2021. 5. 4.
[CLASS 4]백준 1043번 - 거짓말 1043번 - 거짓말 좀 헷갈릴 수 있는 문제이다. 실제로 나도 처음에 막 풀다가 시행착오를 많이 겪었다. 정답 비율이 낮은 것도 이정도면 맞겠지 라고 생각하고 제출한 사람들이 많아서 그런게 아닐까 싶다. 집합을 주로 사용해서 푸는 문제는 처음인거 같은데 파이썬의 교집합, 차집합 등이 특정 상황에서 아주 유용하게 쓸 수 있을 것 같다. # dawitblog.tistory.com/149 from sys import stdin from collections import deque input = stdin.readline n, m = map(int,input().split()) l = list(map(int,input().split())) if l[0]: s = set(l[1:]) else: print(m) .. 2021. 5. 1.

티스토리툴바