[Python/파이썬] 백준 1865번: 웜홀

문제 풀이 벨만 포드 알고리즘을 사용해서 풀면 된다. 단, 일반적인 벨만 포드 알고리즘이 아닌 "음의 간선 사이클"이 존재하는지 여부만 구하면 된다. 또한 "도로"는 양방향이고 "웜홀"은 단방향임을 주의해서 입력받아야 한다. https://www.youtube.com/watch?v=Ppimbaxm8d8&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=13 코드 from sys import stdin input = stdin.readline def bf(): for i in range(n): for j in range(len(edges)): cur, next, cost = edges[j] if dist[next] > dist[cur] + cost: dist[next] = ..

[Python/파이썬] 백준 5014번: 스타트링크

문제 풀이 전형적인 너비우선 탐색 문제, heap을 이용해 풀어보았다. 코드 from sys import stdin import heapq input = stdin.readline f, s, g, u, d = map(int, input().split()) visited = [False] * (f + 1) q = [(0, s)] visited[s] = True ans = "use the stairs" while q: cnt, now = heapq.heappop(q) if now == g: ans = cnt break if now - d > 0: if not visited[now - d]: visited[now - d] = True heapq.heappush(q, (cnt + 1, now - d)) if n..

[Python/파이썬] 백준 1238번: 파티

문제 풀이 다익스트라 알고리즘을 사용하면 된다. 단, 학생들이 마을로 돌아가는 경우도 구해야 하는데, 이때의 간선은 주어진 입력의 시작점과 끝점을 서로 바꾸면 된다. 코드 from sys import stdin import heapq input = stdin.readline n, m, x = map(int, input().split()) toX = [[] for _ in range(n + 1)] #집에서 파티 마을로 가는 최단 경로 toHome = [[] for _ in range(n + 1)] #파티 마을에서 집으로 가는 최단 경로 for _ in range(m): a, b, t = map(int, input().split()) toX[a].append((b, t)) toHome[b].append((a..

[Python/파이썬] 백준 14938번: 서강그라운드

문제 풀이 다익스트라 방법과 플로이드-와샬 방법이 있는데, 노드의 개수가 적어서 플로이드-와샬 방법으로 풀었다. 플로이드-와샬 알고리즘을 안다면 쉽게 풀 수 있는 문제이므로 풀이는 생략함. 코드 from sys import stdin input = stdin.readline n, m, r = map(int, input().split()) items = list(map(int, input().split())) graph = [[1e9] * (n + 1) for _ in range(n + 1)] for _ in range(r): a, b, l = map(int, input().split()) graph[a][b] = l graph[b][a] = l for i in range(n + 1): for j in r..

[Python/파이썬] 백준 11444번: 피보나치 수 6

문제 풀이 분할 정복을 이용한 거듭제곱이므로 피보나치 수를 제곱의 형태로 만들려고 노력했다. 노트에 끄적이다가 우연히 규칙 발견!! n % 2 == 0 인 경우 Fn = F(n//2+1) ** 2 - F(n//2-1) ** 2 n%2 == 1 인 경우 Fn = F(n//2+1) ** 2 + F(n//2) ** 2 메모제이션도 활용해야 시간 초과가 나지 않는다. 코드 dp = dict() def fibo(n): if dp.get(n) != None: return dp[n] if n == 0: return 0 if n == 1 or n == 2: return 1 if n % 2 == 0: dp[n // 2 + 1] = fibo(n // 2 + 1) % 1000000007 # 맨 처음에는 % 100000000..

[Python/파이썬] 백준 9251번: LCS

문제 풀이 ACAYKP의 A와 CAPCAK의 C, CA, CAP, CAPC, CAPCAK 부분 수열의 LCS를 구한 뒤 2차원 배열에 저장. (0, 0) : A, C의 LCS 값(0) 저장 / (1, 0) : A, CA 의 LCS 값(1) 저장 / (2, 0) : A, CAP 의 LCS 값(1) 저장 ACAYKP의 AC, CAPCAK의 C, CA, CAP, CAPC, CAPCAK 부분 수열의 LCS를 구한 뒤 2차원 배열에 저장. (0, 1) : AC, C 의 LCS 값(1) 저장 / (1, 1) : AC, CA 의 LCS 값(1) 저장 / (2, 1) : AC, CAP 의 LCS 값(1) 저장 위 과정을 반복 그림에서 빨간색 글자는 최장 부분 수열 검은색 글자는 최장 부분 수열의 길이 파란색 글자는 L..

[Python/파이썬] 백준 1654번: 랜선 자르기 [이진 탐색]

내 코드 def find(lans, n,h,m): high = h min = m mid = (high + min)//2 while min = n: min = mid + 1 elif sum < n: high = mid - 1 mid = (high + min)//2 return mid from sys import stdin k, n = map(int,stdin.readline().split()) lans = [] for i in range(k): lans.append(int(input())) high = max(lans) min = 1 mid1 = find(lans,n,high,min) print(mid1) 처음 작성한 코드 k,n = map(int,input().split()) lans = [] for i..

[Python/파이썬] 백준 1157번: 단어 공부

내가 쓴 코드 a = input().upper() s = list(set(a)) count = [] for i in range(len(s)): count.append(0) for j in range(len(a)): if(s[i] == a[j]): count[i]+=1 max = 0 for i in range(0, len(count)): if(count[max] 0) & (max != i): k = "?" print(k) 다른 사람이 쓴 코드 n = input() n = n.upper() alpa='ABCDEFGHIJ..