Min IT's Devlog

풀이 일자: 23.02.23 난이도: [Hard] 분류: [Heap, Sorting, Greedy] 문제 내용 k = 최대로 진행할 수 있는 프로젝트 개수( 서로 다른 프로젝트) w = 현재 가지고 있는 자본 profits[i] = i번째 프로젝트를 해서 얻게 되는 순이익 capital[i] = i번째 프로젝트를 하기 위한 최소 자본 최대 k개의 프로젝트를 진행하여 w를 최대로 만드는 문제였다. 문제 해결 흐름(내 풀이) 1.우선 k개의 프로젝트를 진행하여 w를 최대로 만드는 것이기에 뭔가 Greedy하게 처리할 수 있지 않을까라는 생각.. → w의 자본이 있다고 했을 때 capital중에 w이하인 인덱스를 찾아서 profits 배열을 탐색 후 제일 큰 값 찾기 ## 배열이 작은 경우에는 잘 처리가 되었..

풀이 일자: 23.02.22 난이도: [Medium] 분류: [Binary Search] 문제 내용 weights라고 하는 배열에 순서대로 옮겨야 할 물건의 무게가 들어있고 days라는 변수에는 옮기는데 주어진 시간이 들어있다. weights에 들어있는 물건 순서대로 물건을 배로 옮기는데 하루에 배로 옮길 수 있는 최대 무게가 최소화되도록 옮긴다고 했을 때 배의 capacity를 구하는 문제이다. weights = [3,2,2,4,1,4], days = 3 만약 위의 배열이 주어졌을 때 (3,2), (2,4), (1,4)로 옮긴다면 최대무게가 6이 된다. 만약 (3,2,2), (4,1), (4) 이렇게도 옮길 수 있는데 이럴 경우 최대무게가 7이 된다. => 이러한 최대무게중 최소가 되도록 물건을 day..

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

풀이 일자: 23.02.18 난이도: [Easy] 분류: [Tree, DFS, BFS, Binary Tree] 문제 내용 이진트리의 root가 주어졌을 때 tree의 모든 노드의 좌우 위치를 바꾸는 게 문제의 내용이다. 문제 해결 흐름 1. 노드 순회가 필요하고 노드 순회 과정에서 단순히 자식 노드의 위치를 바꾸면 된다. → 일단 재귀적으로 구현해보자. # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def invertTree(self..

풀이 일자: 23.02.17 난이도: [골드 V] 분류: [Math, DP] 문제 내용 문제 해결 흐름 1. 이것도 대표적인 DP문제 중 하나로 DP문제에서 가장 중요한 것은 점화식을 찾는 게 중요하다. → 한번 N과 K를 차례대로 조정해보면서 직접 경우의 수를 구해보자. K=2 N=3인 경우 0~3사이에 2개의 수를 가지고 3을 만들 수 있는 경우의 수는 0+3 / 1+2 / 2+1 / 0+3으로 경우의 수가 4이다. 이런식으로 계속 채워나가다보면 어떤 패턴을 발견해나갈 수 있는데 바로 현재 위치의 위쪽과 왼쪽의 수를 합하면 해당 경우의 수가 된다는 것을 확인할 수 있게 된다. 이를 코드로 옮겨본다면, N, K = map(int, input().split()); dp = [[1 for i in rang..

풀이 일자: 23.02.17 난이도: [Easy] 분류: [Tree, BST] 문제 내용 BST의 root가 주어졌을 때 BST 내부의 노드 간의 차 중에서 가장 작은 값을 리턴하는 문제이다. [BST란?] BST란 Binary Search Tree의 축약어로 우리말로는 이진탐색트리라고 한다. 탐색 대상이 주로 배열인데 이를 이진 탐색트리로 변환한다면 데이터의 삽입, 삭제 등 데이터 조작에 강점을 가지게 된다, => 특징으로는 root를 기준으로 root보다 작은 수는 왼쪽 node, 큰 수는 오른쪽 node에 있는 것을 확인할 수 있다. 문제 해결 흐름 1. 트리가 나왔고 노드 간의 차이를 일단 알아야 하므로 Tree를 순회하는 알고리즘을 생각해봐야 한다. → 일반적인 Tree 순회 알고리즘으로는 DF..

풀이 일자: 23.02.16 난이도: [Silver 3] 분류: [DP] 문제 내용 문제 해결 흐름 1. 대표적인 DP문제로 점화식을 뽑아내는 것이 가장 중요하다. → 해당 문제에서 가장 중요한 제약 조건은 시작점을 계단으로 치지 않고 세 계단 연속으로 밟을 수 없다는 것이었다. → 3번째 계단까지는 시작점을 계단으로 계산하지 않는다는 점에서 따로 계산했고 그 이후부터는 점화식을 사용했다. dp[i-2] => 2칸으로 현재 위치로 올라왔을 때 값 dp[i-3] + stair[i-1] => 1칸으로 현재 위치로 올라왔을 때 값 ex. 왜 dp[i-1]로 안했는지에 대한 의문이 든다면? 만약 dp[i-1]이라고 하자.. dp[i-1]은 현재 위치보다 1보다 낮은 계단에 도착했을 때의 최대값이다. 그런데 dp..

풀이 일자: 23.02.16 난이도: [Easy] 분류: [Tree, DFS, BFS] 문제 내용 이진 트리의 root Node가 주어지면 해당 tree의 최대 depth를 구하는 문제이다. 문제 해결 흐름 1. 단순한 트리 순회 문제로 트리 순회 알고리즘 둘 중 아무거나 사용해도 무방하다. → BFS를 이용해 구해보자. # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def maxDepth(self, root: Optional[Tre..