처음에 bfs로 풀었다가 크게 당했던 문제...다 풀고나서 통과 못한 테케를 보고 백트래킹 써야하는 걸 깨달았다class Solution: def exist(self, board: List[List[str]], word: str) -> bool: n,m = len(board), len(board[0]) dirx,diry=[0,0,-1,1],[1,-1,0,0] start=[] for i in range(n): for j in range(m): if board[i][j] == word[0]: start.append((j,i)) def backtrack(x,y,s..

위상정렬이 med로 나오다니 무서운 곳이다옛날에 열심히 연습했던 것 같은데 오랜만에 보고 1트로 풀어서 뿌듯deg 가 0인 것부터 진입할 수 있다from collections import dequeclass Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: # 위상정렬 r = {i: 0 for i in range(numCourses)} link = {i:[] for i in range(numCourses)} fin =[] q = deque() for pre, cur in prerequisites: r..

First Try: TLEI was like.. why does it make TLE???? it seemed like there was only one for loopHOwever "if i not in nums:" also takes O(n).. which makes the Time Comp O(n^2)Even so it needs some optimizationIn the for loop, we only have to iter till the length of the list, and if theres no return value then return n+1class Solution: def firstMissingPositive(self, nums: List[int]) -> int: ..

easy Q that asks the missing numberclass Solution: # 0~n 까지인 배열/set/dict를 만들고, nums 에 for 돌리면서 없는지 찾기 def missingNumber(self, nums: List[int]) -> int: # for no in range(len(nums)+1): # if no not in nums: # return no n = len(nums) ex_res = (n*(n+1))//2 tmp = sum(nums) return ex_res-tmp At first attempt...came up with a common ans,..

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/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()..

한국 코테에서는 트리가 잘 안 나오는 것 같다자료구조 때 했었는데 직접 구현해본 기억이 별로 없는 듯100. Same Tree두 트리가 같으면 True, 다르면 False를 반환하는 문제다처음에는 inorder 등 순회를 하면서 가지고 온 결과가 같으면 같은 트리지~ 생각하고 풀었는데 막상 확인해 보니결과 배열에 들어있는 노드들의 값은 같았지만 구조가 다른 경우 (null) 등.. 정확하게 파악되지 않았다다른 트리임에도 res 배열 값이 같아서 같은 트리로 취급됨주석처리한 부분이 문제의 코드이고# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# s..

주말에 갑자기 c++ 로 코테를 치게 되어서 3일동안 c++을 공부했다예전 자료구조 수업을 c로 들었던 것 그리고 컴프실을 c로 들었던가특히 ~자동으로 알아서 다 해주는~ 파이썬을 쓰다가 c++ 쓰려니까 수동기어가 달린 차를 모는 것 같은 느낌이다언어가 c, c++, java밖에 없던데 c로 필요한 자료구조 다 만들어서 코테를 통과하려면 피지컬이 대단해야 할 것 같다암튼 타입 지정, 세미콜론, vector, 필요한 파라미터 전달같은 것에 익숙해져 있다가 다시 파이썬으로 오니까 또 관성대로 하게 된다 친구 네트워크문제민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.어떤 사이트의 친구 관계가..

리트코드 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..