백준 11725번 문제를 푸는데 계속해서 시간초과로 난항을 겪고 있었다. 이 문제를 풀기 위해 내가 짠 코드는 다음과 같다. 파이참에서 실행시켰을때는 입출력 예제와 똑같이 나왔기에 이제 여기서 줄일 만한 곳을 찾기 시작했다. graph를 딕셔너리로 만들었는데 리스트로 변경하면 좀 더 시간이 줄어들까 싶어 시도했지만 역시나 실패였다. 그후 몇 가지 시도를 하다보니 코드가 아예 틀리기도 했다. 결국 나는 그를 찾아갔다. 거의 솔루션은 간단했다. 리스트(list)를 세트(set)로 변경하는 것이다. 위 코드 중 일부를 보면 입력값을 받아 그래프를 만든 후 부모 노드를 찾기 위해 bfs를 사용했다. def bfs_queue(start): parent = [0] * (n+1) visited = [start] q = deque([start]) while q: node = q.popleft() for adj in graph[node]: if adj not in visited: parent[adj] = node q.append(adj) visited.append(adj) def bfs_queue(start): parent = [0] * (n+1) visited = set([start]) q = deque([start]) while q: node = q.popleft() for adj in graph[node]: if adj not in visited: parent[adj] = node q.append(adj) visited.add(adj) visited는 방문한 노드를 중복 방문하지 않기 위해 만든 리스트다. if문에 인접 노드가 이미 visited에 없다면 아래 코드를 반복해서 실행한다. 이때 if adj not in visited의 시간 복잡도는 O(n)이다. 하지만 visited를 세트(set)로 바꾸면 시간 복잡도는 O(1)이 된다. 리스트와 세트의 연산 차이점을 나타낸 표를 참고해보면, 리스트(list)

Scope 파이썬에서 변수의 유효 범위를 말한다. 위치에 따라 작성한 코드가 작동하거나 작동하지 않을 수도 있고 때로는 원하는 대로 값이 안나올 수도 있다. 변수의 위치를 알맞게 작성해야 한다. LEGB rule 이 규칙에 따라 순서대로 작동한다. Local scope 함수 내부에서 선언된 변수나 함수로 그 범위에만 유효하다. Enclosed scope 외부함수에 정의되었지만 내부함수까지 사용된다. 주로 중첩 함수가 정의될 때 사용된다. Global scope 외부에 선언된 변수로 전체적인 범위에 유효하다. Built-in scope 파이썬 설치 파일 안에 바로 내장된 것으로 별다른 선언없이 실행된다. ex) len(), input(), print() 등