import sysclass Solution: def maxProfit(self, prices: List[int]) -> int: minVal = sys.maxsize res=0 for i in prices: if i 엊그제인가 코테를 봤는데 1번 문제가 이거랑 똑같은 게 나왔다아주 쉬운 문제인데 1시간에 3문제라 촉박해서 그런지... O(n^2)으로 풀어버렸다실수하지 않게 다시 풀어본다...다행히도 1번을 O(n^2)으로 풀어내고 2, 3번엔 집중했는지,,, 코테는 붙어서 면접을 보게 됐다

처음에 bfs와 딕셔너리 쓰면 되는 건 잘 알겠는데, 어떻게 한글자씩 다른 word를 탐방할지 고민스러웠다for 문을 다 돌려서 딕셔너리에 넣고 비교하는 코드를 짰는데, 당연하게도 TLE 가 났고 ...답은 fox 면 그 안에 fix, fux, xox 이런 걸 넣는 게 아니라*ox : foxf*x: foxfo*: fox이렇게 딕셔너리에 키랑 값을 저장하는 거였다메모리는 많이 들겠지만 TLE 가 나지는 않을 것 같다from collections import Counter, defaultdict, dequeclass Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: if end..

https://www.acmicpc.net/problem/1707처음에 지문 읽고 이해가 안돼서 (ㅠㅠ) 구글에서 이미지 봤다자료구조 시간에 배웠던 건데 구현해보는 건 처음이다그냥 번갈아서 색 칠하고 겹치면 Out 시키면 되는 거 같다그러면 dfs bfs 중 하나 쓰면 될 듯하다 import sysfrom collections import dequeinput = sys.stdin.readlinetk = int(input())def bfs(x): q = deque() q.append(x) vis[x] = "W" while q: cx = q.popleft() for nx in g[cx]: if vis[nx] == "0": ..

https://www.acmicpc.net/problem/16509  일반적이지만 살짝 귀찮은 bfs 문제다저렇게 뛰는 친구들은 knight prob 비슷한 결로 아주 많이 나오고거기에 visited 할 때마다 이전 노드 방문값 ++ 해주는 방법도 아주 쉽다import sysfrom collections import dequeinput = sys.stdin.readlinen1, m1 = map(int, input().split())# 상 우 하 좌dir = [[-2, -3], [2, -3], [3, -2], [3, 2], [2, 3], [-2, 3], [-3, 2], [-3, -2]]nodir = [ [[0, -1], [-1, -1]], [[0, -1], [1, -1]], [[1, 0],..

https://www.acmicpc.net/problem/3584조금 쉬운 문제다두 노드에서 공통된 가장 가까운 부모를 찾는 문제setrecursionlimit을 안 걸어줬다가 recursionerror로 몇번 반려당했다import syssys.setrecursionlimit(100000)input = sys.stdin.readlinetk = int(input())def find_parent(x, res, depth): res.append((x, depth)) if len(tree[x]) == 0: return for i in tree[x]: find_parent(i, res, depth + 1)for _ in range(tk): n = int(input()..

리트코드 134. Gas Station class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: total=0 curr=0 res = 0 for i in range(len(gas)): total += gas[i] - cost[i] curr += gas[i]- cost[i] if curr=0 else -1 # total, curr, 인덱스 값을 놓고 # 순회하면서 가스-비용 계산한다 # 만약 현재 노드까지에서 가스 - 비용이 마이너스라면 이 시작 지점으로 갈 수..

560. Subarray Sum Equals K리트코드 누적합 문제다처음에는 for문 돌려서 모든 합을 구하고, 또 거기서 기존 누적합 결과들을 하나하나 빼는 방식을 생각했는데 아래와 같은 방법을 이용하면 O(n)만에 풀 수 있다.class Solution: def subarraySum(self, nums: List[int], k: int) -> int: dict={0: 1} res=0 pr = 0 for no in nums: pr +=no if pr-k in dict: res += dict[pr-k] if pr not in dict: d..

def find_parent(x): if p[x] != x: p[x] = find_parent(p[x]) return p[x] find_parent 에서 재귀가 너무 깊어져서 문제가 생겼다sys.setrecursionlimit 으로 늘려줄 수 도 있겠지만 재귀가 아닌 while 을 사용해 부모를 찾아주는 방식으로 변경했다 def find_parent(x): while p[x] != x: p[x] = p[p[x]] x = p[x] return x