문제 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
문제 www.acmicpc.net/problem/1949 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 www.acmicpc.net 풀이 n번 마을을 우수 마을로 선정하면 인접한 마을은 모두 우수 마을로 선정할 수 없다. 또한, n번 마을을 우수 마을로 선정하지 않은 상태에서 인접한 마을을 모두 우수 마을로 선정하는 것이 최적해를 보장하지는 않는다. 이 문제는 서브트리의 가중치의 합을 구하는 문제이다. 이를 dfs와 동적계획법으로 풀 수 있다. dp[n][1]은 n번 마을을 우수마을로 선정했을 경우에 우수 마을의 주민 ..
