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..

Problem Solutionpermutationbacktracking DFS중복 순열을 사용한 문제.중복 허용, 순서 고려하여 모든 경우의수를 따져야하지만 만들어진 string이 중복되면안된다.permutation을 사용하되 결과를 set에 담아서 저장하도록했다. 백트래킹을 사용했지만 시간복잡도에서 최악의 경우 많이 소요될 수 있다.Codeimport itertoolsclass Solution: def numTilePossibilities(self, tiles: str) -> int: def generate(cur, used, result, r): if len(cur) == r: print(cur) result...

Problem Solutionstackbrute forceI 가 나오면 숫자 증가,D 가 나오면 숫자가 감소하도록하여 가장 작은 수를 반환하는 문제.지난번 비슷한 문제에서 dfs 를 사용했어서 비슷하게 풀면되는 줄 알고 삽질함 사전적으로 가장 작은 숫자를 반환해야하므로 가장 작은 수인 1부터 숫자 추가.마지막 인덱스이거나 patter[i] == I 이면 stack 모두 비울때까지 res 배열에 넣는다. stack 이라서 FIFO 구조로 먼저 넣은 숫자 먼저 res에 저장된다. 마지막에 res 배열에 있는 숫자들 join 해주면됨! pattern의 길이가 8까지라서 hint에도 bruteforce로 다해보라고 권했음.  Codeclass Solution: def smallestNumber(self, ..

ProblemSolutionHashMapi bad pair 정의 if i bad pair의 쌍 개수 구하기관점을 바꿔서 i - nums[i] == j - nums[j] 인 good pairs를 구한 뒤 전체 - good pairs를 구한다.즉, nums[i] - i 값이 동일한 숫자끼리 good pair가 된다.그러므로, 특정 값 key = nums[i] - i를 기준으로 그룹을 만들고, 동일한 값이 등장할 때마다 good pair를 세면, 전체 쌍에서 빼서 bad pair를 구할 수 있다. 아래는 처음에 2중 for문으로 bruteforce로 풀었다가 time out 이 발생했던 코드..ㅠㅠ# solve 1)class Solution: def countBadPairs(self, nums: List..