해당 글은 "이것을 위한 코딩 테스트다 with python" (나동빈), 바킹독
(bakkkkkkingdok)을 보며 참고하여 작성한 글입니다.
시간 복잡도, 공간복잡도 이해하기
바킹독을 통해서 시간, 공간복잡도를 이해했지만, 해당 내용을 적용하기에는 미숙 하다고 생각했다.
이번기회에 코딩테스트에서 적용 및 이해하기 위해서
"이것을 위한 코딩 테스트다 with python" (나동빈)의 책을 보며 잘 이해해 보려고한다.
✔️ 복잡도 (Complexity)
복잡도는 알고리즘의 성능을 나타내는 척도
시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
단순히 코드가 복잡하다는 것이 아닌, 성능적에서의 측면을 말한다.
- 우리는 이것을 빅오표기법으로 표기한다.
- 빠르게 증가하는 항만을 고려한다.
- 함수의 상한만을 나타내게 된다.
ex ) 3n^3 + 5n^2 + 1000000 인 알고리즘이 있다고 가정
빅오 표기법에서는 차수가 가장 큰 항만 남기므로 O(N^3)으로 표현된다
나동빈 ver
바킹독 ver
array = [1,2,3,4,5] # 5개의 데이터 ( N =5 )
summary = 0 # 합계를 저장할 변수
# 모든 데이터를 하나씩 확인하며 합계를 계산
for i in range(5):
summary += i
# 결과를 출력
print(summary)- 수행 시간은 데이터의 개수 N에 비례할 것을 예측
시간 복잡도: O(N)
n이 100억이 넘어가면 비례하여 올라갈 것 이다.
array = [3,5,1,2,4]
for i in arrry:
for j in array:
temp = i * j
print(temp)
시간복잡도: O(N^2)- 참고로 모든 2중 반복문의 시간 복잡도가 O(N^2)인 것은 아니다.
- 소스코드가 내부적으로 다른 함수를 호출한다면 그 함수의 시간 복잡도까지 고려해야한다.
log부분이 이해가안가서 참고
- 로그 log 뜻
로그는 로가리즘logarithm의 줄임말이다.
❗로그log
지수exponent와 역inverse의 관계다.
2를 몇 번 곱해야 N이 나올까? = log₂N
1이 될 때까지 N을 2로 몇 번 곱해야 할까? = log₂N
지수exponent와 역inverse의 관계다.
log₂8은 2³의 역converse 관계다.
log₂64은 2⁶의 역이다.
- 2를 몇 번 곱해야 N이 나올까?
2를 세 번 곱해야 8이 나오므로 log₂8 = 3이다.
2를 여섯 번 곱해야 8이 나오므로 log₂64 = 6이다.
- 1이 될 때까지 N을 2로 몇 번 곱해야 할까?
8 / 2 / 2 / 2 = 1
8이 1이 될 때까지 2를 세 번 나눠야 하므로 log₂8 = 3이다.
64 / 2 / 2 / 2 / 2 / 2 / 2 = 1
64가 1이 될 때까지 2를 여섯 번 나눠야 하므로 log₂64 = 6이다.
O(logN) == O(log₂N)
컴퓨터 과학에서 O(logN)은 O(log₂N)을 줄여 부르는 말이다.
핵심 질문 : 데이터 원소가 N개 일 때 알고리즘에 몇 단계가 필요할까?
정답 : O(logN)은 데이터 원소가 N개 있을 때 알고리즘에 log₂단계가 걸린다.
원소가 8개면 log₂8 = 3이므로 이 알고리즘은 3단계가 걸린다.
이진 검색이 정확히 O(logN) 알고리즘 방식으로 동작한다.
이진 검색을 빅 오 표기법의 관점에서 어떻게 설명할까?
배열의 크기가 3일 때 이진 검색은 2단계
배열의 크기가 7일 때 이진 검색은 3단계
배열의 크기가 15일 때 이진 검색은 4단계
배열의 크기가 100일때 이진 검색은 7단계
배열의 크기가 10,000일때 이진 검색은 13단계
배열의 크기가 1,000,000일때 이진 검색은 20단계
데이터가 커질수록 단계 수가 늘어나므로 이진 검색은 O(1)이라 표현할 수 없다.
검색하고 있는 배열의 원소 수보다 단계 수가 훨씬 적으므로 O(N)이라 표현할 수도 없다.
이진 검색은 O(1)과 O(N)사이 어디쯤엔가 있다.
이것을 빅 오로 O(logN)으로 나타낸다.
그리고 오 로그 엔 이라고 부른다.
✔️ 알고리즘 설계 Tip
-
일반적으로 cpu 기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우
python 기준으로 통상 5~15초 소요 -
pypy의 경우 때때로 C언어보다도 빠르게 동작함
-
O(N^3)의 알고리즘을 설계한 경우 N의 값이 5000이 넘는다면 ? -> 1250억 2500초 시간 발생
-
코딩 테스트 문제에서 통상
1~5초가량 -
혹여 문제에 명시되어 있지 않는 경우는
대략 5초
일반적인 CPU 기반의 PC나 채점용 컴퓨터에서 1초에 실행할 수 있는 최대 연산 횟수는 약 1억번이다.
내풀이가 이문제를 제한 시간내로 통과 수 있는지 즉 , 내알고리즘의 시간복잡도가 올바른지 꼭 생각해봐야한다.
예를들어 N = 500 이면 O(2^N)을 생각해 냈다면 답을 낼 수 없기 때문에 잘못된 풀이 인것이다.
시간복잡도를 고려하지않고 풀이를 진행한다면 1시간을 걸려서 실컷 다 짜고 제출을 한 후에야 시간초과가 난다는 것을 깨닫고 절망에 빠질것이다
✔️요구사항에 따라 적절한 알고리즘 설계하기
- 문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항)입니다.
- 시간제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같다.
1초에 2000만번 연산을 안정적으로 설계 가정
N의 범위가 500인경우 -> 시간 복잡도가 O(N^3)인 알고리즘을 설계
N의 범위가 2000인경우 : 시간 복잡도가 O(N^2)인 알고리즘을 설계
N의 범위가 100,000인경우 : 시간 복잡도가 O(NlogN)인 알고리즘을 설계
N의 범위가 10,000,000인경우 : 시간 복잡도가 O(N)인 알고리즘을 설계
✔️알고리즘 문제 해결 과정
- 일반적인 알고리즘 문제 해결 과정은 다음과 같다.
- 지문 읽기 및 컴퓨터적 사고
- 요구사항(복잡도) 분석
- 문제 해결을 위한 아이디어 찾기
- 소스코드 설계 및 코딩
일반적으로 대부분의 문제 출제자들은 핵심 아이디어를 캐치한다면, 간결하게 소스코드로 작성할 수 있는 형태로 문제를 출제한다.
✔️수행 시간 측정 소스코드 예제
import time
start_time = time.time() # 측정 시작
# 프로그램 소스코드
end_time = time.time() # 측정 종료
print("time:" , end_time - start_time) # 수행 시간 출력