Min IT's Devlog

풀이 일자: 23.03.10 난이도: [Medium] 분류: [Linked List, Reservoir Sampling, Randomized, Math] 문제 내용 문제의 내용은 한 방향의 linkedList가 주어졌을 때 임의의 노드를 리턴하는데 linkedlist의 모든 노드는 모두 같은 선택될 확률을 가지고 있어야 한다. Follow up: Linked List가 극단적으로 크고 길이를 모르는 경우를 가정해보고 O(1)의 space complexity가 되도록 푸는 문제 문제 해결 흐름 1. 일단 Follow-up을 무시하고 풀어본다면.. → class 내부의 constructor에서는 linked-list를 끝까지 읽으면서 arr에 저장해놓고 파이썬 내의 내장함수인 random.choice를 사용..

풀이 일자: 23.03.09 난이도: [Medium] 분류: [Hash Table, Two Pointer] 문제 내용 LinkedList의 head가 주어졌을 때 cycle이 시작되는 노드를 리턴하고 cycle이 없으면 null을 리턴하는 문제이다. Follow-up으로 자료구조 이용하지 않고 풀기. 문제 해결 흐름 1. 우선 포인터를 하나만 사용한다면 cycle이 없는지는 확인이 가능한데 그거 외에는 가능한게 없다. → Two-pointer를 사용해야겠다. 2. Two-pointer을 사용하는데 cycle이 있음을 확인하려면 두 개의 포인터의 이동 속도가 달라야겠다. → 포인터 하나는 한 칸씩 움직이고 나머지 하나는 두 칸씩 움직인다. 3. 이거랑 관련된 알고리즘이 있다. → 플로이드-마샬 알고리즘으로..

풀이 일자: 23.03.08 난이도: [Medium] 분류: [Binary Search] 문제 내용 n개의 바나나 무더기가 존재하고 piles[i]의 의미는 i번째 무더기에 존재하는 바나나의 개수를 의미한다. 이를 지키는 가드가 h시간 후에 올 예정이며 이에 Koko는 시간당 k의 속도로 매 시간마다 하나의 무더기를 골라 바나나를 먹을 예정이다. 만약 선택한 무더기에 있는 바나나의 수가 k보다 적은 경우 해당 무더기에 남아있는 바나나만 먹게 된다. 이러한 와중에 Koko는 바나나를 최대한 천천히 먹되 Gaurd가 오기 전까지 모든 바나나를 먹으려고 할 때의 최소 k를 구하는 문제이다. piles = [3,6,7,11], h = 8 만약 k가 4라고 가정한다면, [1,2,2,3] 즉 8번만에 다 먹게 되며..