분류 전체보기

문제https://www.acmicpc.net/problem/2887백준 문제집 - 0x1B강 - 최소 신장 트리 알고리즘: 정렬, 최소 스패닝 트리풀이 좌표가 2차원이 아닌 3차원으로 주어진다. (x, y, z)간선비용은 두 행성간의 좌표차이 x1 - x2, y1 - y2, z1 - z2 중 가장 작은 것을 택한다.생각의 경로를 살짝 바꿔야하는 문제다. 모든 행성 쌍 간의 간선비용을 만들면 메모리 초과가 발생한다.행성이 N개일때, 총 C(N, 2) = N * (N-1) / 2 개의 간선이 만들어지기 때문... PyPy3로 제출해도 결과는 메모리 초과였고, 질문 게시판을 뒤져보던 중 해설 글을 발견했다.결론부터 말하자면 해결방법은 x 거리, y 거리, z 거리를 따로 계산한 간선들로만 구성하는것이었다.M..

문제https://www.acmicpc.net/problem/10423백준 문제집 - 0x1B강 - 최소 신장 트리 알고리즘: 최소 스패닝 트리풀이 1368: 물대기 문제와 비슷한 느낌이다.차이점은 물대기 문제는 물을 직접 연결할지 / 다른 논에서 끌어올지 선택할 수 있었다는것.반면 이 문제는 발전소가 이미 설치되어 있는 상태다. 선택권이 없다.따라서 트리 구성을 진행하기 전, 발전소가 설치된 노드들을 미리 처리해줘야한다.👉 이러면 '케이블이 연결되어 있는 도시에는 발전소가 하나만 존재한다'는 조건도 자연스레 처리된다.크루스칼의 경우: 발전소 노드들을 미리 같은 집합으로 처리프림의 경우: 각 발전소 노드들을 기준으로 MST들을 구성 1️⃣ 크루스칼 풀이크루스칼의 원리는 '두 노드가 같은 집합이 아님 →..

문제https://www.acmicpc.net/problem/1774백준 문제집 - 0x1B강 - 최소 신장 트리 알고리즘: 최소 스패닝 트리풀이 ❗ 염두해둬야할 조건이미 연결된 행성 쌍들은 MST(최소 신장 트리)를 보장하지 않음.모든 행성은 이어져있고, 행성간의 거리값(비용)이 따로 정해져있지 않음.비용: 행성 a, b 좌표간의 거리결과값은 실수형이어야 함. (두번째 자리에서 반올림) 처음엔 크루스칼로 풀었다가 프림으로 다시 풀어봤다.행성간의 거리값이 따로 지정되어있는게 아니다.즉, 모든 간선이 주어지는것과 마찬가지므로 프림으로 푸는게 더 효율적이다. 1️⃣ 프림 풀이🚨 "이미 연결된 행성들 != 최소 신장 트리에 포함된 행성"임을 주의해야한다.이걸 오해해서 삽질 좀 했다... 일단 모든 간선이 가..

문제https://www.acmicpc.net/problem/13418백준 문제집 - 0x1B강 - 최소 신장 트리 알고리즘: 최소 스패닝 트리풀이 체크해야할 조건피로도 = 오르막길 ^ 2오르막길: 0, 내리막길: 1 이 문제는 크루스칼로 푸는게 훨씬 편하고 효율적이다.(프림으로 풀고 나서 한탄함) 잘 보면 간선비용이 무조건 0 아니면 1이다.👉 크루스칼 사용 시 굳이 정렬해줄 필요가 없어진다.최적의 경우 / 최악의 경우를 한꺼번에 계산할 수 있다.👉 각각의 parent배열을 통해 1(내리막길) → 최적의 경우, 0(오르막길) → 최악의 경우로 넘겨주면 된다. 1️⃣ 크루스칼 풀이 (굿)# ⭐ 2. 크루스칼 알고리즘 풀이# 메모리: 91776KB / 시간: 720msfrom sys import std..

(i, j)가 포함되는 모든 경우를 구해야함.단, 연속 부분배열(끊어지지 않은 직사각형 형태)여야 한다.🚨 또한 아래의 공식은 0-based 기준임! 크기가 NxM인 행렬에서 (i, j)를 포함하는 부분배열의 갯수= (i+1) * (j+1) * (N-i) * (M-j) 아래는 추가 설명글임. 우선 가능한 경우는 아래와 같다.(i, j)가 좌상단 꼭짓점이 되거나, 그보다 위쪽에 있는 꼭짓점을 좌상단으로.(i, j)가 우하단 꼭짓점이 되거나, 그보다 아래에 있는 꼭짓점을 우하단으로. 1️⃣ (i+1): 윗부분 선택의 경우의 수(i, j) 또는 그보다 위쪽에 있는 칸 중 하나가 좌상단 꼭짓점이 되어야 하는 상황.(i+1)개의 선택지가 존재한다. N = 5, M = 8 인 배열이 있다고 가정해보자.만약 (1,..

문제https://www.acmicpc.net/problem/1647백준 문제집 - 0x1B강 - 최소 신장 트리 알고리즘: 최소 스패닝 트리풀이 답은 아래의 조건을 만족해야한다.두 개의 마을(집합)으로 분리각 마을은 최소 하나의 집으로 구성 나는 크루스칼을 사용해서 풀었는데, 내 첫 풀이는 이러했다.일단 최소 신장 트리를 만듦. 최소 신장 트리에 포함되는 간선 정보 (u v w)를 따로 저장.트리의 간선을 하나씩 제거해보며 최소비용 갱신.즉, MST에서 간선을 하나하나 제외시켜보며 새롭게 트리를 만들어본것이다.결과는 당연히 시간초과였다.지금 봐도 놀라운 풀이법이다. 왜 이렇게 풀었는지 의문이다;; (트리를 왜 다시 만들어보는건지...?😶‍🌫️) 해결방법은 아주 간단하다.구성된 간선 중 가장 비용이 ..