CodeAngie

문제그래프가 주어졌을 때 최소 스패닝 트리(최소 신장 트리)를 구하고 그의 가중치를 출력하는 문제이다.풀이크루스칼 알고리즘을 사용하여 가중치를 계산한다.간선(edge)을 가중치가 작은 순으로 정렬한다.부모 노드를 자기 자신으로 초기화한다.가장 작은 가중치부터 순서대로 노드를 서로 연결한다.노드를 서로 연결한다는 것은 두 노드가 같은 루트를 갖게 한다는 의미이다.즉 부모 노드가 다를 경우, 아직 서로 연결이 안 된 노드이기에union을 통해 부모 노드를 동일하게 만들어 줌으로써 서로 연결하는 것이다.Python 코드import syssys.setrecursionlimit(10**6)input = sys.stdin.readlinev,e = map(int,input().split())edges = [list(..

1. 신장 트리 (Spanning Tree)신장 트리는 모든 노드끼리 연결되어 있는 (모든 노드 간에 경로가 존재하는) 연결 그래프가 주어졌을 때, 모든 노드가 연결되지만 사이클이 존재하지 않는 부분 그래프를 의미한다.그래프의 최소 연결 부분 그래프라고 할 수 있다.여기서 최소 연결이란, 간선의 수가 최소가 되는 부분 그래프를 의미한다.n개의 노드가 있을 때 간선의 수는 n-1이 된다.2. 최소 신장 트리최소 신장 트리는 연결 그래프가 주어졌을 때, 가능한 신장 트리 중 가중치 합이 가장 작은 트리이다.2.1. 최소 신장 트리의 특징간선의 가중치 합이 최소여야 한다.노드가 n 개일 때, 간선은 반드시 n-1 개다. (신장 트리 특징)사이클이 존재하지 않는다. (신장 트리 특징)3. 크루스칼 (Kruska..

문제 5*3 개의 전구를 통해 0~9까지의 숫자를 표현할 수 있을 때, 전구가 망가졌을 수도 있음을 가정하고, 켜진 전구들을 살펴보아 만들 수 있는 숫자들의 평균을 구하는 문제이다. 층 안내판의 크기는 5*3 판을 여러 개 이어 붙인 형태이며 판 사이의 꺼진 전구가 존재한다. 풀이 먼저 문제에서 주어진 0~9까지의 표현을 가지고 5*3 판 위의 어떤 전구가 켜졌을 때 어떤 숫자를 만들 수 있는지 판별해야 한다. 예를 들어 5*3 판을 기준으로 (0,0) 위치의 전구가 켜지면 만들 수 있는 숫자들(0,2,3,4,5,6,7,8,9)을 저장한다. 같은 간격으로 숫자가 있기에 (i, j+k*4)를 통해 동일한 위치의 전구들을 확인할 수 있다. 각각의 판이 만들 수 있는 숫자들을 추출한다. 만약 (3,0) 위치의..

문제 0에서 n까지 숫자 한개로 이루어진 n+1개의 집합이 있다. 합집합 연산(0)과 두 원소가 같은 집합에 포함되는지 여부를 확인하는 연산(1)을 수행할 때, 같은 집합에 포함되면 yes, 아니면 no를 출력하는 문제이다. 연산은 연산종류(0,1), a원소, b원소 순서대로 입력된다. 풀이 이 문제는 각 원소가 포함된 집합의 대표 번호(부모 노드)를 저장함으로써 합집합 연산에서는 두 원소의 부모 노드를 더 작은 번호로 일치시켜주고 (union) 두 원소의 집합이 같은지 확인하는 연산에서는 부모 노드가 동일한지 확인하면 되기 때문에 (find) 분리집합 알고리즘으로 해결할 수 있다. 먼저 부모 노드들을 담을 parent(p) 리스트를 생성한다. 초기 부모 노드는 각 집합에 담겨있는 숫자의 번호로 초기화한..

백준 문제를 풀다 보면 종종 리스트 안의 행과 열을 바꿔야 하는 경우가 생긴다. 하지만 코딩테스트에서는 보통 numpy를 사용할 수 없다. 간단한 내장함수를 사용하여 전치행렬을 구현하는 방법을 알아보자. 1. zip for문을 실행할 때 zip 함수로 열의 요소들을 묶어줄 수 있다. arr = [list(temp) for temp in zip(*arr)] 2. map과 zip map 함수를 사용하면 for문을 거치는 것보다 더 빠르게 전치행렬을 만들 수 있다. arr = list(map(list,zip(*arr)))

코딩테스트 문제를 풀다 보면 문제를 입력받을 때, 이차원 배열을 받을 때가 많다. for문을 통해서 배열을 입력받을 때 빈 리스트에 한 줄씩 append 해줄 수 있지만, list comprehension을 이용하면 쉽게 한줄로 입력받을 수 있다. 개인적으로 입력을 받거나 행렬을 생성할 때 간단하게 리스트를 표현할 수 있기 때문에 특히 많이 사용하게 되는 것 같다. 표현식 + for문 형식 result = [표현식 for 변수 in 리스트] # 예시 # 1차원 배열 # 숫자를 순차적으로 입력받을 때 result = [] for i in range(n): result.append(int(input())) # list comprehension result = [int(input()) for i in rang..

문제 N개의 섬이 존재하고 이들이 n-1개의 다리로 어떤 두 섬이든 이동할 수 있도록 연결되어 있다. 이때 다리 하나가 파괴되었고 새로운 다리를 연결해야할 때, 어떤 두 섬 사이에 다리를 연결하면 어떤 두 섬이든 이동할 수 있게 되는지 알아내는 문제이다. 풀이 이 문제에서 기존에 어떤 두 섬이든 이동할 수 있었다는 것은 모든 섬들이 하나의 집합을 이루고 있다는 뜻이다. 즉 모두 같은 부모 노드를 갖고 있다는 의미이다. 여기서 다리 하나가 없어졌다는 것은 1개의 집합이 끊어져 2개의 집합이 되었다는 것이다. 따라서 두 개의 집합의 섬(노드) 하나씩을 연결해주면 다시 1개의 집합으로 만들 수 있다. 즉, 두 집합의 부모 노드 끼리 연결해주면 되는 것이다. Union-Find 알고리즘을 사용해 두 개의 분리된..