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

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

풀이 일자: 23.02.15 난이도: [Easy] 분류: [Array, Math] 문제 내용 int형 배열 num과 int형 변수 k가 주어졌을 때 num+k의 결과를 array형태로 리턴시키는 문제 문제 해결 흐름 저번에 풀었던 2023.02.14 - [코테/LeetCode] - [python3] 67. Add Binary문제와 사실상 비슷한 문제이다. 다만 num내부의 자료형이 int이고 결과도 int로 해야하기 때문에 저번처럼 여러번 자료형 변환을 거쳐 푸는 것은 비효율적으로 보인다. 1. k의 각 자리를 분리하기 위한 방법을 생각해보자. → 일반적인 십진수의 경우 각 자리를 구하는 방법은 반복문을 돌려가며 일의 자리를 하나씩 확인하는 방법이 존재한다. k = 112; ans = [] while (..

풀이 일자: 23.02.11 ~ 14 난이도: [Medium] 분류: [BFS, Graph] 문제 내용 n이 주어지고 이를 통해 0 ~ n-1로 각각 라벨링되어있는 노드가 있다고 생각하면 edge가 red인 것과 blue인 것이 존재하며 현재 이루고 있는 graph가 directed graph라고 했을 때 answer[i]이라는 곳에는 0에서 i번째 노드로 갈 때 제일 최단의 길이를 넣어서 리턴하는 문제. ( 단 빨간색과 파란색 edge를 번갈아가며 이동하도록 해야함) 문제 해결 흐름 1. 전체적으로는 shortest path 알고리즘을 사용하면 되는 것으로 보이나 우선 directed graph이므로 일단 다익스트라 알고리즘은 사용할 수 없다. → 그럼 이를 대체할 알고리즘은 현재 0에서 각 노드로의 ..

풀이 일자: 23.02.14 난이도: [Easy] 분류: [Math, Bit Manipulation] 문제 내용 str형태로 주어지는 이진수 a, b를 합한 결과를 이진수 문자열형태로 리턴하는 문제이다. 문제 해결 흐름 1. 2진수를 10진수로 바꿔서 더한다음 다시 2진수로 변환하는 방법이 있겠다. → int(num, 2)를 사용하면 2진수 형태의 문자열을 10진수로 변환이 가능하며 bin(num)을 사용하면 '0b1111'의 형태의 이진수 문자열을 얻을 수 있다. 0b는 필요없으니까 [2:]를 이용한 slicing을 하면 끝! class Solution: def addBinary(self, a: str, b: str) -> str: a = int(a, 2); b = int(b, 2); ans = bin..

풀이 일자: 23.02.13 난이도: [Easy] 분류: [Math] 문제 내용 2개의 양수가 주어졌을 때 그 수들을 포함한 그 사이의 수들 중 홀수의 개수를 구하는 문제이다. 문제 해결 흐름 1. 별다른 알고리즘 보다는 어떤 수학적인 패턴을 찾아서 구해내는 것이 맞겠다. → 짝수부터 세는 경우 ( high - low )//2 + 1개의 홀수가 나온다. class Solution: def countOdds(self, low: int, high: int) -> int: if (low & 1) == 0: low += 1; return 0 if low > high else (high - low)// 2 + 1; Time Complexity: O(1) 반복문 돌아가는 것 없이 계산만 진행하기에 O(1)이다. S..

풀이 일자: 23.02.10 난이도: [Medium] 분류: [DP, BFS] 문제 내용 0(물)과 1(땅)로 구성된 n*n 크기의 grid라는 배열을 줬을 때 땅과 가장 가까운 물타일들 중 땅과의 manhattan거리가 최대일때의 거리를 구하는 문제이다. 주의) 문제에 나와있긴 하지만 거리를 구할 때 manhattan거리를 사용하라고 했다. Manhatten 거리 = |x0 - x1| + |y0 - y1| Euclidian 거리 = ( (x0 - x1)2+(y0 - y1)2)½ 예를 들면 아래의 배열처럼 주어졌다고 가정해보자. 1 0 1 0 0 0 1 0 1 각 물타일과 해당 물타일과 가장 가까운 땅과의 거리를 적어보면 아래와 같이 될 것으로 최대일 때의 거리는 2이다. 1 0(1) 1 0(1) 0(2..