매일 조금씩

문제 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 크루스컬로 풀면 될 것 같은데 간선 정보가 없다. 간선을 내가 만들어야 하는데 모든 경우의 수를 고려하면 시간초과 각이다 비용이 각 양쪽 좌표 별 차이 값의 최소값이므로 좌표를 분리해서 간선을 만든다. x, y, z 각 좌표와 노드 번호를 저장 후 좌표 값 오름차순으로 정렬 좌표 별로 한쌍 씩 묶어서 비용과 노드를 edges 리스트에 저장 edges 리스..

문제 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 floyd 알고리즘 소스코드 n = int(input()) m = int(input()) arr = [[1e9]*(n+1) for _ in range(n+1)] for i in range(1, n+1): for j in range(1, n+1): if i == j: arr[i][j] = 0 for _ in range(m): i, j, cost = map(int, input().split..

문제 https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 LIS 알고리즘 사용. DP방식으로 이중 For문 사용하여 구현 https://gom20.tistory.com/91 [Algorithm] LIS 알고리즘 (최장증가수열 알고리즘) LIS 알고리즘이란? LIS 알고리즘 (Longest Increasing Subsequence Algorithm) 은 최장증가수열 알고리즘으로 증가하는 원소들의 가장 긴 부분집합을 찾는 알고리즘이다...

문제 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 초반에는 작은 수끼리 묶으면 될거라 생각해서 단순 sort하여 더하는 코드를 작성하였다. 근데 틀렸다고 나온다. 왜냐면 동일한 숫자 카드가 존재할 수 있기 때문이다. 예를 들어 3 3 3 3 4개의 숫자카드를 순차적으로 더해나간다면 3+3 = 6 6+3 = 9 9+3 = 12 27로 오답이 나온다. 이 경우 3+3 = 6 3+3 = 6 6+6 = 12 24가 정답이다. 결..

문제 https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 풀이 중간값에 위치한 집에 안테나를 설치하면 안테나와 집간 거리의 합이 최소가 된다. 소스코드 n = int(input()) data = list(map(int, input().split())) data.sort() if n == 1: print(data[0]) elif n % 2 == 0: print(data[int(n//2-1)]) else: print(data[int(n//2)])

문제 https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 풀이 Python 다중 정렬 sort 라이브러리 사용 labmda로 튜플의 몇 번째 원소부터 정렬할 지 명시 오름차순은 그대로, 내림차순은 - 붙여서 소스코드 n = int(input()) a = [] for _ in range(n): data = list(input().split()) a.append((data[0], int(data[1]), int(data[2]), ..

문제 https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 풀이 combnation으로 3개의 장애물 좌표 조합 구하기 장애물 설치 후 teacher 위치 좌표 반복문 돌려서 dfs 실행 감시영역 내의 학생수 count dfs 종료 후, 감시된 학생 수가 0명이면 'YES' 출력하고 프로그램 종료 소스코드 from itertools import combinations n = int(input()) arr = [] teachers = [] s..

문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 재귀함수 사용 소스코드 n = int(input()) nums = list(map(int, input().split())) opers = list(map(int, input().split())) # +,-,*,/ max_result = -1e9 min_result = 1e9 def dfs(nums, opers, total, k, s..

문제 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 풀이 최소힙으로 낮은 번호의 바이러스부터 증식시켰고, 모든 증식이 끝난 후에 시간을 증가 시킨 후 다음 바이러스를 큐에 넣었다. 다른 답안을 보니 virus를 소팅하고 deque를 이용해 정석적인 BFS 방식으로 풀 수 있었는데 좀 돌아서 간 것 같다. 소스코드 from collections import deque import heapq n, k = map(in..

문제 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 BFS로 최단 거리를 만족하는 노드를 저장한다. 최단 거리 이후의 도시는 방문할 필요 없으므로 큐에 넣지 않는다 소스코드 from collections import deque import sys input = sys.stdin.readline # n노드, m간선, k최단거리, x시작노드 n, m, k, x = ma..