1. 문제 출처 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 2. 풀이 간단한 bfs문제이다. from collections import deque # 입력 m,n,k = map(int,input().split()) # 상하좌우 이동 dx = [0,0,-1,1] dy = [-1,1,0,0] # 방문 리스트 visted = [[0]*m for _ in range(n)] # 너비 리스트 area_list = [] # 직사각형..
1. 문제 출처 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 2. 풀이 기초적인 BFS문제 이지만 , 가로 세로가 리스트에서는 [세로][가로]로 되어있어 헷갈렸었다... 조심하자. from collections import deque # 테스트 케이스 개수 t = int(input()) # 이동 경로(상하좌우) dx = [0,0,-1,1] dy = [-1,1,0,0] for _ in range(t): # 팔요 벌레 개수 worm = 0 # 가로,세로,배..
1. 문제 출처 https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 2. 풀이 그냥 문제대로 구현해 본다. # 입력 n = int(input()) length = int(input()) S = input() p = "IO"*n+"I" idx = 0 count = 0 # I일 때 p와 비교해서 똑같으면 count+=1 while idx < length: if S[idx] == "I"..
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/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/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 를 대신 사용 하였더니 해결되었다..
