Algorithms and Languages/파이썬 알고리즘 문제풀이 (59) 썸네일형 리스트형 [Python/DailyAlgo, 백준] 86. 최소 신장 트리, 1197. 최소 스패닝 트리, 89. 동기화 서버 구축 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기크루스칼 알고리즘https://dailyalgo.kr/ko/problems/86https://www.acmicpc.net/problem/1197https://dailyalgo.kr/ko/problems/89풀이세 문제는 사실상 동일한 문제임.86. 최소 신장 트리더보기def solution(n, edges): def find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x] def union(x, y): x_root = find(x) y_roo.. [Python/백준] 20040. 사이클 게임 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기유니온파인드https://www.acmicpc.net/problem/20040풀이import sysinput = sys.stdin.readline# 0 ~ n-1 점 n개 주어짐# 어느 세 점도 일직선 위에 놓이지 x.# 매 차례 두 점 선택 긋는데, 교차는 가능.# 사이클 완성 시 게임이 종료됨.# 이전에 그은 선분만 다시 못 그을 뿐, 이미 뽑은 점 재선택은 가능# 입력 : 점의 개수 n, 진행된 차례 수 m# 출력 : m차례까지 게임 진행 후 사이클 만들어졌다면 만들어진 차례 번호 출력,# 안만들어졌으면 0을 출력.# 출력 단계는 1부터 시작해서 m까지임에 유의.def find(x): .. [Python/백준] 1717. 집합의 표현 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기더보기유니온 파인드https://www.acmicpc.net/problem/1717풀이import sysinput = sys.stdin.readline# 백준 때문에sys.setrecursionlimit(10 ** 6)n, m = map(int, input().split())parent = list(range(n+1))rank = [0] * (n + 1)def find(x): if parent[x] != x: # 만약 루트 노드가 아니면 # -> 루트 노드를 찾아가서, 그 루트 노드의 parent 즉 루트 노드 그 자체를 return한 걸 # 계속 끌.. [Python/DailyAlgo] 93. 게으름뱅이 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기힙https://dailyalgo.kr/ko/problems/93풀이from heapq import heappop, heappushdef solution(todoList): # 홀수 번째 날: 할 일을 받기만 # 짝수 번째 날: 할 일을 받은 후 쌓인 일 중 하나를 처리 # 각 일(todo)에는 이름, 마감 기한, 중요도가 부여됨. # 처리 기준: # 1. 마감 기한이 빠른 놈. (오름차순) # 2. 중요도가 가장 높은 놈. -> 반대로 설계하자 (오름차순) # 이름이 사전순으로 앞선 놈. (오름차순) # n일동안 주어지는 할 일 정보 todoList.. [Python/프로그래머스] 42626. 더 맵게 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기힙https://school.programmers.co.kr/learn/courses/30/lessons/42626풀이from heapq import heappush, heappop, heapifydef solution(scoville, K): # 가장 낮은 놈 하나 빼서, 그거 지수 + 하나 더 뺌 * 2 한거 push하면 됨 # 그 push한 결과가 K보다 크면, 거기까지 pop한 횟수(또는 push한 횟수)를 return하면 됨 # 원래 있던 리스트 scoville을 heap으로 바꾸는 게 핵심임. # 그냥 저 scoville를 가지고 heappop을 .. [Python/DailyAlgo, 백준] 92. 우선순위 큐, 11279. 최대 힙, 11286. 절댓값 힙 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기힙https://dailyalgo.kr/ko/problems/92https://www.acmicpc.net/problem/11279https://www.acmicpc.net/problem/11286풀이92. 우선순위 큐더보기from heapq import heappop, heappushdef solution(queries): heap = [] answer = [] for query in queries: # pop if query == 0: # answer.append(heappop(heap) if heap else 0) .. [Python/백준] 1068. 트리 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기더보기트리 + dfs or 트리 + 순회https://www.acmicpc.net/problem/1068풀이1차 시도) 실패테케는 다 맞았는데… 더 고민해보자.import sysinput = sys.stdin.readline# 노드 하나 지운 이후의 트리의 리프 노드 개수를 구하라.# 노드를 지우면 그 노드에 딸린 서브트리가 통째로 지워짐.# 입력 : 노드 개수, 0~n-1번 노드까지의 각 노드의 부모, 지울 노드의 번호# 출력 : 처리 이후 리프 노드의 개수# 흠... 이거 오름차순으로 주나?# 일단, 결국 그 노드를 기준으로 후위 순회 돌리면 되겠는데?# 후위 순회의 action은, 자신의.. [Python/백준] 20364. 부동산 다툼 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기이진 트리https://www.acmicpc.net/problem/20364풀이1차 풀이, 실패import sysinput = sys.stdin.readline# 이진 트리# 루트 땅은 1번# 방 번호는 그냥 완전 이진 트리 인덱스대로임.# 오리들이 1번 땅에서 출발할건데,# 입력 : 땅 개수 n, 오리 수 Q# N 100만# 2번째 줄부터 Q개의 줄 동안 i줄에 i번째 오리가 원하는 땅 번호 xi# 출력 : Q개의 줄을 출력할건데, 갈 수 있으면 0, 못 가면 처음 마주치는 점유된 땅 번호.# 이거 dfs + 백트래킹 쓰면 될 것 같은데? => 안됨. q*O(V + E) 시간 터짐.# 원하는.. 이전 1 2 3 4 5 ··· 8 다음