1. 문제 출처 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 2. 풀이 매번 이동시에 bfs를 이용하여 각 지점의 최소 거리를 구하고 이동하는 작업을 더 이상 이동할 수 있는 거리에 먹이가 없을 때 까지 반복한다... from copy import deepcopy from collections import deque # 입력 n = int(input()) space= [0] * n for i in range(n): space[i] =..
1. 문제 출처 https://www.acmicpc.net/problem/2941 2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net 2. 풀이 문자열을 이용한 단순 구현 문제이다.. # 크로아티아 문자 리스트 3글자인 것을 빼었다. cro_list =\ ["c=", "c-", "d-", "lj", "nj", "s=", "z="] # 입력 string = input() length = len(string) total_count = length idx = 0 # index가 l..
1. 문제 출처 https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 풀이 내림차순으로 정렬되어 있는 부분 최장 길이의 부분 수열을 구하는 문제이다..이는 LIS를 구하는 알고리즘과 매우 유사하다..이제 코드를 보자.. n = int(input()) soldier_list = list(map(int,input().split())) # LIS (최장 증가 부분 수열) 처럼 사용하기 위해 오름차순으로 변환 해준다. soldier_list..
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/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 2. 풀이 bfs(너비 우선 탐색)를 이용하여 구하였다. 제일 어려웠던점은 아이러니하게 알고리즘 구현이 아닌 시간 초과 문제 였다.처음에는 deque 대신 리스트에 pop()을 하는 형식으로 구현 하였으나 시간 초과가 발생하였다. 이를 deque 자료형을 불러와 popleft 를 대신 사용 하였더니 해결되었다..
1. 문제 출처 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 2. 풀이 처음에는 다음과 같이 치킨집의 개수가 M개가 되는 모든 경우의 수를 재귀로 구하였다. 하지만 시간 초과 되었다... # 입력 받기 N,M = map(int, input().split()) city = [0 for _ in range(N)] result = [] for idx in range(N): city[idx] = list(map(int, inp..
