문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92344
파이썬 소스: https://bit.ly/49Yj8oW
이 문제를 풀기 위해서는 누적합 알고리즘을 알아야 합니다. 누적합으로 검색해보면, prefix sum과 cumulative sum에 대한 내용이 같이 나오는대요, 둘 중에, cumulative sum알고리즘으로 풀어야 하는 문제입니다.
하지만, cumulative sum으로 검색하면, 이게 cumulative sum에 대한 내용보다 cumulative distribution function에 대한 내용이 더 많이 나와서, 찾기가 어렵더라구요. 카카오에서 제공하는 풀이를 통해서 cumulative sum에 대한 내용을 미리 공부하고 나서, 문제를 풀어 보시는 것도 추천드립니다.
https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/
cumulative sum알고리즘을 사용하지 않고, 문제를 푼다고 가정하면 시간 복잡도가 너무 커서 문제를 풀 수 없습니다.
skill의 길이 250000 = 2.5 * 10 ** 5
board의 가로/세로 길이 = 10 ** 3, 10 ** 3
결과 적으로 O(2.5 * 10 ** 11)이 되어서, 일반적으로 시간내에 풀 수 있는 10 ** 9 보다 매우 큰 수입니다. 여기서 줄일 수 있는 부분은 skill을 사용했을 때, r1, c1 ~ r2, c2 영역을 모두 방문하는 부분입니다.
이제 cumulative sum알고리즘을 알아보겠습니다.
1, 0, 3, 2 <- #1 배열이 있다고 가정합니다.
첫번째 아이템의 값을 0으로 만들이 위해서, 1을 모든 아이템에서 빼기를 합니다.
0, -1, 2, 1 <- #1 배열의 값에서 모두 1을 뺀 상태입니다.
원래 값으로 돌아 가기 위해서, 더 해야 할 값을 아래와 같이 배열을 하나 더 만들어 줍니다.
1, 1, 1, 1 <- #2 배열입니다. 1을 뺀 것을 표시하는 배열 이구요, 원래 배열과 더하면 기존의 #1 배열 값으로 돌아 갈 수 있습니다.
#2 배열을 아래와 같이 변형할 수 있습니다.
1, 0, 0, 0, -1
첫번째 1아이템 1을 오른쪽으로 계속 더해주면, 1, 1, 1, 1, 0 배열로 변환 되구요, 마지막 아이템 0만 제외하면, #2 배열과 동일한 배열입니다.
현재 상태를 다시한번 정리하면 아래와 같습니다.
1, 0, 3, 2 <- #1 배열
0, -1, 2, 1 <- 1 뺀 상태
1, 0, 0, 0, -1 <- #2 배열의 변형
여기서 3번째 아이템 2를 0으로 만들기 위해서 2를 아래와 같이 빼기 합니다.
0, 0, 2, 2
0, -1, 0, -1 <- 1을 빼고, 2를 뺀 상태, #4 배열입니다.
여기서 0, 0, 2, 2 배열을 #2 배열의 변형과 같은 변형을 해보겠습니다.
0, 0, 2, 0, -2 가 되구요, 이 배열을 #3 배열의 변형이라고 부르겠습니다.
#2 배열의 변형과 #3 배열의 변형을 아래와 위에서 아래로 더해줍니다.
1, 0, 0, 0, -1
0, 0, 2, 0, -2
1, 0, 2, 0, -3 <- 더한 결과 배열입니다.
이 배열을 왼쪽부터 오른쪽으로 더해 보겠습니다.
1, 1, 3, 3, 0 이 됩니다. 여기에 #4 배열을 더 하면, #1 배열로 돌아 갈 수 있습니다.
0, -1, 0, -1 <- 1, 2를 빼고 남은 숫자
1, 1, 3, 3, 0
1, 0, 3, 2, 0 <- 마지막 0만 제외하면, 기존 #1 배열과 같아 졌습니다.
위의 방법을 사용하면 내구도 증가/감소하는 양만 표시해 두었다가, 증가/감소하는 양을 한번에 계산해서, board 배열과 더하면, 보다 빠르게 계산이 가능합니다.
하지만, 아직 1차원이구요, 2차원 배열에 위의 cumulative sum알고리즘를 적용해 보겠습니다.
더하고자 하는 숫자 n 이 있다고 하고, board가 4 x 4 2차원 배열이라고 가정하고, 목표로 하는 영역은 1,1 부터 3, 3까지입니다.
아래 배열을 #1 배열이라고 부르겠습니다.
0, 0, 0, 0, 0
0, n, 0, 0, -n
0, 0, 0, 0, 0
0, 0, 0, 0, 0
0, -n, 0, 0, n
위의 배열을 왼쪽에서 오른쪽으로 더해주겠습니다.
0, 0, 0, 0, 0
0, n, n, n, 0
0, 0, 0, 0, 0
0, 0, 0, 0, 0
0, -n, -n, -n, 0
위의 배열을 위에서 아래로 더해줍니다.
0, 0, 0, 0, 0
0, n, n, n, 0
0, n, n, n, 0
0, n, n, n, 0
0, 0, 0, 0, 0
#1 배열 상태에서 내구도 증가/감소를 연산을 할 수 있습니다.
0, 0에서, 2, 2까지 -m 감소시키겠습니다.
-m, 0, m, 0, 0
0, n, 0, 0, -n
m, 0, -m, 0, 0
0, 0, 0, 0, 0
0, -n, 0, 0, n
위의 2차원 배열을 왼쪽으로 더해주고, 다시 아래쪽으로 더해보면, 2번 내구도 증가/감소한 결과 배열을 얻을 수 있습니다. 이 배열을 board와 더하면, 내구도가 1이상인 건물을 찾을 수 있습니다.
cumulative sum알고리즘을 사용하여 시간 복잡도를 다시 계산해보면 다음과 같습니다.
1. 리스트 skill의 길이: 2.5 * 10 ** 5
2. 매 스킬 마다 + 또는 -가 4번 있습니다.
3. 보드의 크기 보다 1큰: 101 * 101 루프를 돌아서 내구도 증가/감소의 합을 구합니다.
4. 보드 크기만큼 100 * 100 루프를 돌아서, 모든 건물의 내구도를 구합니다.
1번은 시간 복잡도에 포함되구요.
2번은 상수의 곱하기 이기 때문에 시간복잡도에서 제외합니다.
3번은 10 ** 4 이지만, 이미 더 높은 차수인 10 ** 5가 있고, 여기에 더하기 이기 때문에 시간 복잡도 계산에서 제외합니다.
4번은 3번과 같은 이유로 시간 복잡도 계산에서 제외합니다.
2.5 곱하기도 제외하면, cumulative sum알고리즘을 사용했을 때, 이 문제의 시간복잡도는 O(10 ** 5) 에 수렴하게 됩니다.
cumulative sum알고리즘에 따라서, 함수 solution()의 인자로 주어지는 board보다 가로, 세로 크기가 1씩 더 큰 2차원 배열이 필요합니다.
|
sums = [[0 for _ in range(len(board[0]) + 1)] for _ in range(len(board)+1)] |
리스트 sums로 0으로 초기화된 2차원 배열을 만들었습니다.
skill에서 주어지는 type에 따라서, 건물의 내구도를 높이거나 낮춥니다.
for type, r1, c1, r2, c2, degree in skill: |
r2, c2는 cumulative sum알고리즘을 사용하기 위해서, 1씩 증가된 값을 사용하는 것을 확인해주세요.
변수 type이 1 or 2 인지에 따라서, 건물 내구도를 증가/감소시키는 값을 sums의 4가지 위치에 저장합니다.
cumulative sum알고리즘에 따라서, 리스트 sums에 간략하게 표시된 증가/감소 값을 풀어 볼 차례입니다.
먼저 왼쪽에서 오른쪽 방향으로 증가/감소 값을 풀겠습니다.
for r in range(len(sums)): |
그 다음에는 위에서 아래 방향으로 증가/감소 값을 풀겠습니다.
for c in range(len(sums[0])): |
이제 모든 증가/감소 값이 리스트 sums에 저장되었습니다.
answer = 0 |
위와 같이 board의 값과 sums의 값을 더 하면, 건물의 내구도입니다. 이 값이 1보다 크거나 같은 횟수를 모두 answer에 저장하여, 리턴하면 이문제의 답을 구할 수 있습니다.
궁금한 문제, 내용은 댓글, 이메일(coding.data.pul@gmail.com)로 보내주세요.
코데풀 유튜브 구독 부탁드립니다.
https://www.youtube.com/@codapul
전체 코드는 아래에 있습니다.
from typing import List |
댓글 없음:
댓글 쓰기