1. 문제 출처 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 2. 풀이 모든 위치에서의 최대값을 구한다.. 이를 매번 처음부터 구하면 매우 오래 걸리므로 Dynamic Programming (동적 프로그래밍)을 사용한다..아래는 Botton_Top 형식으로 구현하였다. # 입력 n = int(input()) # 정수 삼각형 입력 tri = [[0]*idx for idx in range(1,n+1)] for idx in range(n): tri[idx] = list(map(int,input().split())) #..
1. 문제 출처 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 2. 풀이 모든 지점에서 다른 모든 지점까지의 최단경로를 계산하는 문제이다.. 딱 플로이드 워셜(이름부터 플로이드 이다...)을 위한 문제이다. 플로이드 워셜의 점화식을 이용하였다. Dab = min(Dab , Dak +Dka) 이를 코드로 표현하면 다음과 같다. for k in range(n): for a in range(n): for b in range(n): D[a][b] =..
1. 문제 출처 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 2. 풀이 가장 작은 두 카드 묶음 값을 더하는 것이 최적의 해이다. 일단은 다음과 같이 구현하였다. 하지만 시간 초과이다... 그래서 heap자료구조를 사용하여 시간을 줄였다... #입력 n = int(input()) cards = [] for _ in range(n): cards.append(int(input())) # 정렬 cards.sort() total_co..
1. 문제 출처 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 2. 풀이 연구소 문제와 비슷한 점이 있다. 연합하고 인구를 이동 시켜주는 작업을 BFS를 사용하여 구현하고 연합체의 개수가 전체 데이터의 수와 같으면 반복 했던 횟수를 반환한다... from collections import deque # 입력 N,L,R = map(int, input().split()) A = [] for _ in range(N): A.append..
1. 문제 출처 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 2. 풀이 일단 문제 대로 eval을 사용하여 구현해 보았다.. 특정 부분에서 잘못 계산되는 것 같다...반례를 찾을 수 없어서 DFS로 다시 구현하였다.(반례 찾으시면 말해주시면 감사하겠습니다.) from itertools import permutations # 입력 N = int(input()) num_list = list..
1. 문제 출처 https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 2. 풀이 그냥 구현을 해보자 # 시간 초과 N = int(input()) home_list = list(map(int,input().split())) def solution(): # 최소길이 구하기 min_dis = total_distance(home_list[0]) antenna = home_list[0] for idx in range(1,N): if min_dis > total_distance(ho..
1. 문제 출처 https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 2. 풀이 이 문제는 list.sort()대해 물어보는 문제인 것 같다. sort 함수에는 어떤 값을 기준으로 정렬한 것인지 key 파라미터를 통해 정할수 있다. N = int(input()) student_list = [] for _ in range(N): student_list.append(input().split()) # lambda통해 함수를 정의한다...
1. 문제 출처 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 2. 풀이 해당 문제는 1 ->2->....->K 순으로 바이러스가 움직이기 때문에 2차원 리스트을 queue처럼 이용하고자 하였으나, 그것보다 temp라는 3차원 배열에 코드와 같이 index + 1 과 같은 바이러스 번호를 가진 좌표를 모으고 2차원으로 펴준 queue를 생성한다. 그러면 자동적으로 바이러스 번호가 작은 순으로 나오게 된다. 예시)..
