Problem Solutionarrayn*n 2차 배열에서 중복된 값, 존재하지 않는 값을 찾는 문제.hash를 사용해서 frequency를 구한다음에 정답을 구해도되고나는  1~n*n까지 연속된 숫자이므로 visited 를 사용해서 이미 방문했는지를 체크하도록 했다.  Codeclass Solution: def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]: answer = [] n = len(grid) visited = [0] * (n*n + 1) twice_num = 0 missing_num = 0 for i in range(..

Problem SolutiondbLCS (Longest Common Subsequence)이 문제의 힌트를 보고 LCS 알고리즘을 사용한 문제라는 것을 알았다.LCS 알고리즘에 대한 설명은 다른 블로그에서 더 자세하게 설명해두어서 참고했다!https://chanhuiseok.github.io/posts/algo-34/ 알고리즘 - LCS(Longest Common Subsequence, 최장 공통 부분 문자열) 알고리즘LCS 알고리즘이란?chanhuiseok.github.io 단 LCS 의 길이를 구하는 알고리즘이라서 LCS 문자를 찾으려면 역추적(back tracking)을 이용해서 구해야한다. 주어진 2개의 string의 LCS 를 구하는 규칙은 아래와 같다.문자열을 비교하여 같았을 때현재 칸에 들어..

Problem Solutiondphashi, j를 피보나치 수열 마지막 두 숫자로 두고 dp[(i, j)] 에 해당 수열의 길이를 저장한다.해시맵 index_map 을 사용하여 빠르게 arr[k] 의 index를 찾을 수 있도록한다.해시셋을 이용하여 arr[i]+arr[j] in arr 여부를 확인한다.Bruteforce 로 풀면 time limit exceeded 나는 문제. db를 사용해서 풀어햐한다. (i, j)를 마지막 두 숫자로 하는 피보나치 수열 찾기!즉, arr[i], arr[j]를 고정하고, arr[i] + arr[j] == arr[k]가 되는 k를 찾아가야 합니다.이를 위해 j를 기준으로 i를 선택하고, (i, j) 쌍을 만들도록 설계합니다.반복문을 돌때 j부터 돌아서 항상 idb[(i,..

Problem SolutionKadane's algorithmsubArray 중 절대값 합의 최대값을 구하는 문제.2중포문으로 구현하면 당연히 time limit 이 발생한다.힌트 중에서 Kadane's 알고리즘을 사용하라고한다. 알아보았더니 dp 문제였다.Kadane's 알고리즘을 간략히 설명하면일반적인 Kadane’s Algorithm은 최대 연속 부분합을 구하는 알고리즘입니다.여기서는 최대 합과 최소 합을 동시에 추적하여, 그 절댓값 중 가장 큰 값을 반환하도록 변경합니다.현재까지의 max_sum/min_sum 을 현재 num과 비교하며 갱신한다.Kadane's 알고리즘 설명은 다른 블로그 설명을 참고했다.https://scavienger.tistory.com/19 [Algorithm] Kadane..

Problem Solutionarraybinary treerecursive preorder, postorder list 을 보고 binary tree을 구하는 문제. Code# 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 = rightclass Solution: def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]..

Problem Solutionbrute force 1, 0 으로 만들 수 있는 이진법 수 중 n=len(nums) 을 만족하는 배열 중 nums에 존재하지않는 string 반환하는 문제. Codeclass Solution: def findDifferentBinaryString(self, nums: List[str]) -> str: n = len(nums) chars = ["1", "0"] def generate(n, cur=""): if n==0: return [cur] res = [] res += generate(n-1, cur + "0") res += g..