코드의 실행 시간이 오래 걸리는 이유는? 연산량!
계산량은 '입력'과 관련이 있다.
sum() 의 연산량은?
더하기 연산 n번 + 반복문 n번 = 2n
연산과 시간
- 연산에 따라 속도는 각각 다름
- 모든 연산을 Counting할 수는 없음
- 최악의 경우와 최선의 경우
- 실행시간이 달라질 수 있음 - 컴퓨터, 서버의 CPU성능에 따라
Big-O 표기법
시간 복잡도를 '대충'계산하기 위한 표기법
항상 최악의 경우를 가정한다.
O(1) 의 예시
1부터 n까지의 합 구하기 → 단순한 수식으로 표현가능
def sum(n):
return n*(n+1)//2O(n)의 예시
길이가 N인 수열에서 K라는 수 찾기, 합계 구하기, 최솟값, 최댓값 찾기
→ 최악의 경우 n번 반복해야 답을 구할 수 있음. 확률적으로는 n/2번
def search(arr, n, k):
for i in arr:
if i == k:
return True
return FalseO(logN)의 예시
업다운 게임이 대표적.
수열이 정렬되어 있을 경우 사용하면 빠르게 찾을 수 있음.
수열의 길이가 계속 절반씩 줄어들기 때문에 log2N → logN 이 된다.
이진탐색 등 균등하게 쪼개지는 경우 logN인 경우가 많다.
def binary_search(arr, n, k):
low, high = 0, n-1
while low <= high:
mid = (low + high) // 2
if arr[mid] == k:
return True
if arr[mid] > k:
high = mid - 1
else:
low = mid + 1
return False표현법와 감
계산 + 시스템에 대한 감이 중요!
파이썬 코드로 천만~오천만 연산을 1초안에 할 수 있다면 안정적. 그러나 시스템마다 다름!
예제로 알아보기 - 수 이어 쓰기
시간, 메모리 입력, 출력
이 문제의 제한 시간은 0.5초이다(파이썬의 경우)
그러나 입력값의 범위가 10억개이므로 단순히 for문을 사용한 알고리즘은 최악의 경우 10억개의 연산을 수행해야 한다. (O(n)알고리즘 이상은 통과 불가능!)
일반적인 풀이 - O(NlogN)
def solution(n):
ret = 0
for i in range(1, n+1):
ret += len(str(i))
return ret
# 좀더 Pythonic한 풀이
def solution(n):
return sum(map(lambda x: len(str(x)), range(1, n+1)))반복문에서 N, str연산에서 logN의 시간복잡도가 발생한다.
중간 과정에 반드시 필요한 로직
수의 길이를 구하는 로직은 반드시 필요하다.
수의 길이는 나머지가 0일 때까지 10으로 나눈 횟수이므로 시간복잡도는 log10N이 된다.
나의 코드
n = input()
result = 0
for i in range(len(n)):
if i == len(n)-1:
result += len(n)*(int(n)-(10**i-1))
else:
result += 9*(10**i)*(i+1)
print(result)자릿수별로 분리하여 합계를 구하고, 이를 총합하여 결과를 출력한다.
n 이 120이라면, 1자리수9개 + 2자리수99개+3자리수*21개
좀더 간결한 코드
def solution(n):
l, ret = len(str(n)), 0
for i in range(1, l):
ret += i * (10**i - 10 ** (i-1))
ret += l * (n - 10 ** (l-1) + 1)
return ret1부터 L-1까지(마지막자릿수 전까지) for문을 돌려, return 변수에 91, 992, 999*3 씩 더해준다.
마지막자릿수의 개수를 구해서 마지막자릿수와 곱하여 최종으로 더해 결과를 반환한다.
마지막 자릿수가 2자리라면 n-9, 3자리라면 n-99, 4자리라면 n-999 라는 규칙을 갖는다.
예제로 알아보기 - 주사위 네개 ⭐ 자주 나오는 문제!!
🔖 읽기와 분석 외전
입력과 초기화 팁
- Map과 Comprehension
- 입력의 대표 사례 3가지
- num = int(input())
- string = input()
- char_arr = list(input()) → 다시 문자열로 바꾸기 : join 사용
- arr = list(map(int, input().split()))
- map(x, y)는 x함수를 y의 원소에 모두 적용한 후 map 객체를 반환한다.
- list 초기화 - 표현식 사용
- arr1d = [0 for in range(N)]
- arr2d = [[0 for in range(N)] for j in range(N)]
- 같은 표현법으로 딕셔너리, 튜플 등도 만들 수 있음
- 입력의 대표 사례 3가지
에러 메시지
- 맞았습니다 : 모든 TC를 시간제한과 메모리제한에 맞춰 통과
- 틀렸습니다(Wrong Answer) : 특정 TC에 대해 정답이 틀림
- 컴파일 에러 : 보통 틀린 문법에 의해 생김
- 런타임 에러 : 돌아가는 과정 상에 에러 발생(0으로 나누기, 잘못된 메모리 참조 등)
- 메모리 초과 : 메모리 터짐
- 시간초과 : 시간 터짐, 더 좋은 알고리즘 또는 최적화 필요
- 출력 에러 : 없는 사이트도 있음. 출력이 너무 길어져버린 경우 등
추상화와 기능분리
- 함수의 활용 - 대부분의 내용은 함수화하는 것이 적절
가독성 - 코드를 간결하게
조건문, 반복문, 함수 모두 줄일 부분은 줄이기
indent 최대한 줄이기!
for i in range(N):
for j in range(N):
for k in range(N):
# i, j, k process
for num in range(N**3):
i, j, k = num // (N*N), num // N % N, num % N
# 세 방법 중 아무거나 사용 가능. 결과는 같음 for i in range(N):
if state :
process()
# indent 를 한 단계 줄이기 위해 처리하지 않고 지나가야 하는 경우를 continue를 통해 배제
for i in range(N):
if not state : continue
process()def function(x):
if x:
return True
else:
return False
def function2(x):
if x: return
return False # else 대신 그냥 False를 리턴
def function3(x):
return True if x else False명명법
- 주로 변수에 snake, 함수에 카멜케이스 사용
