글 읽기 - 도와주세요~~(python)

sls666 4년 전 0

아래의 시간복잡도를 O(n^3)으로 봐도 괜찮은건가요?(n_Queen함수의 for문이 O(n)이고 그때마다 check함수가 매번 호출되므로...)

check함수는의 연산은 current_row가 0일때부터 하나씩 올라가므로 O(n^2)의 복잡도를 가진다고 생각했습니다...이렇게 생각하는게 맞는건가요? 고수님들?

n = int(input())
result = 0
myQueen = list()
def n_Queen(current_row):
    global result
    if current_row == n:
        result += 1
        return
    
    for current_col in range(n):
        if check(current_col, current_row, myQueen):
            myQueen.append(current_col)
            n_Queen(current_row + 1)
            myQueen.pop()
            
def check(current_col, current_row, myQueen):
    for i in range(current_row):
        if myQueen[i] == current_col or abs(myQueen[i] - current_col) == current_row - i:
            return False
        
    return True

n_Queen(0)
print(result)
            

ho94949 4년 전 1

n_Queen 이 n_Queen 함수를 호출하네요, 그러면 시간복잡도를 O(n^3)이라고 말할 수 없습니다.

n_Queen 함수에서 나머지 부분이 O(n^2)이 걸리고, 또 다시 n_Queen 을 호출하고 나머지 부분이 O(n^2)이 걸리고, ... 이가 계속 반복되게 됩니다.

sls666 4년 전 0

그렇군요~ 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

도와주세요~~(python)

sls666 4년 전 0

ho94949 4년 전 1

sls666 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말