문제 풀다 시간 제한 걸릴 때 참고사항

📌 최대 시간이 1초일 때 입력 데이터 수에 따른 시간 복잡도

▪ 1,000개  -> O(n2) 이하

▪ 10,000 -> O(n2) 미만

▪ 100,000 -> O(nlogn) 이하

▪ 1,000,000 -> O(nlogn)미만

▪  그 이상이라면 -> 입력 데이터 수가 백만 개 이상이라면 문제의 조건을 유심히 살펴보기 , 특정 알고리즘을 사용하도록 요구할 가능성이 큼

 

 

📌 자주  사용하는 자료 구조에 따른 시간 복잡도

자료 구조	탐색	삽입	삭제
배열	O(n)	O(n)	O(n)
정렬된 배열	O(logn)	O(n)	O(n)
연결 리스트	O(n)	O(1)	O(1)
스택/큐	O(n)	O(1)	O(1)
해시	O(1)	O(1)	O(1)
이진 트리	O(logn)	O(logn)	O(logn)

 

 

📌 문제 풀다 시간 제한 걸리는 이유

연산이 비효율적이거나, 입력값과 맞지 않는 알고리즘을 사용했기 때문이다.

‘1억 번 연산에 1초 걸린다.’ => CPU가 1초에 1억번 연산하기 때문이다.

입력 데이터 10만 개를 정렬하는 경우 => for문 2개로 계산하면 O(n2)이므로 10만 X 10만 = 100억 정도의 연산이 발생

=> 시간초과 !!!

 

 

📌내장 함수 시간 복잡도를 이용해 시간 복잡도 어림짐작하기

🔹 리스트 (list; [ ])

O(1)	조회	data[1]
	값 할당	data[1]=1
	길이 가져오기	len(data)
	리스트 1개 추가	data.append(2)
	마지막 리스트 1개 제거	data.pop()
	리스트 초기화	data.clear()
O(n)	리스트 슬라이싱	data[a:b]
	리스트 + 리스트	data.extend(data2)
	리스트 할당	list(data)
	리스트 비교	data=data2/data != data2
	값 범위 할당	data[a:b] = 3
	특정 리스트 항목 제거	del data[1] / data.pop(1)
	리스트에 값이 있는지 확인	1 in data
	리스트 복사	data.copy()
	최솟값/최댓값 탐색	min(data), max(data)
	리스트 역순	data.reverse()
	리스트 전체 연산	for v in data :
O(nlogn)	리스트 정렬	data.sort() / sorted(data)
O(Kn)	데이터 전체 반복	2 * data

 

 

📌 sys.stdin.readline()

: input() 보다 속도가 빠르며 시간 초과 문제를 해결할 수 있다.

 

1. 문자열 입력 받을 때

import sys

str = sys.stdin.readline()

 

2. 한 개의 정수를 입력 받을 때

import sys

str = int(sys.stdin.readline())

 

3. 정해진 개수의 정수를 입력 받을 때

import sys

a, b = map(int, sys.stdin.readline().split())

 

4. N줄의 문자열을 입력 받아 리스트에 저장할 때

import sys

n = int(sys.stdin.readline())
data = [sys.stdin.readline().strip() for i in range(n)]