<리트코드> 739번 파이썬 알고리즘 [스택] def dailyTemperatures(self, t: List[int]) -> List[int]: ans = [0] * len(t) stk = [] # store idx for i, cur in enumerate(t): while stk and cur > t[stk[-1]]: l = stk.pop() ans[l] = i - l stk.append(i) return ans 알고리즘 2021.12.05
<리트코드> 20번 파이썬 알고리즘 [스택] def isValid(self, s: str) -> bool: table = { "}" : "{", ")" : "(", "]" : "[" } stack = [] for c in s: if c in table: # stack 마지막과 c가 [] {} () 이런식으로 되는지 확인 if stack and stack[-1] == table[c]: stack.pop() else: return False else: stack.append(c) return True if not stack else False 알고리즘 2021.12.04
<리트코드> 206번 파이썬 알고리즘 [연결 리스트 역순] def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: prev, cur = None, head while cur: nxt = cur.next cur.next = prev prev = cur cur = nxt return prev 알고리즘 2021.12.03
<리트코드> 21번 파이썬 알고리즘 [연결 리스트] def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode(0, head) prev, cur = dummy, head while cur and cur.next: # save ptrs nxtPair = cur.next.next scd = cur.next # reverse cur.next = nxtPair scd.next = cur prev.next = scd # update prev = cur cur = nxtPair return dummy.next # 필요한 것 처음에 무엇을 저장할 포인터로 설정 해야 할지 생각하기 이후에 reverse 코드 짜기 다음으로 업데이트 하기 알고리즘 2021.12.01
<백준> 5525번 파이썬 알고리즘 n = int(input()) m = int(input()) s = input() ans = 0 cnt = 0 for i in range(1, m - 1): if s[i - 1] == "I": if s[i] == "O" and s[i + 1] == "I": cnt += 1 i += 2 if n == cnt: ans += 1 cnt -= 1 else: cnt = 0 print(ans) I로 시작했을 때 그뒤에 OI가 있으면 cnt += 1 그리고 cnt 가 n 과 일치할 때 ans += 1 이후에 또 판별해야되니까 cnt -= 1 하는 것이다 알고리즘 2021.11.28
<백준> 5430번 파이썬 알고리즘 import sys from collections import deque t = sys.stdin.readline() for _ in range(int(t)): f = sys.stdin.readline().rstrip() n = int(sys.stdin.readline()) arr = deque(sys.stdin.readline().rstrip()[1:-1].split(",")) if n == 0: if 'D' in f: print("error") continue else: print("[]") continue e = 0 # R 홀수 or 짝수 일때 경우 r = 0 for i in f: if i == "R": r += 1 else: if arr: if r % 2 == 0: #짝수일때 arr.popleft.. 알고리즘 2021.11.27
<리트코드> 561번 파이썬 알고리즘 def arrayPairSum(self, nums: List[int]) -> int: nums.sort() res = 0 for i in range(0, len(nums), 2): res += nums[i] return res 알고리즘 2021.11.24
<리트코드> 42번 파이썬 알고리즘 [투 포인터] def trap(self, height: List[int]) -> int: if not height: return 0 v = 0 l, r = 0, len(height) - 1 l_max, r_max = height[l], height[r] while l < r: l_max, r_max = max(l_max, height[l]), max(r_max, height[r]) if l_max 오른쪽 장벽은 왼쪽보다 크거나 같기 때문에 신경 안써도 되고 왼쪽의 최대만 신경써서 현재 높이만큼 뺀게 물이 찬다 이부분만 이해하면 될 것 같다 알고리즘 2021.11.24
<백준> 2579번 파이썬 알고리즘 [동적 프로그래밍] import sys n = int(sys.stdin.readline()) s = [0 for _ in range(301)] dp = [0 for _ in range(301)] for i in range(n): s[i] = int(input()) dp[0] = s[0] dp[1] = s[0] + s[1] dp[2] = max(s[0] + s[2], s[1] + s[2]) for i in range(3, n): dp[i] = max(dp[i - 3] + s[i - 1] + s[i], dp[i - 2] + s[i]) print(dp[n - 1]) dp에 i - 3 부분이 있으므로 0, 1, 2 까지는 직접 계산해준다 알고리즘 2021.11.20
<백준> 1629번 파이썬 알고리즘 [분할정복] import sys a, b, c = map(int, sys.stdin.readline().split()) def pow(a, b): if b == 1: return a % c tmp = pow(a, b // 2) if b % 2 == 0: return tmp * tmp % c else: return tmp * tmp * a % c print(pow(a, b)) 문제를 통해 시간을 줄일 수 있는 부분은 b!! a * a * a * a * a ..... 연속적이면 시간소모가 큼 따라서 나눠서 곱함(a, b = 5, 4 -> (5^2) * (5^2)) 완전 이진트리 모양으로 생각하면 편함 알고리즘 2021.11.12