Dev_Diary

https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net CCW 알고리즘을 활용하면 풀 수 있는 문제입니다. def solution(x1, y1, x2, y2, x3, y3, x4, y4): # CCW 알고리즘은 기본적으로 주어진 점선들의 회전방향을 알 수 있음 # 어떤 직선을 기준으로 두 점이 양방향에 있으면 직선과 각 점을 이었을 때 회전방향은 반대임 # 각 선분을 기준으로 나머지 선분의 각 점이 이루는 회전방향이 모두 다르면 # 각 선분을 이루는 점은 나머지 선분을 ..

https://www.acmicpc.net/problem/25308 25308번: 방사형 그래프 게임 캐릭터의 능력치를 한 눈에 보기 좋게 나타내는 방법으로 방사형 그래프가 있다. 캐릭터는 8개의 능력치를 갖고 있고 각 능력치를 $a_1, a_2, \cdots, a_8$이라고 하면, 그래프는 팔각형 형태이고 www.acmicpc.net 특정 인덱스를 기준으로 왼쪽과 오른쪽의 각도 합을 통해 풀 수 있는 문제였습니다. from itertools import permutations import math def solution(data_list): # 데이터를 조합 permute_data = permutations(data_list, 8) # 카운트 count_convex = 0 # 인덱스를 돌아가면서 판단 ..

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 CCW 알고리즘을 사용하면 쉽게 풀 수 있습니다. import math def solution(data_list): # x, y 좌표 분리 x_list = [] y_list = [] for x, y in data_list: x_list.append(x) y_list.append(y) x_list.append(data_list[0]..

https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 외적을 통해 넓이를 구하면 쉽게 풀 수 있습니다. def solution(N, data_list): # 데이터 x 좌표 y 좌표 분리 x_list = [] y_list = [] for x, y in data_list: x_list.append(x) y_list.append(y) x_list.append(x_list[0]) y_list.append(y_list[0]) # 외적 합 sum_cross = 0 # 외적 for i ..

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 좌표와 좌표간의 거리를 계산해 가중치로 둔 뒤 크루스칼 알고리즘을 통해 풀 수 있었습니다. import heapq import math def solution(n, data_list): # 거리 맵 dist_map = [[0 for __ in range(n)] for _ in range(n)] # 거리 맵 구성 for i in range(len(data_list)-1): for j in range(..

https://www.acmicpc.net/problem/1197 최소 스패닝 트리 알고리즘 중 하나인 크루스칼 알고리즘을 통해 쉽게 풀 수 있습니다. import sys import heapq def solution(V, E, data_list): # kruskal weight_sum, tree, union_list = kruskal(V, E, data_list) print(weight_sum) # kruskal def kruskal(V, E, data_list): # 트리, tree[i] = [i번째 노드의 자식들] tree = [[] for _ in range(V+1)] # 유니온 리스트 union_list = list(range(V+1)) # 큐 queue = [] # 데이터를 큐에 삽입 for ..

https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 사실 최소 신장트리를 구성하게 되면 간선의 수는 노드의 수 - 1 이 되므로 그냥 N-1 을 리턴해도 정답이 됩니다. 하지만 크루스칼과 프림 알고리즘으로도 구현해봤습니다. from collections import deque def solution(N, M, data_list): # 프림과 크루스칼 모두 해보자 # 유니온 리스트 union_list = list..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 유니온 파인드 알고리즘 문제입니다. 우선 주어진 데이터를 통해 트리를 구성한 뒤 유니온 파인드 알고리즘을 통해 루트노드를 병합했습니다. from collections import deque def solution(N, M, data_list, plan): # 루트 노드 리스트 union_list = list(range(N+1)) # 방문 리스트 visited = [1 for _ in range(N..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 투포인터를 사용해 풀 수 있는 문제입니다. import sys def solution(N, data_list): # 데이터 정렬 data_list = sorted(data_list) # 투포인터 left = 0 right = N-1 # 비교 값 value = int(2e9) # 포인터 값 left_value = data_list[left] right_value =..

https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 시간이 충분하므로 플로이드-워셜 알고리즘을 통해 모든 시작점에서 모든 끝점까지의 거리를 구한 뒤 시작-끝 거리와 끝-시작 거리를 더한 최솟값을 구해주면 됩니다. import sys def solution(V, E, data_list): # 최대 거리 inf = float('inf') # 거리 맵 dist_map = [[inf for _ in range(V+1)] ..