[백준/python] 2738번 - 행렬 덧셈 / 새싹

2738번: 행렬 덧셈

import sys
input=sys.stdin.readline

n,m = map(int,input().rstrip().split())
b =[]
c =[]
d =[]

for i in range(n):
        b.append(list(map(int,input().rstrip().split())))

for i in range(n):
        c.append(list(map(int,input().rstrip().split())))

for i in range(n):
    for j in range(m):
            b[i][j] = b[i][j]+c[i][j]

for i in range(n):
    print(' '.join(map(str,b[i])))

 

행렬과 관련된 문제를 풀 때 항상 주의할 점은 시간복잡도이다.

시간복잡도는 연산을 할때 몇 초가 걸리느냐를 기호로 표시하는 것으로, worst case를 토대로 O(n)과 같이 표기한다.

여기서 worst case란, 코드를 돌릴 때 진짜 몇 번이나 연산해야지 결과를 얻을 수 있는 가에 대한 최악의 경우를 말한다.

즉, for 루프의 경우 설정한 n번을 돌려야 하므로 worst case는 n번이고, O(n)과 같이 표기되는 것이다. 

자료구조의 기본이니 잘 알아두자.

 

행렬이 N*M이고 만약에 for 루프를 두 번 쓴다면 시간복잡도는 필히 O(N*M)이 될 수 밖에 없다.

M번 돌리고 난 걸 다시 N번 돌리니까 말이다.

이 문제에서는 N과 M이 100보다 작거나 같아서 최대 연산은 10000 정도이다. 이 정도면 괜찮은 정도다.

하지만 코딩을 하다가 100만*100만을 해야 하는 행렬 문제가 나온다면 그때는 시간초과를 유발할 수밖에 없다. 따라서 조건에 주의해야 한다.

 

대략적으로 어떤 언어든 코딩테스트에서 n당 10만번의 연산 정도가 시간상 O(n^2)을 쓸 수 있는 최대 한도라고 생각하면 된다.

10만번이 넘어간다 하면 무조건 O(n)으로 해결할 수 있는 코드를 짜야 한다. 이걸 명심하자.

 

만약 100만 *100만을 해결해야 하는 문제가 나온다면 메모리 효율상 numpy를 쓰는 방법이 최선이 된다.

하지만 코딩테스트에서는 numpy를 쓸 수 없으므로 이런 문제는 내지 않을 것이란 것이 정론이긴 하다.

프로젝트에서는 numpy를 쓰는 방법을 알아두는 것이 정말 도움이 되니 잘 공부하자. 

 

아무튼 일단 각각의 for 루프를 분리하여 리스트를 만들어준다.

둘째 줄부터 N개의 줄까지는 리스트 b에 넣고, N개의 줄부터 2N개의 줄까지는 리스트 c에 넣는다.

 

그리고 나서 for 루프를 두 번 돌면서 둘을 더하게 되면, 시간 복잡도 O(N*M)으로 문제를 해결 할 수 있다.