실버1_11660_수열의 합 5
page link : https://www.acmicpc.net/problem/11660
💡풀이전략
- 인수를 받는다
- N: 배열의 길이(정사각형), queries: 쿼리의 갯수, Array: 주어진 배열
- 배열생성
- for 구문과 슬라이싱 인덱스를 이용해 N * N 배열 생성
- prefix_sum 배열 생성
- 첫행, 첫열에 0을 포함한 prefix_sum배열을 생성한다.
- 이 때 우하단에 누적합을 기재한다.
- 우하단의 값(기준) = 행(기준 - 1) + 행(기준 - 1) - 대각선(기준 - 1)
- 쿼리 정의
- 여기서 쿼리는 무조건 4개의 index를 순환
- 계산 함수를 이용해 결과값 도출
- x, y, i, j 의 갯수 만큼 순회
- 쿼리별 결과값 : i, j 의 누적합 - (i, y -1) - (x - 1, j) + (x - 1, y - 1)
- 함수에서 return된 값을 순환하여 print
- ‘\n’.jonin(map(str, results))를 통해 출력할 수도 있지만, 이는 join 함수를 사용하기 위해 문자열로 다시 저장하는 과정을 거치므로 for…in함수를 통해 출력하는 것이 메모리 사용에 더욱 효율적임.
🎨 사용된 알고리즘
prefix_sum(누적합)
code
Python
import sys
input = sys.stdin.read()
data = list(map(int, input.split()))
# 입력값 정의
idx = 0
N = data[0] #배열의 길이
K = data[1] #쿼리 갯수
idx += 2
# 배열 생성
A = []
for i in range(N):
row = data[idx : idx + N + 1]
A.append(row)
idx += N
# prefix_sum 구축
prefix_sum = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
for j in range(1, N + 1):
prefix_sum[i][j] = A[i - 1][j - 1] + prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1]
# 쿼리 정의
queries = []
for _ in range(K):
query = data[idx : idx + 4]
queries.append(query)
idx += 4
# 계산 함수
def array_sum(prefix_sum, queries):
results = []
for i, j, x, y in queries:
result = prefix_sum[x][y] - prefix_sum[i - 1][y] - prefix_sum[x][j - 1] + prefix_sum[i - 1][j - 1]
results.append(result)
return results
results = array_sum(prefix_sum, queries)
for result in results:
print(result)
해결한 오류
1. 얕은복사로 인해 모든 객체의 값 변경 이슈
A = []
for idx in range(2, N * N, 4): # init of array
row = [data[idx], data[idx + 1], data[idx + 2], data[idx + 3]]
A.append(row)
**# prefix_sum 구축 -> !!오류 발생 지점!!
prefix_sum = [[0] * (N + 1)] * (N + 1) # init prefix_sum
print(prefix_sum)**
for i in range(1, N + 1):
for j in range(1, N + 1):
prefix_sum[i][j] = A[i - 1][j - 1] + prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1]
**print(prefix_sum)**
결과 : prefix_sum의 모든 배열이 같은 배열로 출력된다.
[[0, 10, 14, 18, 22], [0, 10, 14, 18, 22], [0, 10, 14, 18, 22], [0, 10, 14, 18, 22], [0, 10, 14, 18, 22]]
이유 : 얕은복사(포인터 복사, 주소값 복사)
- 단일리스트 생성
[[0] * (N + 1)]을 통해[0, 0, 0, 0, 0]이란 value와[0, 1, 2, 3, 4]라는 key를 가진 단일 리스트(객체)를 생성한다.- 이 리스트는 메모리에 저장된 데이터 영역의 불변 데이터를 참조하는 주소(포인터)로 저장된다.
- 리스트 참조 복사
- 위 리스트를 (N + 1)번 반복하여 새로운 리스트를 만든다.
- 이 과정은 독립된 리스트를 만드는 것이 아니라, 동일한 리스트 객체를 참조하는 주소를 복사하는 것
-
얕은 복사 메모리 저장 형태(도식)
+---------------------+ | 변수영역 | +---------------------+ | 1001 | +---------------------+ => **N + 1 번 복사** | key : [[0]*(N + 1)] | = **value : @5003 N + 1번 복사** +---------------------+ | value : @5003 | +---------------------+ +---------------------+---------------------+---------------------+ | 데이터영역 | +---------------------+---------------------+---------------------+ | 5003 | 5004 | 5005 | +---------------------+---------------------+---------------------+ | @7003~ | 0 | 1 | +---------------------+---------------------+---------------------+ +---------------------+---------------------+---------------------+ | 변수영역 | +---------------------+---------------------+---------------------+ | 7003 | 7004 | 7005 | +---------------------+---------------------+---------------------+ | key : @5004 | key : @5005 | key : @5006 | +---------------------+---------------------+---------------------+ | value : @5004 | value : @5004 | value : @5004 | +---------------------+---------------------+---------------------+ - 따라서, prefix_sum[0][1] = 1 로 변경해 보면 prefix[n][1] = 1로변경됨.
해결 방법
- 깊은 주소 복사 이용
- 각 순환마다 리스트가 독립적인 객체가 될 수 있도록 함
-
순환문 사용
prefix_sum = [] for i in range(N + 1): prefix_sum.append([0] * (N + 1)] -
리스트 컴프리핸션 사용 (list comprehension)
prefix_sum = [[0] * (N + 1) for _ in range(N + 1)]
-
- 각 순환마다 리스트가 독립적인 객체가 될 수 있도록 함
- 순환을 통해 매번 새로운 참조의 리스트 생성
-
깊은 복사 메모리 저장 형태(도식)
+---------------------+---------------------+---------------------+ | 변수영역 | +---------------------+---------------------+---------------------+ | 7003 | 7004 | 7005 | +---------------------+---------------------+---------------------+ |key : [[0]*(N + 1)]-1|key : [[0]*(N + 1)]-2|key : [[0]*(N + 1)]-3| +---------------------+---------------------+---------------------+ | value : @5003 | value : @5004 | value : @5005 | +---------------------+---------------------+---------------------+ +---------------------+---------------------+---------------------+ | 데이터영역 | +---------------------+---------------------+---------------------+ | 5003 | 5004 | 5005 | +---------------------+---------------------+---------------------+ | @7003~ | @7008~ | @7013~ | +---------------------+---------------------+---------------------+ +---------------------+---------------------+---------------------+ | 변수영역 | +---------------------+---------------------+---------------------+ | 7003 | 7008 | 7013 | +---------------------+---------------------+---------------------+ | key : @5005 | key : @5005 | key : @5005 | +---------------------+---------------------+---------------------+ | value : @5006 | value : @5006 | value : @5006 | +---------------------+---------------------+---------------------+ - 따라서, prefix_sum[0][1] = 1 로 변경 시, prefix[0][1] = 1 로 변경됨.
결론 : 깊은 복사를 해야 서로 독립되게 데이터를 수정할 수 있다.
결과값도 제대로 변경된다.
-
기존코드
import sys input = sys.stdin.read() data = list(map(int, input.split())) print(data) # data정의 N = data[0] # size of array K = data[1] # range of queries idx = 2 A = [] for idx in range(2, N * N, 4): # init of array row = [data[idx], data[idx + 1], data[idx + 2], data[idx + 3]] A.append(row) # prefix_sum 구축 prefix_sum = [[0] * (N + 1)] * (N + 1) # init prefix_sum print(prefix_sum) for i in range(1, N + 1): for j in range(1, N + 1): prefix_sum[i][j] = A[i - 1][j - 1] + prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1] # 쿼리 계산 queries = [] for i in range(K): query = [data[idx], data[idx + 1], data[idx + 2], data[idx + 3]] queries.append(query) idx += 4 results = [] for i, j, x, y in queries: result = prefix_sum[x][y] - prefix_sum[i - 1][y] - prefix_sum[x][j - 1] + prefix_sum[i - 1][j - 1] results.append(result) for answer in results: print(answer)
댓글남기기