Share
Sign In
TIL 웹개발
TIL 웹개발 - 리스트(list)와 세트(set)의 시간 복잡도 차이
서경태
👍
백준 11725번 문제를 푸는데 계속해서 시간초과로 난항을 겪고 있었다.
이 문제를 풀기 위해 내가 짠 코드는 다음과 같다.
import sys from collections import deque input = sys.stdin.readline 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) for i in range(2, n+1): print(parent[i]) n = int(input()) graph = {i: [] for i in range(1, n+1)} for _ in range(n-1): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) bfs_queue(1)
파이참에서 실행시켰을때는 입출력 예제와 똑같이 나왔기에 이제 여기서 줄일 만한 곳을 찾기 시작했다. graph를 딕셔너리로 만들었는데 리스트로 변경하면 좀 더 시간이 줄어들까 싶어 시도했지만 역시나 실패였다. 그후 몇 가지 시도를 하다보니 코드가 아예 틀리기도 했다.
결국 나는 그를 찾아갔다.
왔니...?
거의 솔루션은 간단했다.
리스트(list)를 세트(set)로 변경하는 것이다.
위 코드 중 일부를 보면 입력값을 받아 그래프를 만든 후 부모 노드를 찾기 위해 bfs를 사용했다.
리스트
세트
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)
세트(set)
탐색(search)
O(n)
O(1)
삽입(append)
O(1)
O(1)
삭제(remove)
O(n)
O(1)
리스트로 구성될 경우 처음부터 끝까지 순차적으로 탐색을 해야하기 때문에 O(n)이 되고
세트의 경우 해시 테이블을 사용하기 때문에 O(1)이 된다.
해시테이블의 위력... 내 링크도 함께 첨부해본다.
Subscribe to 'kyugntae-ai'
Welcome to 'kyugntae-ai'!
By subscribing to my site, you'll be the first to receive notifications and emails about the latest updates, including new posts.
Join SlashPage and subscribe to 'kyugntae-ai'!
Subscribe
👍
Other posts in 'TIL 웹개발'See all
서경태
TIL 웹개발 - CS 기초 지식
메인보드 컴퓨터 본체 내부에 위치한, 주회로가 내장된 보드이다. CPU (Central Processing Unit) 컴퓨터의 두뇌 역할을 하는 실질적으로 모든 기능을 수행하는 요소 입력을 받은 명령을 해석/연산 한 후에 결과값을 출력장치로 전달하는 컴퓨터의 주요 부품 GPU (Graphic Processing Unit) 병렬 연산에 특화되어 이전에는 3D 그래픽을 처리하는데 많이 사용했지만 현재는 범용적으로 사용된다. 주기억장치 (RAM) 휘발성 메모리로 컴퓨터를 껏다 키면 메모리가 사라진다. DRAM SRAM 보조기억장치 비휘발성 메모리로 컴퓨터를 껐카 켜도 메모리가 사라지지 않는다. HDD : 물리적인 보조기억장치 SSD : 반도체에 전기 신호를 이용하여 데이터를 적재하는 보조기억장치 OS 운영체제란 사용자가 컴퓨터를 조작 및 제어하고 작업의 편의성을 제공하기 위한 '시스템 소프트웨어'입니다.
서경태
TIL 웹개발 - 재귀함수, 그저 믿음 뿐
정확히 말하면, 머릿속에 함수 실행 순서를 그리려고 하지 말라는 것이다. 이유는 머릿속에서 재귀에 재귀에 재귀에 재귀를 따라가보면 어는 순간 핀트가 나가버리기 때문이다. 그래서 중요한 것은 재귀 함수의 중요한 부분에 초첨을 맞춰 문제를 풀어나가는 것이다. 재귀가 풀리는 4단계 접근법 재귀를 꼭 써야 하는가? 반복 대신 재귀를 써야하는 경우인지 생각해본다. 재귀함수를 사용해서 푸는 문제의 대부분은 반복을 사용해서도 풀수 있다. 복잡한 문제를 더 작은 문제로 쪼개고, 작은 문제를 반복적으로 풀고, 작은 답들을 조합해서 전체 문제를 해결한다. 그리고 일반적으로 성능은 반복문이 재귀함수보다 더 좋다. 그렇기에 꼭 재귀함수를 써야하는지 먼저 체크해본다. 베이스 조건 답을 바로 알 수 있는 가장 간단한 상황을 생각한다. 재귀함수는 무한루프에 빠질 경우가 많다. 그렇기에 베이스 조건을 가장 먼저 만들어야 한다. 베이스 조건에서 무엇을 return 해야할지 헷갈린다면 문제에서 요구한 답의 데이터 타입을 본다. 예시로 주어진 인풋 값을 보고, 답으로 만드는 방법을 생각하면 함수 실행 순서를 떠올린다. 그보다 문제에 초점을 맞춰 베이스 조건을 만들어보자. 분해 베이스 조건에 가까워지도록 인풋값을 조작한다. 예를 들어, n이라는 정수로 함수를 실행한다면, 자기 자신을 호출할때는 n-1을 넣는다. 그래야 재귀함수가 반복하면서 인풋값이 조금식 더 간단해진다. 재귀적 분해라고도 하는데 인풋값을 간단하게 만들어서 문제를 더 작게 만드는 것이다. 이 재귀적 분해에는 패턴이 보이기도 한다. 정수 : 수를 줄여나간다. n-1 or n-2 배열 : 앞의 숫자를 없애 길이를 줄인다. [1, 2, 3, 4] → [2, 3, 4] → [3, 4] 링크드 리스트 : 포인터가 가리키는 다음 노드가 input으로 들어간다.
서경태
TIL 웹개발 - DFS, BFS
DFS(Depth Fisrt Search) 깊이우선탐색으로 말 그대로 연결된 노드 트리를 따라 끝까지 탐색 후 다시 올라와 나머지를 탐색한다. 위와 같은 노드 트리를 탐색한다면 순서는 아마 [0, 1, 3, 4, 2]가 될 것이다. DFS를 재귀함수로 구현한 코드다. 함수에 함수가 쓰여 조건이 달성될 때까지 반복한다. BFS( Breadth First Search) 너비우선탐색으로 노드트리를 위에서 아래로 차례대로 탐색하는 특징을 갖고 있다. DFS와 달리 BFS로 위 노드 트리를 탐색하면 [0, 1, 2, 3, 4]의 순서를 가진다. 코드로 표현하면 아래와 같다. deque를 사용해 탐색할 노드의 맨 앞에서부터 가져오기때문에 아래에서 위로 순차적인 탐색이 가능하다. dfs, bfs의 특징을 이용해 풀 수 있는 문제가 나뉘기도하고 혹은 두 방법으로 동일한 문제를 풀 수도 있다.