이 글에서는 행(row)과 열(column) 기준으로 정렬된 행렬에서 음수의 개수를 효율적으로 세는 파이썬 프로그램을 소개합니다. 모든 요소를 하나씩 확인하는 대신 정렬된 행렬의 특성을 활용하면 훨씬 적은 연산으로 답을 구할 수 있습니다.
행·열 기준 정렬 행렬이란?
행·열 기준 정렬 행렬이란, 임의의 위치에 있는 값이 같은 행의 다음 열 값보다 작거나 같고, 같은 열의 다음 행 값보다도 작거나 같은 행렬을 말합니다. 즉, 모든 행과 모든 열이 오름차순으로 정렬되어 있는 형태입니다.
예시 행렬 M
M = [[-40, -12, 1, 5],
[-20, -2, 5, 15],
[-18, -1, 13, 18],
[-12, 0, 15, 38]]위 행렬 M에서 첫 번째 행의 첫 번째 값인 -40은 같은 행의 다음 열 값인 -12보다 작고, 같은 열의 다음 행 값인 -20보다도 작습니다. 이 규칙이 행렬 전체에 동일하게 적용됩니다.
전체 코드
# 행렬은 각 행과 열 기준으로 오름차순 정렬되어 있어야 합니다.
matrix = [
[-40, -12, 1, 5],
[-20, -2, 5, 15],
[-18, -1, 13, 18],
[-12, 0, 15, 38]
]
rowCount = len(matrix) # 행의 개수
columnCount = len(matrix[0]) # 열의 개수
count_of_negative_integer = 0
row = 0
col = columnCount - 1 # 오른쪽 위 모서리에서 시작
while row < rowCount and col >= 0:
if matrix[row][col] < 0:
# 현재 값이 음수면 같은 행의 왼쪽 값들도 모두 음수
count_of_negative_integer += (col + 1)
row += 1 # 아래 행으로 이동
else:
col -= 1 # 왼쪽 열로 이동
print("정렬된 행렬에서 음수의 개수:", count_of_negative_integer)실행 결과
정렬된 행렬에서 음수의 개수: 7
알고리즘 동작 원리
- 탐색은 행렬의 오른쪽 위 모서리에서 시작합니다.
- 현재 값이 0 이상이면, 그 열의 아래쪽에는 더 큰 값만 있으므로 음수가 존재하지 않습니다. 따라서 한 칸 왼쪽으로 이동합니다.
- 현재 값이 음수라면, 같은 행에서 왼쪽에 있는 값들은 모두 음수입니다. 따라서 (현재 열 인덱스 + 1)개를 한 번에 세고, 한 칸 아래로 이동합니다.
- 이 과정을 행렬의 범위를 벗어날 때까지 반복합니다.
시간 복잡도
모든 요소를 일일이 확인하는 브루트 포스 방식은 O(m×n)의 시간이 필요하지만, 이 알고리즘은 매 단계마다 하나의 행 또는 열을 탐색 대상에서 제외하므로 O(m+n) 만에 완료됩니다. 추가 자료구조를 사용하지 않으므로 공간 복잡도 역시 O(1)로 매우 효율적입니다.
응용
비교 조건만 바꾸면 특정 값보다 작은 수의 개수도 손쉽게 구할 수 있습니다. 예를 들어 조건을 < 5로 변경하면 5보다 작은 정수의 개수를 같은 방식으로 계산할 수 있습니다.