문제 www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 입력부에서 가장 높은 지역의 높이(MAX)를 저장한다. 그 후 강수량을 1부터 MAX-1까지 정해서 DFS를 진행한다. 이때, 강수량보다 높은 지역에 한해서만 탐색을 진행하고, 탐색이 끝나면 비교를 통해 안전 영역의 최댓값을 구한다(비가 안 오는 경우도 존재하므로 최댓값은 1이상이다). 코드 import sys sys.setrecursionlimit(10**9) def dfs(y, x, r): visited..
문제 www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 풀이 DFS로 풀이했다. 각 종이를 검사하며 종이가 같은 수로 되어있는지 여부를 확인하고, 만약 그렇지 않다면 9개의 크기로 자르고 다시 해당 종이의 첫번째 지점에서 탐색을 시작한다. 코드 import sys sys.setrecursionlimit(10**9) dy = [0, 0, 0, 1, 1, 1, 2, 2, 2] dx = [0, 1, 2, 0, 1, 2, 0, 1, 2] def dfs(y,..
문제 www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 풀이 파이썬에 내장된 힙(heap)모듈을 사용하여 풀 수 있다. 이것은 기본적으로 min heap이므로 약간의 처리가 필요하다. 삽입 시 리스트의 형태([-x, x])로 삽입하는 방식으로 max heap을 구현할 수 있다. 파이썬에서 정렬은 첫번째 원소를 기준으로 이루어지기 때문이다. 코드 import sys import heapq as hq def get_max(x): if heap:..
문제 www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 풀이 주어진 배열에서 구할 수 있는 순열을 모두 구한 뒤, 각 순열에 식을 적용하여 최댓값을 구한다. 코드 import sys, itertools def cal_max(candi): result = 0 for i in range(1, len(candi)): result += abs(candi[i-1] - candi[i]) return result n = int(sys.stdin.readline().strip()) arr..
문제 www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 이전에 풀었던 베르트랑 공준과 비슷한 문제이다. 아래와 같이 소수를 구하는 방법은 O(n^2)의 시간을 가지므로 n이 최대 1,000,000이 될 수 있는 이 문제에 적합하지 않다. # O(n^2)의 시간 n=100 def isPrime(a): if(a
