Min IT's Devlog

풀이 일자: 23.07.06 난이도: [Medium] 분류: [Binary Search, Sliding Window, Prefix Sum] 문제 내용 주어진 array에 대해서 target이 주어졌을 때 해당 target과 같거나 큰 합을 가지는 subarray의 최소 길이를 찾는 문제이다. 문제 해결 흐름 1. 연속적인 subarray의 합이 우선 중요하고 각각의 subarray를 관찰하는 것이 필요하기에 Sliding Window이 적합하다. → 이때 가장 중요한 것은 Sliding Window의 핵심 idea인 sum을 구하는 방식이다. 일반적으로 two pointer를 이용하고 sum을 구할 때에는 다시 계산하지 않도록 i가 증가할 때는 sum의 값에 이전의 값을 빼고 j가 증가할 때는 sum의 ..

풀이 일자: 23.07.03 난이도: [Easy] 분류: [Hash] 문제 내용 2개의 string이 주어지고 s에서 2 문자의 자리를 바꿨을 때 goal이 될 수 있는지 리턴하는 문제이다. 문제 해결 흐름 1. 일단 불가능한 경우과 가능한 경우가 있을텐데 불가능한 경우의 경우의 수가 훨씬 많을 것이다. → 크게 나누면 len이 다른 경우, len이 같은데 들어가 있는 문자 수가 다른 경우, 자리를 바꾸더라도 불가능한 문자인 경우 이렇게 나눌 수 있을 것이다. class Solution: def buddyStrings(self, s: str, goal: str) -> bool: sc = Counter(s); gc = Counter(goal); if sc != gc: # 크기가 다르거나 문자의 갯수가 다른..

풀이 일자: 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..