티스토리 뷰
반응형
프로그래머스의 도넛과 막대 그래프 문제를 풀면서 시간초과가 발생했다.
from collections import defaultdict
def solution(edges):
answer = [0, 0, 0, 0]
graph = defaultdict(list)
out_ = defaultdict(int)
in_ = defaultdict(int)
for e in edges:
graph[e[0]].append(e[1])
out_[e[0]] += 1
in_[e[1]] += 1
centor_node = [g for g in graph.keys() if out_[g] >=2 and in_[g] == 0][0]
answer[0] = centor_node
doughnut = 0
bar = 0
eight = 0
visited = set() # 시간 초과 발생을 일으킨 부분
for start_node in graph[centor_node]:
visited.add(start_node)
curr = start_node
while curr:
if out_[curr] == 0:
bar += 1
break
elif out_[curr] == 2:
eight+=1
break
curr = graph[curr][0]
if curr in visited and out_[curr] == 1:
doughnut+=1
break
visited.add(curr)
answer[1] = doughnut
answer[2] = bar
answer[3] = eight
return answer
위의 코드를 보면 visited 변수 부분에 원래는 리스트 자료구조를 사용했다. 리스트 자료구조를 사용하니 시간초과가 발생해서 set 자료구조로 변경 했더니 시간초과가 해결이 되었다. set은 중복된 값을 허용하지 않는 자료구조로 알고 있는데 두가지 자료구조의 속도 차이가 있는 것 같아 알아보았다.
ChatGPT 답변
- 리스트(List):
- 탐색(Search): 리스트는 순차적으로 요소를 찾아야 하기 때문에 시간 복잡도가 O(n)입니다. 즉, 리스트의 길이에 비례하여 시간이 증가합니다.
- 삽입/삭제(Insertion/Deletion): 리스트의 끝에 추가하는 작업은 평균적으로 O(1)이지만, 중간에 삽입하거나 삭제하는 경우 O(n) 시간이 소요됩니다.
- 집합(Set):
- 탐색(Search): 집합은 해시 테이블을 사용하기 때문에, 요소를 찾는 작업이 평균적으로 O(1) 시간 복잡도를 가집니다. 따라서 대량의 데이터가 있을 때 매우 빠릅니다.
- 삽입/삭제(Insertion/Deletion): 집합에 요소를 추가하거나 제거하는 작업도 평균적으로 O(1)이므로 리스트보다 훨씬 빠릅니다.
결과적으로 정리해보면 아래와 같이 차이점이 있다는 것을 알 수 있다. 순서가 중요하지 않는 경우 set을 사용하면 탐색 속도면에서 더욱 빠르다!
Aspect | 리스트 (List) | 집합 (Set) |
---|---|---|
시간 복잡도 (탐색) | O(n) - 순차 탐색 | O(1) - 해시 기반 탐색 |
시간 복잡도 (삽입/삭제) | O(n) (중간 삽입/삭제), O(1) (끝 삽입/삭제) | O(1) - 평균 |
순서 보장 | 보장됨 | 보장되지 않음 |
인덱싱 가능 여부 | 가능 | 불가능 |
중복 허용 여부 | 허용 | 허용하지 않음 |
메모리 사용량 | 효율적 (해시 테이블 없음) | 비효율적 (해시 테이블로 인한 메모리 사용 증가) |
반응형
'Programming > 자료구조 및 알고리즘' 카테고리의 다른 글
[자료구조] 접두사에 강한 트라이(Trie) (0) | 2024.08.23 |
---|---|
[자료구조] 해시테이블 클로즈 기법 개념 및 구현 with 파이썬(Python) (0) | 2022.08.28 |
[자료구조] 해시테이블 체이닝 기법 개념 및 구현 with 파이썬(Python) (0) | 2022.08.27 |
[자료구조] 링크드리스트 파이썬으로 구현 (0) | 2022.08.24 |
[알고리즘] 버블 정렬이란 (Java, Python) (0) | 2022.08.14 |
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 카카오페이
- FastAPI
- 파이썬
- 다이나믹프로그래밍
- 시간초과
- 프로그래머스
- 정보보안기사
- Ai
- 보안
- t검정
- springboot
- synflooding
- java
- 리눅스
- 우선순위큐
- 그리디
- 백준
- lightsail
- LangChain
- t-test
- linux
- 코딩테스트
- 자료구조
- 정보보안
- 분산시스템
- 보안기사
- 카카오페이면접후기
- llm
- Python
- 딥러닝
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
글 보관함