Sangmun

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 기본적인 최소신장트리 문제와는 달리 마을을 두개로 분할해야하는 조건이 있는 문제이다. 최소신장트리 알고리즘으로 모든 마을을 연결하는 최소비용의 경로를 구해준 후 가장 비용이 높은 간선을 제거해주면 마을을 최소비용으로 2개로 분할하게 된다. import sys input = sys.stdin.readline def find_parent(parent,x): if ..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 백준 1916번 최소비용 구하기 문제의 변형으로 경로를 추가적으로 구해주면 된다. distance에 각 노드로 갈 수 있는 최소 비용뿐만 아니라 각 노드에서 이전에 방문한 노드를 추가적으로 넣어줘서 해결을 하였다. import heapq import sys input = sys.stdin.readline INF = int(1e9) n = int(input()) m ..

https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 기하학의 기본적인 문제라고 한다. 푸는 방법이 이미 널리 알려진 듯 하다. https://www.acmicpc.net/blog/view/27 점 3개의 방향성을 나타내는 CCW 세 점 P1(x1, y1), P2(x2, y2), P3(x3, y3)가 있을 떄, 점 3개를 이은 선분은 어떤 방향성을 나타내게 될까요? 11758번 문제..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 생성해야 하는 Matrix의 범위가 x축, j => y축 for i in range(a): for j in range(b): for each in polyomino: tmp_sum = 0 flag = 0 # 생성가능한 테트로미노를 순회하면서 임시로 합계값을 계산 for k in each: x = k[0] + i y = k[1] + j if 0

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net n의 케이스가 0 1: graph[a][b] = 0 # 결과 출력 for a in range(n): result = map(str,graph[a]) print(' '.join(result))

https://www.acmicpc.net/problem/14624 14624번: 전북대학교 전북대학교의 심볼은 균형과 조화, 지성과 이상을 향한 방향성과 목표를 나타낸다. 절제된 한국적 아름다움을 꾸밈없는 소박함과 여백을 통해 시각화하였으며, 심볼의 방향에 따라 한국적인 대 www.acmicpc.net ㅈ 문자를 찍는 과정에서 계속 '잘못된 출력형식입니다.' 라고 나오길래 뭐가 문제인지 봤는데 아래와 같은 사항을 고려하지 않고 코드를 짜서 그렇다. https://www.acmicpc.net/board/search/all/problem/14624 게시판 검색 - 1 페이지 www.acmicpc.net import sys input = sys.stdin.readline a = int(input()) if ..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 백준 2252번 줄 세우기 문제와 같이 기본적인 위상정렬 알고리즘을 연습해볼 수 있는 문제다. 백준 2252번 문제와 다른점은 2252번 문제는 가능한 정답 중에 하나만 출력해도 정답으로 인정이 되었지만 1766번 문제는 출력의 순서에 신경을 써야 한다는 점이다. 문제의 조건이 '가능한 낮은 난이도의 문제를 먼저 푸는것'임으로 위상 정렬상으로는 같은 순서여도 문제의 ..

https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 백준 4386번 문제와 같은 유형의 문제이다. 이번에는 n이 1000개라 2중 for문을 돌리면 시간초과가 나오지 않을까 싶었는데 다행이도 2중 for문으로 통과가 되었다. 중간에 이미 연결된 우주신의 좌표들은 입력받자마자 union_find 해버리면 최소비용계산때 알아서 계산대상에서 제외가 된다. import math import sys input = sys.stdin..