[Gold I] 멀티탭 스케줄링 - 1700 문제 링크 성능 요약 메모리: 34120 KB, 시간: 68 ms 분류 그리디 알고리즘 문제 설명 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다. 예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면, 키보드 헤어드라이..

새로운 목표 설정 1. 해당 부분이 GOLD III이 나올때까지 반복 숙달한다. 2. 공부한 내용을 REVIEW 하면서 블로그 포스팅으로 정리한다. 3. 문제집(BOJ)에 북마크 한 문제 위주로 공부한다. 목표 기한 05/31

괄호 안은 현재 수준 1. 그리디 (SILVER III) 2. 구현 (SILVER II) 3. 그래프 1. BFS, DFS (GOLD III) 2. 최소 신장 트리 (GOLD III) 4. 정렬 1. 선택정렬 2. 삽입 정렬 3. 퀵 정렬 4. 계수 정렬 5. 탐색 1. 순차 탐색 2. 이진 탐색 3. 이진 탐색 트리

보호되어 있는 글입니다.

N = int(input()) M = int(input()) import sys input = sys.stdin.readline print = sys.stdout.write result = 0 #a, b, cost edges = [list(map(int, input().split())) for _ in range(M)] edges.sort(key=lambda x: x[2]) parent = [i for i in range(N+1)] def find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x] def union(a, b): a = find(a) b = find(b) if a > b: parent[a] = b else: parent..

오늘 Union-Find 심화 문제까지 풀이하였고 (정답 코드를 일부 참고함... 너무 어려움,.) Union-Find가 무엇인지 파악을 완료하였다. 그리고 이를 이용한 MST 구현 방법 중 크루스칼 알고리즘을 공부하고 구현하였다. 크루스칼 알고리즘은 그리디 알고리즘의 일부이며, 알고리즘의 수행시간을 잡아먹는 것 중 가장 긴 것은 sort 라고 하였다. 이를 이용한 기본 문제를 풀이하였고 처음에는 시간초과가 나왔지만 입출력을 표준 입출력으로 바꿔풀어 정답을 맞췄다. 내일은 이 알고리즘을 조금 더 풀어보고 익숙해졌다 싶어질때쯤 위상정렬을 공부할 예정이다. https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결..