영최의 개발켈로그

1️⃣  위상정렬✅ 언제 사용? 유향 그래프의 모든 그래프를 방향성을 지키면서 순서대로 나열할때✅ 시간복잡도:  O(V+E) 노드와 간선을 모드 확인✅ 원리 : 1) 진입차수가 0인 노드를 큐에 넣는다.2) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거3) 새롭게 진입차수가 0이 된 노드를 큐에 넣음큐가 빌때까지 2)-3)반복(진입차수란? 특정한 노드로 들어오는 간선의 개수)✅ 주의: 1) 큐에 들어가는 원소가 2개 이상이면 정답이 여러개 존재함2) 모든 원소를 방문하기 전에 큐가 비면 사이클이 존재함✅ 기본 코드:from collections import deque# 노드의 개수와 간선의 개수를 입력 받기v, e = map(int, input().split())# 모든 노드에 대한 ..

0️⃣  MST( 최소신장트리, Minimum Spanning Tree)✅ 정의: 무방향 그래프에서 최소의 비용으로 모든 노드를 연결하면서 사이클이 발생하지 않는 트리✅ 사용되는 알고리즘: 크루스칼, 프림 ✅ 간적쿠간만프: 간선 적으면 크루스칼 간선이 많으면 프림 사용1️⃣  크루스칼✅ 언제 사용? 간선이 적을때✅ 시간복잡도(개선된) :  O(ElogE) (100만 정도) - 간선 정렬✅ 원리 :1) 간선 데이터를 비용에 따라 오름차순으로 정렬 2) 사이클이 발생하지 않는 경우 최소신장 트리에 포함시킴 (반복)✅ 서로소 집합 부모 찾기 최적화:parent[x] = find_parent(parent, parent[x]): 처음에는 parent[x] != x에서 parent[x] == x 까지 재귀를 돌면서..

1️⃣ 다익스트라✅ 언제 사용? 음의간선 없을때 한지점에서 특정지점까지 최단거리 구할 때 사용✅ 시간복잡도(개선된) :  O(elogv) (100만 정도) (경우에 따라 BFS로도 풀 수 있음; 인접리스트: O(e+v),인접행렬  O(v^2))✅ 원리 :1) 출발노드 선정 -> 2) 최단거리 테이블 ∞로 초기화 (출발노드는 0으로) -> 3) 방문하지 않은 노드 중 최단 거리가 짧은 노드 선택 (처음엔 출발노드, 최단 거리가 0이니까)-> 4) 해당 노드를 거쳐 다른 노드로 가는 비용 계산하여 최단 거리 테이블 갱신-> 3),4) 반복✅ 최적화: 힙 사용(거리 가장 짧은 노드), 방문처리 대신 테이블에 기록된 거리와 비교하여 큰 경우 PASS✅ 기본 코드:import heapq# sys.stdin.rea..

링크: https://www.acmicpc.net/problem/1261✅ 벽을 부순다 = 벽의 비용을 더했을때 최소비용이된다 => 다익스트라import heapqM,N = map(int,input().split())graph = [list(map(int,list(input()))) for _ in range(N)]INF = int(1e9)distance = [[INF]*M for _ in range(N)]dr = [-1,0,1,0]dc = [0,1,0,-1]def dijkstra(start_r,start_c): distance[start_r][start_c]=0 q=[] heapq.heappush(q,(0,(start_r,start_c))) while q: dist,(..

✅ 특정노드사이의 비용을 최소비용으로 잘못판단했다. => 이부분(start_v1[v2],start_v2[v1]) / 어느 지점을 특히 지나가야한다면 그사이에서도 다른 노드를 지날때가 더 최소일 수도 있다는걸 명심하자#수정 후path_1_v1_v2_N = start_1[v1]+start_v1[v2]+start_v2[N]path_1_v2_v1_N = start_1[v2]+start_v2[v1]+start_v1[N]#수정 전v1_v2_cost=INFfor (node, cost) in graph[v1]: if node==v2: v1_v2_cost=costpath_1_v1_v2_N = start_1[v1]+v1_v2_cost+start_v2[N]path_1_v2_v1_N = start_1[v2]..

✅ 이동시 -1 이 있으므로 최대 max(N,K)*2만큼의 배열이 필요하다 (입력이 5 17 일때 : 5->10->20->17)import heapqINF = int(1e9)N,K = map(int,input().split())distance = [INF]*(max(N,K)*2+1)def dijkstra(start): distance[start]=0 q=[] heapq.heappush(q,(0,start)) while q: dist, now = heapq.heappop(q) if distance[now]next_dist: distance[next_now]=next_dist heapq.heappush(q,(..

링크: https://school.programmers.co.kr/learn/courses/30/lessons/60063✅ 벽을 1로 두르는 방식 => 시작좌표:(1,1), 끝좌표:(N,N)으로 됨 유의✅ visited를 set()으로 해야 조회 시간복잡도 O(1)✅ 모든 회전가능성을 염두에 두기 (안그럼 풀이시간 엄청 소요되버림)from collections import dequedef solution(board): N = len(board) new_board = [[1]*(N+2) for _ in range(N+2)] for i in range(N): for j in range(N): new_board[i+1][j+1]=board[i][j] ..

✅ 쓸데없는 checked함수를 만들었음 => DFS에서 이동이 일어났는지를 moved로 flag를 만들고 이후 이동이 없으면 끝내는 방식을 써야함 / checked함수만든이유? 확인은 해야한다고 생각해서 만들었는데 DFS에서 확인할 수 있다는 걸 놓친것 같음. 어떤 과정이 다른 과정에 포함될 수 있는지를 한번 더 생각해보자✅ path에 처음 자기자신이 포함이 되어야한다는 점과 그래서 이동이 일어나면 길이가 1보다 커야한다는 점을 놓침 => 자기자신도 넣어야하는 경우와 해당 기능과 연관된 기능을 한번 더 꼼꼼히 살펴보자✅ DFS에서 재귀오류가뜸 => stack을 활용하거나 BFS를 사용하거나하면됨. stack으로 DFS를 구현할 수 있다는 점이 신기했음✅ 예시가 하나밖에 없을때 얼른 하나 만들어서 확인해..