글 읽기 - 파이썬 고수님들 도와주세요 ㅠㅠ (답 포함)

kingzino 3년 전 0

구현한 코드가 복잡 하시다면 죄송합니다. ㅠㅠ

우선 제가 질문드릴 사항은 queue를 구현할 때 deque를 사용한 것과 그냥 list를 사용한 것의 시간차이 입니다.

제가 생각하기로는 deque에서 popleft()를 할 때 시간 복잡도는 O(1) 이고, list에서 pop()을 할 때는 O(N)입니다.

그러나 백준 사이트에서 두 코드 다 돌려본 결과 deque가 2배정도 느리게 나왔습니다.

이유가 무엇인지 모르겠습니다.

list 쓸 때 : 약 120ms

deque 쓸 때 : 약 210ms

list로 구현한 것은 첫번째 코드이고

deque로 구현한 것은 두번째 코드입니다.

두번째 코드에서 min_dist를 구하는 과정에서 list를 새로 할당 해줬는데

첫번째랑 똑같이 고쳐 해봐도 시간은 안 변하네요,,

python3로 돌려도 봤지만 시간은 변함없이 list가 더 빨랐습니다.

이유가 궁금합니다.

#첫번째 소스코드
from sys import stdin

std = stdin.readline
N = int(std())
shark = []

for i in range(N):
    shark.append(list(map(int, std().split())))

huge, baby, eat = 2, [0, 0], 0  # 아기상어 크기, 위치, 현재먹은 개수
for i in range(N):
    for j in range(N):
        if shark[i][j] == 9:
            baby = [i, j]

q = []
nr, nc = [-1, 0, 1, 0], [0, -1, 0, 1]

check = [[0 for i in range(N)] for j in range(N)]


def find_food():
    check = [[0 for i in range(N)] for j in range(N)]
    f_r, f_c, dd = q[-1]
    check[f_r][f_c] = 1
    F = []
    dist = -1
    while q:
        r, c, d = q.pop(0)
        if d == dist:
            break
        for i in range(4):
            dr = r + nr[i]
            dc = c + nc[i]
            if 0 <= dr < N and 0 <= dc < N:
                if check[dr][dc] == 0 and shark[dr][dc] <= huge:
                    check[dr][dc] = 1
                    if 0 < shark[dr][dc] < huge:
                        F.append((dr, dc, d+1))
                        dist = d+1
                    q.append((dr, dc, d+1))
    F = sorted(F, key=lambda x: (x[2], x[0], x[1]))
    if len(F) == 0:
        return -1
    else:
        return F[0]


answer = 0
aa = 0
food = []
while True:
    r, c = baby
    q.append((r, c, 0))
    food = find_food()
    if food == -1:
        break
    q = []
    shark[r][c] = 0
    new_r, new_c, dist = food
    baby = [new_r, new_c]
    shark[new_r][new_c] = 9
    eat += 1
    answer += dist

    if huge == eat:
        huge += 1
        eat = 0

print(answer)



#두번째 소스코드

from sys import stdin
from collections import deque

std = stdin.readline

N = int(std())

board, baby_size, eat = [], 2, 0
baby_r, baby_c = 0, 0

for i in range(N):
    board.append(list(map(int, std().split())))
    for j in range(N):
        if board[i][j] == 9:
            baby_r, baby_c = i, j
            board[i][j] = 0

q = deque()
nr, nc = [0, 1, 0, -1], [1, 0, -1, 0]


def bfs():
    min_dist = 999999
    d_list = []
    dist = [[-1 for i in range(N)] for j in range(N)]
    q.append((baby_r, baby_c, 0))
    dist[baby_r][baby_c] = 0
    while q:
        r, c, d = q.popleft()
        for i in range(4):
            dr, dc = r + nr[i], c + nc[i]
            if dr < 0 or dc < 0 or dr >= N or dc >= N:
                continue
            if board[dr][dc] > baby_size or dist[dr][dc] >= 0:
                continue
            dist[dr][dc] = d+1
            q.append((dr, dc, d+1))
            if 0 < board[dr][dc] < baby_size:
                d_list.append((dr, dc, d+1))

    d_list = sorted(d_list, key=lambda x: (x[2], x[0], x[1]))
    if len(d_list) == 0:
        return (-1, -1, 0)
    return d_list[0]


answer = 0
while True:
    eat_r, eat_c, d = bfs()
    if eat_r == -1:
        break

    board[eat_r][eat_c] = 0
    baby_r, baby_c = eat_r, eat_c
    eat += 1
    answer += d
    if eat == baby_size:
        baby_size += 1
        eat = 0

print(answer)

mugglim 3년 전 0

아래의 코드처럼 deque를 사용하여 제출하면 약 96ms로 통과됩니다.
반면, list를 사용하면 72ms로 통과됩니다.

저도 한 가지 의문점이, deque의 peek at leftmost item, peek at rightmost item은 O(1)인데 어디서 더 time이 발생하는지 궁금하네요!..

#첫번째 소스코드
from sys import stdin
from collections import deque
std = stdin.readline
N = int(std())
shark = []

for i in range(N):
    shark.append(list(map(int, std().split())))

huge, baby, eat = 2, [0, 0], 0  # 아기상어 크기, 위치, 현재먹은 개수
for i in range(N):
    for j in range(N):
        if shark[i][j] == 9:
            baby = [i, j]

q = deque([])
nr, nc = [-1, 0, 1, 0], [0, -1, 0, 1]

check = [[0 for i in range(N)] for j in range(N)]


def find_food():
    check = [[0 for i in range(N)] for j in range(N)]
    f_r, f_c, dd = q[-1]
    check[f_r][f_c] = 1
    F = []
    dist = -1
    while q:
        r, c, d = q.popleft()
        if d == dist:
            break
        for i in range(4):
            dr = r + nr[i]
            dc = c + nc[i]
            if 0 <= dr < N and 0 <= dc < N:
                if check[dr][dc] == 0 and shark[dr][dc] <= huge:
                    check[dr][dc] = 1
                    if 0 < shark[dr][dc] < huge:
                        F.append((dr, dc, d+1))
                        dist = d+1
                    q.append((dr, dc, d+1))
    F = sorted(F, key=lambda x: (x[2], x[0], x[1]))
    if len(F) == 0:
        return -1
    else:
        return F[0]


answer = 0
aa = 0
food = []
while True:
    r, c = baby
    q.append((r, c, 0))
    food = find_food()
    if food == -1:
        break
    q = deque([])
    shark[r][c] = 0
    new_r, new_c, dist = food
    baby = [new_r, new_c]
    shark[new_r][new_c] = 9
    eat += 1
    answer += dist

    if huge == eat:
        huge += 1
        eat = 0

print(answer)

kingzino 3년 전 1

deque에 삽입 시 연산이 O(1) 이지만 실제로는 list 삽입과 차이가 좀 나네요.

아마 list에서 첫번째 원소를 빼는 과정보다 넣는 과정에서의 패널티가 좀 더 큰 것 같아요.

밑의 소스코드로 참고 해보시면 좋을 것 같습니다.!!

from sys import stdin
from collections import deque
from math import floor
import time

N = 10000


start = time.time()
queue = [0 for i in range(N)]
end = time.time()
print(floor((end-start)*10000), "ms")


start = time.time()
deque = deque()
for i in range(N):
    deque.append(i)
end = time.time()
print(floor((end-start)*10000), "ms")

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

문제

문제

출처

ICPC

파이썬 고수님들 도와주세요 ㅠㅠ (답 포함)

kingzino 3년 전 0

mugglim 3년 전 0

kingzino 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말