aeightchill

재귀를 많이 써도 오류가 나지 않도록 재귀 허용 깊이를 늘리는 코드import syssys.setrecursionlimit(10000) 왜 필요한지?트리가 깊어지거나 재귀 홏출을 많이 쓰는 그래프 탐색 등을 수행할 때 기본 재귀 제한을 넘어서 초과가 발생하는 것을 방지하기 위해 사용한다.

🗂️ 문제 16953. A → B 📌 PointBFSA에서 2를 곱한 값과 1을 가장 오른쪽에 추가한 값으로 가지치기 하면서 B에 도달할 때까지 탐색한다. 📄 코드from collections import deque, defaultdicta, b = map(int, input().split())visited = defaultdict(int)q = deque([(a, 1)])visited[a] = 0ans = -1while q: num, cnt = q.popleft() #현재 숫자, 탐색 횟수 if num == b: #목표 숫자에 도달하면 탈출 ans = cnt break mul_two, add_one = num * 2, int(str(nu..

최단 경로 + 방문 노드 구하기단순히 거리를 구하는 것뿐 아니라 최단 경로를 따라 방문한 노드들을 어떻게 구할 수 있을까? DFS vs BFSDFS깊이 우선 탐색이라 최단 경로를 보장하지 않음경로를 찾을 수는 있지만 최단 경로가 아닐 수 있음 BFS한 단계씩 확장하면서 탐색하기 때문에무가중치 그래프에서 최단 경로 보장이 가능BFS + 부모 추적 방식 사용 시, 최단 경로를 복원할 수 있음 BFS로 최단 경로 + 방문 노드 구하기from collections import deque, defaultdict# 그래프 정의 (무방향)graph = defaultdict(list)edges = [(1,2), (1,3), (2,4), (2,5), (3,6)]for u, v in edges: graph[u]..

🗂️ 문제1238. 파티📌 PointDijkstra최단 거리 계산을 위해 다익스트라 알고리즘을 사용한다.각 노드에서 다른 모든 노드까지의 최단 거리를 구해야 하며, 다익스트라는 O(E log V)로 단방향 가중치 그래프에 적합하다. https://youngone-kang.tistory.com/118 [Algorithm] 다익스트라 (Dijkstra)다익스트라 알고리즘하나의 시작점에서 다른 모든 노드까지 가장 짧은 거리(최단 경로)를 찾는 알고리즘여러 도시(노드)가 도로(간선)로 연결되어 있을 때, 특정 도시에서 다른 도시로 가장 빠youngone-kang.tistory.com📄 코드import heapqINF = int(1e9) # 무한대 값# N: 마을 개수, M: 도로 개수, X:..

다익스트라 알고리즘하나의 시작점에서 다른 모든 노드까지 가장 짧은 거리(최단 경로)를 찾는 알고리즘여러 도시(노드)가 도로(간선)로 연결되어 있을 때, 특정 도시에서 다른 도시로 가장 빠르게 가는 방법을 찾을 수 있다. 특징음(-)의 간선이 없을 때 정상적으로 동작한다.각 노드까지의 현재까지 확인된 최단 거리를 1차원 리스트에 저장하고, 계속 갱신하면서 더 짧은 경로를 찾는다.* DP의 일종이라고 할 수 있는데 작은 문제의 해(특정 노드까지의 최단 거리 구하기)를 이용해 큰 문제를 푸는 방식을 따르기 때문 작동 방식출발 노드를 설정한다.최단 거리 리스트를 초기화한다.시작점은 거리 0, 나머지는 무한대로 설정한다.방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.해당 노드를 거쳐 다른..

1. 가상환경 리스트 조회conda env list# 또는conda info --envs # conda environments:#base * /Users/username/anaconda3myenv1 /Users/username/anaconda3/envs/myenv1datasci /Users/username/anaconda3/envs/datasci* 표시된 항목은 현재 활성화된 환경 2. 가상환경 실행 (활성화)▶︎ Windows:conda activate myenv1▶︎ macOS / Linux:source activate myenv1# 또는conda activate myenv1 (myenv1) user..

🗂️ 문제 1449. 수리공 항승📌 PointTwo Pointers테이프 시작 지점과 끝 지점을 이용해서 투 포인터로 풀이한다. https://youngone-kang.tistory.com/30 [Algorithm] Two Pointers (투 포인터)Two Pointers리스트에 순차적으로 접근할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. (응용문제) _ 특정한 합을 가youngone-kang.tistory.com📄 코드n, l = map(int,input().split())pipes = list(map(int,input().split()))pipes.sort()# 테이프 시작 위치start = pipes..

🗂️ 문제 2805. 나무 자르기📌 PointBinary Search절단기 높이 H를 이진 탐색으로 조정하며, 잘린 나무의 합이 M 이상인지 확인한다. 조건을 만족하면 더 높은 높이도 가능하므로 높이를 올린다. (left = mid + 1)조건을 만족하지 못하면 더 낮은 높이로 내려야 한다. (right = mid - 1) 📄 코드def solution(): N, M = map(int, input().split()) trees = list(map(int, input().split())) def is_enough(height): return sum((tree - height) for tree in trees if tree > height) >= M lef..

🗂️ 문제 11660. 구간 합 구하기 5📌 PointPrefix Sum2차원 배열 board의 누적합을 저장한 새로운 배열 prefix_sum을 만들어서 직사각형 구간의 합을 O(1)에 구할 수 있도록 한다. 📄 코드def solution(): N, M = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(N)] prefix_sum = [[0] * (N+1) for _ in range(N+1)] for i in range(1, N+1): for j in range(1, N+1): prefix_sum[i][j] = ( ..

🗂️ 문제 17270. 연예인은 힘들어📌 PointDijkstra그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우에 사용한다. 특징음(-)의 간선이 없을 때 정상적으로 동작‘각 노드에 대한 현재까지의 최단 거리’ 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신 작동 방식출발 노드를 설정한다.최단 거리 테이블을 초기화한다.방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.위 과정에서 3번과 4번을 반복한다. 📄 코드import heapq # 우선순위 ..