소민's Blog

25515.트리 노드 합의 최댓값 내 풀이pypy로 하면 메모리 초과recursion제한 안두면 런타임 에러,,,🤬 (백준 문제는 이래서 싫어) dfs로 리프노드부터 각각의 합이 양수인 경우에만 위로 보냄리프노드 일때와 아닐때로 나누고아닌 경우에는 재귀사이클 발생하지 않도록 visited 체크import syssys.setrecursionlimit(10**6)n = int(input())graph = [[] for _ in range(n)]for i in range(n-1): a, b = map(int, input().split()) graph[a].append(b)nums = list(map(int, input().split()))visited = [False for _ in range(n..

리코쳇 로봇 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 내 풀이 - BFS벽이나 장애물에 부딪칠때까지 while문으로 이동부딪치면 그 전 위치 반납하는게 일반 dfs와 차이가장 먼저 return 된게 가장 최단거리from collections import dequedef solution(board): board = [list(b.rstrip()) for b in board] n = len(board) m = len(board[0]) dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] visited = [[False] * m for _ in rang..

1446. 지름길 내 풀이O(D + N)이라 완탐했음DFS + DPdp[i]: 0에서 i까지 도달하는 데 필요한 최소 거리현재 위치에서 갈 수 있는 지름길 or 직진을 따라가며 최소 거리 갱신from collections import defaultdictn,d=(map(int,input().split()))road=defaultdict(list)for _ in range(n): s,e,k=map(int,input().split()) road[s].append((e,k))dp=[i for i in range(d+1)]def dfs(end,total): if end>d: return if dp[end] 다른 풀이- DP + 선형 탐색 (Bottom-Up 방식) DFS 호출..

무인도 여행 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 내 풀이BFS bfs로 하나의 섬 돌면서 합을 tmp로 구한 후에 한번에 return from collections import dequedef solution(maps): answer = [] graph = [] for map in maps: graph.append(list(map)) n = len(graph) m = len(graph[0]) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(i, j): tmp = int(grap..

우수 마을  풀이DFS+DPsys.setrecursionlimit(10**6) 안하면 런타임 에러‘우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.⇒ 선정되지 않은 마을 끼리도 붙어있을 수 있다 루트 노드는 1개의 노드만 붙음 ⇒ 루트, 자식 노드 모두 선정되지 않아도 됨값을 넣어주기 전에 탑다운으로 뒷부분 dfs가 먼저 돌아줘야한다루트 노드를 우수마을로 선택 X → 자식노드 선택 중에 최댓값루트 노드를 우수마을로 선택 O → 무조건 자식노드는 선택 Xfrom collections import defaultdictimport syssys.setrecursionlimit(10**6)n = int(input())village = [0] + list(map(int, in..

여행경로 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 내 풀이종료조건 따지려고 경로마다 num 붙여서 visited 생성근데 이전에 내 풀이 보니까 if len(path)== len(tickets)+1 해도 됐음ㅋㅋ무조건 인천에서 시작한다해당 경로 방문 유무 백트래킹from collections import defaultdictdef solution(tickets): graph=defaultdict(list) num=0 for ticket in tickets: s,e=ticket graph[s].append((e,num)) num+=1 ..

2668.숫자고르기 내 풀이1,2번 행끼리의 집합이 동일해야 한다 1번행을 인덱스, 2번 행을 val로 두기dfs 돌면서 사이클 찾기최대 길이 이므로 사이클 끼리 더함앞 사이클에서 진행된 애들은 다시 체크할 필요 X처음에 바보같이 이미 존재하는 값의 위치를 bisect_left로 찾아서 틀림순서대로 들어가있는게 아니기때문에 index로 찾아야함n=int(input())lst=[0]+[int(input()) for _ in range(n)]answer=[]def dfs(val): global answer if val in picked: i=picked.index(val) answer+=picked[i:] return picked.append(val) ..

빛의 경로 사이클 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  내 첫 풀이- fail예제는 통과하는데 테스트 다 틀림 --...일단 문제가 1,1에서만 시작하는거라고 이해했는데 그게 아니고 완탐이었음문제 설명이 이상한거 아닌가..0으로 겉을 두르고 확인-> 오히려 0일때 값을 그대로 넘기는 과정에서 에러가 나는 듯함from collections import dequeanswer = []def solution(grid): # 동남서북 dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] n = len(grid) + 2 m = len(grid[0]) + 2 ..

단어변환 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  내 풀이백트래킹예외사항 주의할 것! 처음에 한글자씩 비교 확인 안하고 아래와 같은 코드를 넣었는데if len(set(cur+next))!=len(target)+1: #한글자 차이가 아니면 continue ->  "aab", "aba"와 같이 중복된 글자가 다른글자일 경우를 제외해버림answer = 10000def solution(begin, target, words): visited=[False for _ in range(len(words))] def recur(cur, target,cnt): global an..

📍 백트래킹 주의사항리스트를 append, pop으로 변경하면서 재귀를 도는 경우 문제가 발생할 수 있음-> 변경한 경우에는 return 하기전에 path[:] 로 복사해서 쓸 것append, pop 대신 재귀로 넘기는 파라미터값에서 추가해주면 복사 안해도됨def solution(tickets): def dfs(start, path): if len(path) == len(tickets) + 1: answer.append(path[:]) # 리스트를 복사해서 저장 return for i, next in enumerate(dict[start]): dict[start].pop(i) # 항공권 사용 ..