[코드트리 조별과제] 1주차

숫자로 이루어진 사각형

Novice Mid 레벨의 문제 풀이와 복잡도 분석을 해보았다.

🔗 문제 바로가기

 

내 코드

def n_by_n_rect(n):
    i = 1
    for _ in range(n):
        for _ in range(n):
            print(i, end=' ')
            i += 1
            if i==10:
                i = 1
        print()
    
n = int(input())
n_by_n_rect(n)

 

시간 복잡도 (Time Complexity)

코드에서 두 개의 중첩된 루프가 있으며, 각 루프는 n번씩 실행된다. 내부 루프 안의 모든 작업은 상수 시간 O(1)에 수행된다.

- 외부 루프: n번 반복

- 내부 루프: n번 반복

- 내부 루프의 작업: 상수 시간 O(1)

따라서 총 시간 복잡도는 O(n) * O(n) = O(n^2) 이다.

공간 복잡도 (Space Complexity)

이 코드에서 추가로 사용하는 메모리는 주로 변수 i와 두 개의 루프 인덱스이다. 이 변수들은 모두 상수 개수이고, 반복 횟수에 상관없이 일정한 메모리만 사용한다.

- i: 상수 공간 O(1)

- 두 개의 루프 인덱스: 상수 공간 O(1)

 

따라서 이 코드의 공간 복잡도는 O(1) 이다.

요약

- 시간 복잡도: O(n^2)

- 공간 복잡도: O(1)