영최의 개발켈로그

✅ 해시 풀이- dict.fromkeys([arr],value)- 하나씩 더해가면서 자기자신아니면서 dict에 있는지 비교def solution(phone_book): d = dict.fromkeys(phone_book,1) for num in phone_book: temp = "" for n in num: temp+=n if temp in d and temp!=num: return False return True ✅ 정렬 풀이 - 일단 정렬- 파이썬 문자열의 y.startswith(x)사용하여 판단 (+endswith()도 있음)def solution(phone_book): phone_boo..

✅ 파이썬에서 해시(Hash)는 Dictionary 를 통해 구현 가능함 ✅ 언제 사용? 1) 키-값으로 저장할때 (숫자 아닌값으로 저장-찾을때)2) 빠른 접근-탐색 시 O(1)3) 집계 필요 시  -> from collections import Counter ✅ Dictionary 사용법#dict.fromkeys([arr],value)arr원소를 key로하고 value를 가진 딕셔너리가 생성됨keys = ['a', 'b', 'c']value = 0d = dict.fromkeys(keys, value)print(d) # 출력: {'a': 0, 'b': 0, 'c': 0}# 빈딕셔너리 생성dict1 = {} # {}dict2 = dict() # {}# 특정 key-value쌍을 가진 dictionary ..

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