Min IT's Devlog

풀이 일자: 23.06.28 난이도: [Medium] 분류: [Shortest Path/ Bellman-Ford/ Dijkstra] 문제 내용 문제의 내용은 start부터 end까지 간다고 했을 때 가장 높은 weight를 가지고 있는 경로의 weight를 반환하는 문제이다. 문제 해결 흐름 1. 우선 하나의 노드에서 다른 노드로의 이동이기 때문에 BFS를 생각해보았다.(실패) class Solution: def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float: visited = list(); path = dict(); for i in range(len(edges..

풀이 일자: 23.05.25 ( 나중에 다시 풀어보기..) 난이도: [Medium] 분류: [DP, SlidingWindow, Math] 문제 내용 카드가 1부터 maxPts사이의 정수로 이루어져있고 Alice가 초기 점수 0점에서 시작하여 점수의 합이 k이상이 될 때까지 카드를 뽑는다고 한다. 카드 뽑기가 종료되었을 때 Alice의 점수가 n이하일 확률을 구하는 것이 문제이다. 문제 해결 흐름 1. 처음에 해당 문제를 봤을 때 DP라는 것을 바로 알 수 있다. → 점수의 합이 k이상이 될 때까지 뽑고 점수가 n이하일 확률이기 때문에 dp배열을 이용하여 점진적으로 확률을 계산하는 수밖에 없다. 여기까지밖에 생각하지 못했다. 다른 해결 방식 1. 처음 문제에서 제공한 알고리즘은 TLE가 발생하지만 간단한 ..