Min IT's Devlog

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

풀이 일자: 23.05.22 난이도: [Medium] 분류: [Hash Table, Divide and Conquer, Sorting, Heap, Bucket Sort] 문제 내용 단순하게 숫자 배열이 주어졌을 때 상위 k개의 빈번하게 등장하는 수를 순서상관 없이 리턴하는 문제였다. Follow-up에서는 NLogN의 시간복잡도를 갖는 알고리즘으로 풀어보라고 했다. 문제 해결 흐름 1. 단순하게 생각해보면 dictionary 하나 만들어서 숫자 카운트하고 이를 value기준으로 sort해서 return하면 끝나겠다. class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: cnt = dict(); for i in range..

풀이 일자: 23.05.19 난이도: [Medium] 분류: [DFS, BFS, Union Find, Graph] 문제 내용 이번 문제는 undirected graph가 주어졌을 때 이 노드들을 A와 B그룹으로 나눌 수 있는지 여부를 리턴하는 문제로 각 A,B 내부의 노드끼리는 연결되어 있지 않아야 한다. A와 B는 연결되어 있어도 상관없다. 문제 해결 흐름 1. 처음에는 Graph문제이고 A와 B그룹으로 나눌 수 있기 때문에 Union-Find를 떠올렸다. → 가능은 하겠지만 좀더 쉬운 방법을 떠올리고자 했다 2. A그룹과 B그룹을 나누고 같은 그룹의 노드들이 서로 인접하면 안되기 때문에 노드를 색칠하는 문제로 생각해도 되겠다는 생각을 할 수 있다. → BFS를 이용하여 각 level별로 같은 색으로 ..