교대최소제곱법
[백준 파이썬 1647번 도시 분할 계획] 튜플과 리스트의 시간 차이 본문
https://www.acmicpc.net/problem/1647
1647번: 도시 분할 계획
첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번
www.acmicpc.net
튜플은 리스트와 달리 불변성인 특성을 이용하여 빠르게 iteration을 돌 수 있다.
특히 이번 같은 경우 간선의 수가 많고 iteration을 많이 돌아야 하는 빡빡한 문제였기 때문에 튜플을 사용해야한다!!
시간 초과가 나거나 값을 바꾸지 않아도 되는 문제라면 튜플을 이용해보자!
// 튜플 사용 = pass
for _ in range(M):
a, b, c = map(int, input().split())
graph[a].append((c, b))
graph[b].append((c, a))
// 리스트 사용 = 시간초과
for _ in range(M):
a, b, c = map(int, input().split())
graph[a].append([c, b])
graph[b].append([c, a])
https://www.acmicpc.net/board/view/98110
글 읽기 - 프림 알고리즘으로 풀었을때 시간 초과가 납니다
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
https://itholic.github.io/python-list-tuple/
[python] 파이썬 list와 tuple의 차이
파이썬 list, tuple 차이
itholic.github.io
'코딩테스트' 카테고리의 다른 글
| [백준 파이썬 12015번 가장 긴 증가하는 부분 수열 2] DP, Bisect (0) | 2023.10.05 |
|---|---|
| [백준 파이썬 1005번 ACM Craft] 위상정렬 (0) | 2023.09.26 |
| [백준 파이썬 1197번 최소 스패닝 트리] 크루스칼 알고리즘, 프림 알고리즘 (0) | 2023.09.24 |
| [백준 파이썬 1629번 곱셈] 분할 정복 (0) | 2023.09.12 |
| [백준 파이썬 11404번 플로이드] 플로이드 워셜 알고리즘 (0) | 2023.09.12 |