(x1, y1)과 (x2, y2)로 주어지는 두 좌표에 대해 x1 <= x2, y1 <= y2가 성립하며 표는 최대 1024 * 1024사이즈이고 최대 100,000번의 합을 구해야 한다.
무식하게 즉 브루트한 방법으로 푼다면 M번의 트라이에 대해 그 때마다 반복문을 돌며 처리할 수 있다. 그러나 이 방법으로 한다면 최악의 경우 100,000 * 1024 * 1024번의 연산을 해야 하며, 주어진 시간인 1초 내에 통과할 수 없을 것이다.
매번 새로 합을 구하는 것이 아니라 이전에 구한 값을 재활용하는 DP를 통해 문제에 접근해야 한다는 생각이 들었다. 그러나 K번째 트라이에 대한 답을 구할 때 이전 트라이에서 구한 답을 이용해 구할 수 있을지는..
그러다가 풀이방법이 떠올랐다. 누적합을 이용하는 것이다. sum[r][c]가 (0, 0)에서 (r, c)까지의 영역의 합을 의미한다고 하고 (0, 0)부터 (N, N)까지의 모든 sum값을 구해뒀다고 하자. 그렇다면 이를 활용해 임의의 두 좌표 (x1, y1)부터 (x2, y2)의 영역의 합을 sum값을 이리저리 활용해 구할 수 있다! 이 sum값을 구할 때 내가 생각한 방법은
sum[r][c] = sum[r - 1][c] + r번째 행에서 1번 ~ c번값까지의 누적합 이었지만, 다른 사람들의 풀이를 보니
여러 카드더미들이 주어졌을 때, 모든 카드가 합쳐진 더미를 만들 때 비교횟수는 어떤 순서로 카드들을 합쳐나가는지에 따라 달라진다. 이 때 최소 비교횟수는 몇인가?
순서는 임의대로 할 수 있기 때문에 카드가 나열된 순서와는 관계가 없다. 또한 카드더미의 개수가 1개만 주어질 때도 있는데 이 경우 비교횟수는 0이 됨을 알아두자.
1. 일단, 무식하게 풀어본다면?
나올 수 있는 모든 비교횟수합들을 구해서 가장 작은 값을 취하면 된다. n개의 카드더미가 있을 때, 이 중 두 더미를 골라 합치므로 가짓수는 nC2개. 이렇게 두 개를 골라 합치면 하나의 카드더미가 만들어지는 것이므로, 남은 카드더미는 n-1개가 되며 여기서 다시 2개를 골라 합친다. 즉 나올 수 있는 모든 비교횟수합은 nC2 * n-1C2 * n-3C2 * ...번이며 n은 최대 100,000이므로 문제의 제한시간인 2초 내에 통과하는 것은 힘들다. 즉 다른 방법을 모색해볼 것.
2. dp나 그리디를 의심해보자
>> 2-1. 최적부분구조를 가지는가?
Yes. n개의 카드묶음들로부터 나올 수 있는 최소비교횟수는 n개의 카드 중 2개를 골라 얻는 비교횟수와 그로부터 만들어지는 n-1개의 카드묶음들로부터 나오는 최소합 중(즉 nC2개가 있을 것이다) 가장 작은 값이 된다.
ex) 1번 더미와 2번더미를 합치고 남은 n-1개의 카드더미로부터 얻는 최소값2번 더미와 3번더미를 합치고 남은 n-1개의 카드더미로부터 얻는 최소값이런 것들 중 가장 작은 값이 문제가 요구하는 답이 됨
>> 2-2. 중복되는 구조가 있는가?
Sometimes Yes. k개 만큼의 카드더미가 있다고 할 때, 각각의 카드더미들의 구성이 같다면 중복된다고 판단가능. 그러나 이렇게 중복되는 상황이 항상 나올 것이라고 보장할 수 없다. 가끔 중복되는 정도라고 생각된다.
즉 DP로 접근하는 것은 그닥 효율적으로 보이진 않는다.
>> 2-3. 합법적으로 시작하는 그리디 의심. 탐욕적 선택 속성이 있는가?
사실 이 문제는 그리디 티를 팍팍 내는 문제라고 생각되며, 직관적으로 가장 작은 카드더미들부터 합치는 것이 좋을 것이라는 냄새도 솔솔 풍기는 문제지 않나 싶다. 문제에서 보여주는 예시부터 가장 작은 애들부터 합치니까. 실제로 이 문제는 가장 작은 카드더미부터 합쳐나가야 정답을 얻는다. 그러나 실전도 아니고 이렇게 연습 삼아 푸는 문제들에선 엄밀하게 그리디임을 검증하고 넘어가는 것이 좋을 것이다.그럼, 왜 그리디라고 생각했을까?
근거1. 탐욕적 선택 속성이 있다 즉 어떤 페이즈에서 내린 선택이 그 다음 페이즈의 선택에 영향을 주지 않는다.
내가 이번 페이즈의 선택에서 가장 작은 걸 취했다고 해서 다음 선택에서 가장 작은 걸 취할 수 없는 그런 상황은 없다. 늘 가장 작은 걸 취할 수 있다. 그리디 속성이 있다면 이렇게 내가 현재 내리는 선택이 이후의 선택에 영향을 주지 않는다. 살짝 헷갈렸던 것은, 내가 지금 선택하는 카드더미에 따라 다음 페이즈에 선택하는 카드더미의 구성이 달라지므로 "이 상황은 내가 지금 내리는 선택이 뒤에 영향을 주는 상황이 아닌가?"했지만, 정확히는 뒤에 내리는 선택에 영향을 주지 않는다가 맞지 않나 싶다. 이 문제를 통해 배웠음. 예를 들어 1309번 동물원 문제의 경우, 내가 왼쪽에 있는 칸에 사자를 배치하기로 했으면 다음 줄의 왼쪽 칸에는 사자를 배치할 수 없다는 식으로 내가 현재 내린 선택이 뒤의 선택에 영향을 주는 부분이 존재했다. 암튼 간에 이 1715번 카드 정렬하기 문제는 내가 현재 페이즈에서 내리는 선택에 다음번 페이즈에서 내리는 선택에 영향을 주지 않으므로 그리디 속성이 있다고 볼 수 있다.
근거2. 그리디는 한 번의 선택들이 그 자체로 부분문제가 된다.
스터디에서 배운 그리디의 특성이다. 제일 작은 것 2개를 고른다고 할 때, 내가 고른 두 개의 카드더미들로 인해 하나의 카드더미가 새로 만들어지고, 그 n-1개의 카드더미들로부터 또 2개를 고른다는 부분문제가 된다. 즉 한 번의 선택들이 그 자체로 부분문제가 되는 속성 역시 찾아볼 수 있었다.
3. 그렇다면, 그리디의 정당성 검증은?
지금 나는 처음에 가장 작은 카드더미들을 고른 경우를 포함하는 최적해가 있다고 생각하고 있으며, 이를 검증해야 한다. 귀류법을 통해 수학적?으로 검증해보자.
n장의 카드묶음이 있을 때, 매 선택마다 임의의 카드묶음 2개를 골라 합쳐나갔을 때 나오는 각각의 비교횟수들이 있을 것이고 총 n-1번의 비교를 한다. 이 때 가장 작은 카드묶음 2개를 골라나갈 때 나오는 비교횟수들의 집합을
G = {g1, g2, g3, ..., g(n-1)}
이라 하고, 이 문제의 최적해의 비교횟수 집합을
O = {o1, o2, o3, ..., o(n-1)}
이라 해보자. 이 때 G가 이 문제의 최적해가 아니라면 sum(G) > sum(O)가 되야 한다. 그러나 실제로는 G가 가장 작은 카드묶음이므로 sum(G) < sum(O)가 되니 가정에 모순이다. 따라서 G는 이 문제의 최적해이다.
4. 끝나지 않은 문제
작은 애들부터 골라야 한다는 것을 증명했으니, 이젠 코드만 세우면 된다. 그러나 문제가 있다. 우선 오름차순으로 카드를 정렬하고 거기서 카드더미를 2개씩 골라 합쳐나갈 텐데, 이렇게 합쳐지는 카드를 그대로 두면 전체 카드더미가 오름차순 유지가 되지 않는다. 따라서 매번 고를때마다 다시 정렬을 해주거나 적절한 위치에 새로 만들어진 카드더미를 삽입해야 한다. 그러나 정렬의 시간복잡도는 O(nlogn)이고 삽입(리스트의 insert메소드)의 시간복잡도는 O(n)이므로, 정렬이 아니라 계속 합칠 때마다 적절한 위치에 삽입을 해준다고 해도 러프하게 생각하면 최악의 경우 O(n^2)만큼의 연산을 해야 하게 되며 n은 최대 100,000이므로 이 경우 시간초과가 날 것이다). 어떻게 해야 하는가..
5. 해결책은 heapq : 우선순위 큐
일반적인 큐는 FIFO를 만족하지만, 우선순위 큐는 그와 달리 데큐를 할 때 우선순위가 높은 애들이 먼저 나온다. 즉 이 문제에선 가장 작은 카드더미들에게 높은 우선순위가 있다고 하여 우선순위 큐를 쓸 수 있다. 파이썬에서 heapq의 pop의 시간복잡도는 O(1), push의 시간복잡도는 O(logn)으로 전체 시간복잡도는 최대 O(nlogn)정도가 되고 100,000이어도 160만번 정도의 연산만 하면 되므로 시간 내에 통과가 가능해진다. 따라서, 드디어 코드는 다음과 같다.
import heapq
N = int(input())
data = []
for _ in range(N):
heapq.heappush(data, int(input()))
answer = 0
while len(data) != 1:
min1 = heapq.heappop(data)
min2 = heapq.heappop(data)
heapq.heappush(data, min1 + min2)
answer += (min1 + min2)
print(answer)
무식하게 풀어본다면 어떻게 풀 수 있을지 어림짐작을 하려고 했는데, 못 했다. 어떻게해서 풀 수 있을지는 구상이 되는데, 그 방법을 토대로 어떻게 어림짐작을 할 수 있을지를 모르겠었다. 직관적으로 떠오른 방법은 주어진 알파벳들을 자음과 모음들로 구분하고, 자음에서는 2개 이상을 고르는 모든 조합, 모음에서는 1개 이상을 고르는 모든 조합을 서로 매핑시켜서 암호를 만드는 것이었다. 일단 떠오르는 무식한 방법(비단 브루트포스 방식이 아니더라도)에 대한 어림짐작이 잘 안되면 일단 그 방법으로 풀어보는 것도 하나의 방법이라고 한다.
파이썬에서는 순열/조합에 관해서 쓸 수 있는 편리한 라이브러리가 있다. 이를 활용하기로 했으며, 코드는 다음과 같다.
from itertools import combinations
import sys
L, C = map(int, sys.stdin.readline().split())
# data[0] = 자음, data[1] = 모음
data = [list(map(str, sys.stdin.readline().split())), []]
password_list = []
# 자음 모음 분리 .
for ch in ['a', 'e', 'i', 'o', 'u']:
if ch in data[0]:
data[1].append(ch)
data[0].remove(ch)
# 주어진 알파벳들로 암호를 만들 수 있을 경우는 자음이 2개, 모음이 1개 이상인 경우
if len(data[0]) >= 2 and len(data[1]) >= 1:
# i는 모음의 개수를 의미
for i in range(1, len(data[1]) + 1):
if L - i >= 2:
vowels = list(combinations(data[1], i)) # 가능한 모든 모음의 조합
consos = list(combinations(data[0], L - i)) # 그로부터 생기는 가능한 모든 자음의 조합
for v in vowels:
for c in consos:
# 모음의 조합과 자음의 조합들을 합쳐 비밀번호만들기
password = ''.join(sorted(list(v + c)))
password_list.append(password)
# 비밀번호들 사전순 정렬
password_list.sort()
for i in password_list:
print(i)
모음은 총 5개까지 고를 수 있는데, 주어지는 알파벳들이 중복되어 주어지는 것이 없다고 했으므로 모음은 0개 ~ 5개까지 있을 것이다. 따라서 자음 / 모음을 분리했을 때 모음이 1개 이상, 자음이 2개 이상 있어야지 암호를 만들 수 있으므로 이에 대한 예외처리를 해준다.
combinations()의 파라미터로 첫 번째는 반복 가능한 것(배열처럼), 두 번째는 요소의 개수를 넣어주면 첫 번째로 받은 반복 가능한 객체에서 두 번째 파라미터로 받은 개수만큼의 조합을 튜플 형태들로 반환해준다. 주어진 알파벳들로 L글자의 암호를 만든다고 할 때, 모음의 개수를 정했다면 자음의 개수는 L - 모음의 개수이므로 이를 활용해 가능한 모음의 조합과 자음의 조합들을 만들어주고 이들을 합치고 정렬하여 알파벳 순서로 된 비밀번호를 만드는 식으로 코드를 짰다.
24번째 줄, if L - i >= 2를 처음엔 넣어주지 않아 틀렸다고 나왔다. 자음은 2개 이상, 모음이 1개 이상 있어도 모음의 개수에 따라 암호를 못 만들 수도 있는 상황이 있음을 간과한 것이었다. 예를 들어 자음이 3개, 모음이 3개 있을 때 4글자짜리 암호를 만들라고 했다고 하자. 자음이 2개 이상 모음은 1개 이상있는 상황이니 비밀번호를 아예 못 만드는 상황은 아니지만, 모음이 3개인 비밀번호는 만들 수 없다! 이 경우 자음은 1개만 써야 4글자짜리 비번을 만들 수 있는데, 문제의 조건 상 자음은 2개 이상 써야 하기 때문이다. 즉 이에 대한 예외처리를 해줘야했다.
2차원 배열 형태로 필드가 주어졌을 때, 비의 양을 0부터 100까지 해주면서 생기는 영역의 개수를 하나하나 세보면 된다. 영역의 개수를 세는 것은 N * N짜리 필드의 칸들을 하나하나 순회하면서 센다고 할 때, N으로 가능한 최댓값은 100이므로 이론상 최악의 경우 100 * 100 * 100 = 100만번 정도의 계산을 하게 된다. 문제의 제한시간은 1초인데 파이썬은 1초 내에 충분히 100만번의 연산이 가능하므로 통과할 수 있으리라 어림짐작이 가능하다.
조금만 더 최적화시켜서, 비의 양을 굳이 0부터 100까지 순회할 필요는 없다. 비의 양이 0이면 안전영역의 개수는 무조건 1이고(각 영역의 높이는 무조건 1이상이므로), 비의 양이 주어진 필드의 최고높이가 되는 순간 모든 지역이 물에 잠겨 안전영역의 개수는 0이 된다. 따라서 비의 양을 0 ~ 100까지가 아니라 1 ~ 필드에서 주어진 최고높이까지만 순회하면 됨
import sys
sys.setrecursionlimit(10000)
N = int(sys.stdin.readline())
height, checked = [], []
for _ in range(N):
height.append(list(map(int, sys.stdin.readline().split())))
checked.append([True] * N)
# 인접한 영역들 싹 다 표시하기
def checkArea(N, r, c):
checked[r][c] = False
directions = [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]
for nr, nc in directions:
if (0 <= nr < N) and (0 <= nc < N) and checked[nr][nc]:
checkArea(N, nr, nc)
# 빗물의 높이가 rain으로 주어졌을 때 안전영역 개수 계산
def calculate(N, rain):
areas = 0
# 잠기는 영역들 구하기 - False로 표현
for r in range(N):
for c in range(N):
if rain >= height[r][c]:
checked[r][c] = False
else:
checked[r][c] = True
# 안전 영역 개수 구하기
for r in range(N):
for c in range(N):
if checked[r][c]:
checkArea(N, r, c)
areas += 1
return areas
# 안전영역의 최대 개수 리턴
def solution(N):
# 답이 될 수 있는 값의 최소 = 1 (각 지점 높이 최소 = 1, 빗물 최소높이 = 0이므로)
answer = 1
for rain in range(1, 101):
areas = calculate(N, rain)
# 만약 특정 빗물 높이에 대해 안전영역이 0이면 break -> 빗물이 height의 최댓값과 같아진 거니까
if areas == 0:
break
if answer < areas:
answer = areas
return answer
print(solution(N))
인접한 영역을 어떻게 셀 것인가에 대해 고민해본 문제다. 이는 재귀를 통해 방문한 지역들을 모두 방문처리(본 코드에선 cheked배열을 이용)하는 것으로 구현했다. 어떤 지점으로부터 상하좌우방향으로 1칸씩 이동하며 순회해야 할 때, checkArea함수에서 쓴 것처럼 방향배열을 설정해두고 사용하면 매우 편리하다. 아니면 다음처럼 해도 편리한 것 같다. 스터디에서 다른 스터디원이 쓰는 걸 참고했음ㅋㅋ
# global하게 방향배열 만들기
direction = [(0, -1), (0, 1), (-1, 0), (1, 0)]
# 어딘가에서 만든 함수에서 이용
def some_func(r, c):
...
for dr, dy in direction:
nr = r + dr # 다음 row좌표구하기
nc = c + dc # 다음 col좌표구하기
...
왜 이문제가 DFS, BFS분류에도 들어가는지 궁금했는데, 현재 위치에서 상하좌우에 있는 칸 중 잠기지 않은 칸들을 그래프처럼 표기할 수 있겠다는 생각이 든다. 그러면서 방문여부를 따지면서 "전에 방문한 적 있네? 그럼 넌 안 봐"하면서 따지니까 굳이 따지자면 내가 한 방식은 DFS인 듯.
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
출력
첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.
예제 입력 1복사
10
15 5 1 3 5 10 7 4 9 2 8
예제 출력 1복사
2
[접근방식]
1. 배열의 첫 번째 원소부터 시작해 합이 S 이상이 되는 가장 짧은 구간의 길이를 구한다.
2. 배열의 두 번째 원소부터 시작해 합이 S 이상이 되는 가장 짧은 구간의 길이를 구한다.
3. 배열의 세 번째 원소부터 시작해 합이 S 이상이 되는 가장 짧은 구간의 길이를 구한다.
...이렇게 해서 각 단계에서 구한 길이 중 가장 짧은 놈을 고른다.
import sys
N, S = map(int, sys.stdin.readline().split())
length = []
arr = list(map(int, sys.stdin.readline().split()))
for i in range(len(arr)):
j, sum = i + 1, arr[i]
while(sum < S and j < len(arr)):
sum += arr[j]
j += 1
if sum >= S:
length.append(j - i)
if length:
print(min(length))
else:
print(0)
근데 위 코드는 시간초과가 발생한다. 왜일까?
우선 코드를 보면 난 for문에서 i를 시작점으로 설정하며 각 구간들을 구하는데, j라는 변수가 구간의 끝점역할을 한다. 따라서 구하는 구간의 합이 S이상이 되는 순간 구간의 길이인 j - i를 length리스트에 더하고 마지막에 min메소드로 가장 짧은 길이를 출력하면 그것이 정답이다. 근데 시간초과가 뜨는 이유는 다름아닌 j, sum와 관련되어 있다.
바로 매 순간 새로 측정을 시작할 때마다(즉 시작점 i가 바뀔 때마다) j를 i + 1로 세팅한 뒤, j를 늘려가면서 측정하기 때문! 이것이 시간을 잡아먹는다. 마찬가지로 sum을 매 측정마다 새로 설정해주는 것도 시간을 잡아먹는다. 왜 Why?
어떤 단계에서 합이 S이상이 되는 구간을 구했다고 할 때, 이 구간의 끝점이 있다.
다음 단계에서 합이 S이상이 되는 구간을 또 구할텐데, 이 때 새로 구하게 되는 구간의 끝점은 이전 단계에서 구한 구간의 끝점보다 같거나 클 수밖에 없기 때문! 따라서 매 측정의 단계에서 사용한 j와 sum을 그대로 재활용?하는 느낌으로 써주는 식으로 코드를 수정했다.
import sys
N, S = map(int, sys.stdin.readline().split())
length = []
arr = list(map(int, sys.stdin.readline().split()))
sum_arr, j = arr[0], 1
for i in range(len(arr)):
while(sum_arr < S and j < len(arr)):
sum_arr += arr[j]
j += 1
if sum_arr >= S:
length.append(j - i)
sum_arr -= arr[i]
if length:
print(min(length))
else:
print(0)
