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

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

n = int(input())m = list(map(int, input().split()))dp = [0]* ndp[0]=1for i in range(1, n): li =[] for j in range(i): if m[j]0: dp[i] = max(li)+1 else: dp[i] =1print(max(dp)) 지나는 j 인덱스 중 가장 값이 큰 걸 dp[i] 에 넣고 싶어서m[j] 가 m[i]보다 작은 경우에 배열에 넣어서 반복이 끝난 뒤 max 값을 뽑고길이가 증가했으니까 1을 더했다m[j] 가 m[i]보다 작은 경우가 나올 경우 max를 구할 수 있는 배열의 요소가 없고, 길이가 1부터 시작하기 때문에 1을 넣어줬다. 하지만 배열을 써서 max 값..