올바른 괄호 문자열 판별 1. 짝이 맞아야 한다 2. 여는 괄호없이 닫는 괄호가 들어갈 수 없다 3. 모든 괄호가 닫히지 않았다 (여는 괄호가 닫는 괄호보다 더 많음) class Solution: def isValid(self, s: str) -> bool: p={')':'(','}':'{',']':'['} stack=[] for c in s: if c==')' or c=='}' or c==']': if not stack or stack[-1]!=p[c]: return False stack.pop() else: stack.append(c) if stack: return False return True
합한 수가 target이면 현재 수 x와 target-x의 위치를 찾으면 된다 각 숫자의 위치를 저장해가면서 이미 지나간 위치에서 target-x가 있다면 [현재위치, dict[target-x]] 를 리턴하면 된다. 1. python class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: dict={} for i,x in enumerate(nums): if target-x in dict: return [dict[target-x],i] dict[x]=i 2. javascript /** * @param {number[]} nums * @param {number} target * @return {number[]} */ var t..
파이썬 알고리즘 인터뷰 책을 기반으로 공부했는데 (다른 알고리즘 시험에서 안나올 것 같은 뒷 부분이나 중간에 링크드 리스트 부분은 좀 넘겼다) 까먹은 부분 복습할 겸 처음부터 다시 풀어보았다 요즘 사이드 프로젝트 때문에 리액트만 하고 있어서 자꾸 알고리즘을 푸는 감각을 잃는 것 같다 다시 건들어보려고 한다 125번. 펠림드롬 - 한 번에 성공 leetcode.com/problems/valid-palindrome/submissions/ from collections import deque class Solution: def isPalindrome(self, s: str) -> bool: s=[c.lower() for c in s if c.isalnum()] return s==s[::-1] 344번. 문자열..
숫자를 문자열로 변환해서 뒤집은 다음 연산한다 class Solution: def reverse(self, x: int) -> int: x=str(x) x=x[::-1] if x[-1]=='-': x=int('-'+x[:-1]) x=int(x) if x>2**31-1 or x
제일 왼쪽은 고정해놓고 그 오른쪽만 투포인터로 계산한다. O(n^2) 정렬해놓고 합이 작으면 더 큰 곳으로 이동하고 크면 오른쪽 포인터를 왼쪽으로 이동시킨다 같은 원소가 있는 부분은 넘어가면서 구한다 1. python class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() res=[] for i in range(len(nums)-2): if i>0 and nums[i]==nums[i-1]: continue # 중복인 경우 넘어간다 left,right=i+1,len(nums)-1 while left
각 왼쪽, 오른쪽 끝에서 시작한다. 왼쪽의 벽이 더 높으면 오른쪽에서 안쪽으로 이동하고 (더 큰 벽을 찾아서) 오른쪽 벽이 더 높다면 왼쪽에서 안쪽으로 이동한다. 만약 현재 왼쪽에서 안쪽으로 이동하는데 지금까지 왼쪽에서 만난 벽 중 가장 높은 위치 lh 보다 작은 곳이라면 물이 고이므로 lh-height[l] 이런 식으로 더해준다. 1. python class Solution: def trap(self, height: List[int]) -> int: if not height: return 0 left,right=0,len(height)-1 l_max,r_max=height[left],height[right] amount=0 while left
연속된 집은 털 수 없다. 바로 이전 집의 dp값이나 두 번째 전 집에서 현재 집을 턴 합 중 더 큰 값이 현재 위치의 집에서 가장 큰 값이 된다 from collections import defaultdict class Solution: def rob(self, nums: List[int]) -> int: if not nums: return 0 if len(nums)
계단 오르기 문제 메모이제이션으로 재귀로 풀어도 되고 반복문으로 풀어도 된다 1계단에 오르는 방법 1로 가는거 한 가지, 2 계단에 오르는 법은 1에서 1칸 가는 방법, 0에서 2칸 가는 방법 2가지로 초기화한다. 나머지만 현재 위치보다 1칸 아래에서 오는 방법과 2칸 아래에서 오는 방법을 더해주면 된다 from collections import defaultdict class Solution: def climbStairs(self, n: int) -> int: dp=defaultdict(int) dp[1]=1 dp[2]=2 for i in range(3,n+1): dp[i]=dp[i-1]+dp[i-2] return dp[n]
합이 최대인 부분 배열을 찾는다 현재 값 혹은 현재값 + 이전까지의 합이 큰지 비교해서 더 큰 값을 dp배열에 넣고 최대 값을 리턴하면 된다. O(n)이 걸린다 class Solution: def maxSubArray(self, nums: List[int]) -> int: answer=[nums[0]] for i in range(1,len(nums)): answer.append(nums[i]+(answer[i-1] if answer[i-1]>0 else 0)) return max(answer) * 카데인 알고리즘 (가끔 알고리즘이나 자료구조 공부할 때 항상 등장하는 부분배열 최대값 구하기 알고리즘이다 O(n)에 구할 수 있다 현재의 부분 배열 합과 리턴해줄 최대값을 비교해 더 큰 값으로 계속 갱신해준다 ..
이런 방식으로 하면 공간복잡도(1) 시간복잡도(n)으로 아주 효율성이 좋다 class Solution: def fib(self, N: int) -> int: x,y=0,1 for _ in range(N): x,y=y,x+y return x 기본 메모이제이션 풀이 from collections import defaultdict class Solution: dict=defaultdict(int) def fib(self, N: int) -> int: if N