pythaac의 개발노트

BAEKJOON Online Judge(BOJ) 문제입니다. https://www.acmicpc.net/ Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 내가 작성한 코드 import sys, heapq read = sys.s..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 그래프 객체의 일부 쌍(pair)들이 '연관되어' 있는 객체 집합 구조 오일러 경로 한붓 그리기 모든 간선을 한 번만 방문하는 유한 그래프 NP-complete (Non-deterministic Polynomial time) problem 비결정론적 다항시간 해밀턴 경로 - 각 정점을 한 번씩만 방문하는 무향/유향 그래프 경로 - 오일러 경로는 간선 기준, 해밀턴 경로는 정점 기준 해밀턴 순환 - 해밀턴 경로이면서 원래 출발점으로 돌아오는 경로 외판원 문제 (TSP, Traveling Salesman Problem) - 해밀턴 순환 중 최단 경로 비교 해밀턴 경로 한 번만 방문하는 경로 해밀턴 순환 한 번만 방문하여 ..