Min IT's Devlog

풀이 일자: 23.02.21 난이도: [Medium] 분류: [Binary Search] 문제 내용 nums라는 배열 안에 여러 개의 숫자가 2번씩 나타나는 데 그 중 한번만 등장한 숫자를 리턴하는 문제이다. logN의 시간복잡도와 O(1)의 공간복잡도를 가져야 한다. 문제 해결 흐름 1. 시간복잡도와 공간복잡도 제약 사항의 의미를 먼저 파악하자. → logN의 시간복잡도는 이진탐색을 사용하라는 것이고 O(1)의 공간복잡도는 다른 자료구조를 사용하지 않고 변수 몇개만 사용하라는 의미이다. 2. 이진탐색으로 하는 건 확인했고 그럼 1개만 있는 수의 위치를 알아야 이진탐색을 할텐데 규칙을 찾아보자. → 예를 들어보자. nums = [1,1,2,3,3,4,4,8,8] 특징을 찾아보면 답이 되는 숫자 한 개를 ..

풀이 일자: 23.02.20 난이도: [Gold V] 분류: [DP, 0-1 Knapsack] 문제 내용 => 일반적인 Knapsack Problem 문제이다. 문제 해결 흐름 1. 무게당 가치를 각각 계산해서 Greedy하게 처리할 수 있지 않을까? → 만약 해당 문제가 fractional knapsack이었다면 가능하지만 0-1 Knapsack 즉, 물건을 쪼갤 수 없는 상태이기 때문에 Greedy알고리즘으로 처리할 수 없다. 주어진 예제를 보면 바로 확인이 가능한데. MaxWeight = 7이고 (6,13), (4,8), (3,6), (5,12)의 (weight, value)쌍이 존재한다면.. 각 무게당 value 계산시 13/6 = 2.1 8/4 = 2 6/3 = 2 12/5 = 2.4 으로 Gr..

풀이 일자: 23.02.20 난이도: [Easy] 분류: [Binary Search] 문제 내용 정렬된 배열과 target이 주어졌을 때 해당 target이 정렬에 있다면 그 위치를 return하고 정렬에 없다면 들어가야 하는 위치를 return하는 문제였고 반드시 logN의 시간복잡도를 가지는 알고리즘을 쓰라고 했다. 문제 해결 흐름 1. Linear하게도 풀 수 있고 Binary로 풀 수 있는데 시간복잡도에 대한 제약조건이 존재하므로 Binary만 가능하겠다. class Solution: def searchInsert(self, nums: List[int], target: int) -> int: left = 0; right= len(nums) - 1; while(left int: return bise..