블로그

- 난이도 : 실버 1- 시간제한 : 1초 (추가 시간 없음)- 메모리 제한 : 1024MB 문제홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다. 100,000 이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다.  이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자. 입력첫째 줄에 정수 N(1둘째 줄에는 a1, a2, ... , an이 주어진다. (1 출력조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다. 가장 처음에 생각했던 방식은 입력된 a 리스트의 첫 값부터 반복문을 돌면서 ..

1. 신장 트리(Spannging tree) 그래프에서 모든 정점이 서로 연결이 되며 싸이클이 존재하지 않는 그래프 신장 트리들 중에서 가중치의 합이 최소가 되는 신장 트리를 최소 신장 트리(Minimum Spanning Tree, MST)라고 함 2. 크루스칼 알고리즘(Kruskal Algorithm) 그리디(Greedy) 알고리즘 그래프 내의 모든 정점을 가장 적은 비용으로 연결하기 위해 사용 알고리즘 동작 과정 간선 데이터를 비용(가중치)에 따라 오름차순으로 정렬 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인 사이클이 발생하지 않는 경우 최소 신장 트리에 포함 사이클이 발생하는 경우 포함시키지 않음 모든 간선에 대해 2. 과정 반복 def find(parent, i): # unio..