[Python/기타] 알고리즘(set을 이용한) 시간초과에 도움이 되는 팁

[Python] 알고리즘 문제 시간초과 발생했을때 팁 (bfs관련)¶

---

백준의 인구이동 문제를 풀다가 시간초과 문제를 해결하기 위해 많은 방법을 써봤지만 
늘 쓰던 방법들로는 시간초과문제를 해결할 수 없었다.
그와 관련해서 어떤 방식이 시간에 영향을 주는지 알아보기위해 간단한 테스트를 해봤다.

bfs같은 문제를 풀때
if node not in visited:처럼
해당 원소가 어떤 저장공간(ex. 리스트, 집합 등등)에 존재하는가?
이런 문제를 다뤄야 할때, 어떻게 해야 시간초과를 해결할 수 있을까?

---

In [11]:

## 1번 set
## a의 요소들을 (x, y)와 같이 저장하자.
a = set()
for i in range(500):
    for j in range(500):
        a.add((i, j))

In [12]:

## 2번 set
## b의 요소들을 하나의 숫자로 저장하자.
b = set()
for i in range(250000):
    b.add(i)

In [13]:

## 3번 리스트
## c의 요소들을 정수를 담고있는 2차원 배열로 만들어보자.
c = [[0]*500 for _ in range(500)]

각각의 요소들이 그 집합 혹은 리스트 안에 존재하는가?를 확인해보자.
전부 확인하는데 걸리는 시간도 확인하자.

In [5]:

import time

1번¶

In [15]:

start = time.time()

for i in range(500):
    for j in range(500):
        if (i, j) in a: pass

end = time.time()
print(end - start)

0.12466812133789062

2번¶

In [16]:

start = time.time()

for i in range(250000):
    if i in b: pass

end = time.time()
print(end - start)

0.05086255073547363

3번¶

In [17]:

start = time.time()

for i in range(500):
    for j in range(500):
        if c[i][j] == 0: c[i][j] = 1
            
end = time.time()
print(end - start)

0.1107032299041748

같은 로직으로 풀었는데도 시간차이가 많이나던 이유.
같은 set을 이용하더라도, 그 안에 담긴 요소값 무엇이냐에 따라 걸리는 시간이 다르다.