개발자가 되기 위해서 이것 저것 공부하다 보니 블로그 작성할 시간이 없었네요. 거의 한달만에 글을 작성하게 되었습니다.
오늘은 3월 2일에 작성하려던 리스트의 값을 매우 빠르게 변경하는 방법에 대해 작성해 보려고 합니다.
개요
보통, 초반에 반복문을 배우고 문제를 풀다보면 이중반복문을 통해 값을 변경하는 것을 많이 경험하게됩니다. 하지만 이 방법은 매우 느린 편에 속합니다.
그 이유는, 바로 이중 반복 형식때문입니다. 이차원 배열에서 값을 변경을 하기위해 모든 요소들을 전부 순회한다면 의 시간복잡도를 갖게 되죠.
이 때, 특정한 영역을 통째로 변경한다면 시간복잡도를 훨씬 줄일 수 있습니다.
아래 문제가 바로 그런 점을 응용하여 푸는 문제입니다.
풀이1
# 53점 풀이
import sys
input = sys.stdin.readline
n=int(input())
arr = [[0]*1001 for _ in range(1001)] #빈어레이
ans=[0]*(n+1) # 답저장할 리스트
for i in range(1,n+1): # 순회
r,c,w,h = map(int,input().split())
for row in range(r,r+w): # 윗장면적
for col in range(c,c+h):
arr[row][col]=i
for i in range(1,n+1):
for row in range(1001):
ans[i]+=arr[row].count(i)
print(*ans[1:],sep='\n')
풀이 1을 보면 이중 반복문을 순회하면서 조건을 만족하는 영역의 값을 변경해주는 작업을 진행합니다. 하지만 이것을 단일 반복문으로 변경한다면 속도가 개선될 것입니다. 그럼 어떻게 하면 단일 반복문을 사용하여 배열을 수정할 수 있을까요??
저는 여기서 슬라이싱을 이용해보았습니다.
슬라이싱이란??
슬라이싱이란, Sequence 객체에서 인덱스를 이용한 값의 접근법입니다.
Sequence 객체, 즉 리스트, 튜플, string에서 사용가능한 방법입니다.
슬라이싱을 하게 된다면 인덱스 조건에 맞는 값을 복사하여 새로운 객체를 생성하게 됩니다.
이 때 주의해야할 것은 얕은 복사입니다. 나중에 얕은 복사에 대해서 다시 다루겠지만, 2차원 배열의 경우에는 슬라이싱을 한다면 값이 아닌 주소가 복사된다는 점을 유의하시면 됩니다.
슬라이싱의 예시를 간단하게 보고 풀이를 마저 진행해보겠습니다.
arr = [1,2,3,4,5,6]
new_arr = arr[1:3]
print(new_arr) # [2,3]위의 예시에서 new_arr은 arr의 1에서 3번까지의 index영역을 복사하게 됩니다.
즉, index=1인 2부터 index=2인 3까지 값을 복사하여 새로운 리스트로 반환해줍니다.(이때, 슬라이싱하는 뒤쪽의 index는 그 수의 바로 직전 index까지 참조하게 됩니다. 위의 경우에는 [1:3]으로 표기되어 뒤의 index는 3이니깐 3-1=2인 index가 2인 위치까지 값을 참조합니다.)
풀이2
# 100점 풀이
import sys
input = sys.stdin.readline
n=int(input())
arr = [[0]*1001 for _ in range(1001)] #빈어레이
ans=[0]*(n+1) # 답저장할 리스트
for i in range(1,n+1): # 순회
r,c,w,h = map(int,input().split())
for row in range(r,r+w): # 윗장면적
arr[row][c:c+h] = [i]*h
for i in range(1,n+1):
for row in range(1001):
ans[i]+=arr[row].count(i)
print('\n'.join(map(str,ans[1:])))위의 풀이처럼 작성한다면, 이중 반복문으로 작성했던 값의 변환을 슬라이싱을 통해 단일 반복문으로 처리하면서 시간을 단축할 수 있게 됩니다.
마무리
- 이중 반복문은 시간이 오래걸리기 때문에 시간을 단축하고 싶으면 단일 반복문을 사용하는 알고리즘을 구상해 봅시다.
- 리스트의 값들을 동일한 값으로 변경하는 경우, 슬라이싱으로 접근한다면 쉽게 값을 변경할 수 있기 때문에 모든 인덱스를 순회할 필요가 없게 됩니다.
- 2차원 배열의 경우에는 얕은 복사를 조심해야 합니다.
이상으로 오늘의 포스트를 마치겠습니다. 틈틈이 블로그를 작성하고 싶지만, 시간이 도저히 나지 않네요 ㅜㅜ 임시글로 저장해 놓은 것만이라도 빠르게 작성해보겠습니다. 아직 10개정도의 임시글이 남아있어요ㅜㅜㅜ 오늘도 개발 공부하는 모든 분들을 응원합니다. 같이 힘내서 공부해 보아요!
