글 읽기 - [정답 코드 주의] 복잡도 차이가 나는 이유가 궁금합니다.

puleugo 2년 전 0

로직에는 큰 차이가 없는것 같은데, 1번이 시공간 복잡도가 훨씬 효율적입니다.

리스트를 불러오지 않는게 시간과 공간 복잡도에 영향을 주는건가요?

아니면 제가 놓친 부분이 있는건가요?

1번 코드 
from collections import deque
import sys

n, m, v = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
visited = [False] * (n + 1)
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
for i in range(1, n+1):
    graph[i].sort()


def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)


def bfs(graph, v, visited):
    q = deque([v])
    visited[v] = True
    while q:
        v = q.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                q.append(i)
                visited[i] = True


dfs(graph, v, visited)
print()
visited = [False] * (n + 1)
bfs(graph, v, visited)



2번 코드
from collections import deque
import sys
input = sys.stdin.readline

def dfs(x):
    print(x, end=' ')
    dvisited[x] = 1
    for i in graph[x]:
        if not dvisited[i]:
            dfs(i)


def bfs(x):
    q = deque([x])
    visited = [0] * (n+1)
    visited[x] = 1
    while q:
        x = q.popleft()
        print(x, end=' ')
        for i in graph[x]:
            if not visited[i]:
                visited[i] = 1
                q.append(i)


n, m, x = map(int, input().split())
graph = [[] for _ in range(n+1)]
dvisited = [0]*(n+1)

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
for i in range(1, n+1):
    graph[i].sort()

dfs(x)
print()
bfs(x)

puleugo 2년 전 0

지금 확인해보니 1번 코드는 python으로, 2번 코드는 pypy로 제출했네요.
pypy가 더 빠르기로 아는데, 케바케인건가용?

* 시공간 복잡도는 이론의 얘기입니다. 따라서 로직이 큰 차이가 없는데 어떤 하나가 시공간 복잡도가 효율적이란 말은 잘못된 겁니다. 극단적으로 어떤 시간 공간 복잡도 모두 O(n) (혹은 Ω(n))인 알고리즘을 사용하는 프로그램이 10개의 입력을 받았을 때 16MB의 메모리를 사용하고 10000개의 입력을 받았을 때 16GB의 메모리를 사용한다고 가정하면, 평범한 램을 사용하는 경우 당연히 메모리 계층상 수행시간이 1000배보다 훨씬 더 걸릴 겁니다. 그런다고 시간 복잡도가 O(n)이 아니게 되는 건 아닙니다.

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

문제

문제

출처

ICPC

[정답 코드 주의] 복잡도 차이가 나는 이유가 궁금합니다.

puleugo 2년 전 0

puleugo 2년 전 0

onart 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말