책 'Do it! 알고리즘 코딩 테스트 파이썬편'
책이 8월 16일에 나왔다.
코딩테스트가 한창이기 때문에 빠르게 구입해서 빠르게 공부해서 빠르게 합격해야한다.
시작👊
Do it 알고리즘 코딩테스트 는 자바편이 있어서 자바편(5월에 나온거 같음) 살려고했는데,
16일에 나온다길래 예약구매하고, 어제 받음.
소문만 듣던 시간 복잡도!
시간 복잡도 표기법 알아보기
코딩테스트의 핵심 중 하나는 문제마다 주어진
시간 복잡도를 고려해 적절한 알고리즘을 선택하는 것입니다. 시작부터 알고리즘을 잘못 선택하면 아무리 코드를 잘 짜려고 노력해도 좋은 결과를 거두기 어려우니까요. 문제를 풀어보기 전에시간 복잡도를 표기하는 방법과 활용하는 방법을 익혀봅시다!
알고리즘에서
시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말합니다.
시간 복잡도 유형
빅 오메가(Ω(n)):최선일 때(best case)의 연산 횟수를 나타낸 표기법빅 세타(Θ(n)):보통일 때(average case)의 연산 횟수를 나타낸 표기법빅 오(O(n)):최악일 때(worst case)의 연산 횟수를 나타낸 표기법
import random
# 1~100 사이 랜덤값 생성
findNumber = random.randrange(1, 101)
for i in range(1, 101):
if i == findNumber:
print(i)
break여기서
빅-오메가 표기법의 시간 복잡도는 1번,
빅-세타 표기법의 시간 복잡도는 N/2 번,
빅-오 표기법의 시간 복잡도는 N 번입니다.
책에서 자세한 설명은 없지만, 코드는 랜덤으로 나온 값(i)이 찾는 값(findNumber)과 같을 때 멈출 거다.
for 문이 연산을 한 번 했을 때 i와 findNumber 가 같은 게 최선이지. 빅-오메가임.
최악은 전부 돌려서, 그러니까 전체 경우의 수가 N번이니까 그 전부인 N번 돌렸을 때 두 값이 맞는 것. 빅-오임.
빅-오메가와 빅-오의 중간 값(average) 는 빅-세타.
코딩테스트에서는 어떤 시간 복잡도 유형을 사용해야 할까?
코딩 테스트에서는
빅-오표기법을 기준으로 수행시간을 게산하는 것이 좋습니다.
응시자가 작성한 프로그램으로 다양한 케이스를 수행해 모든 케이스를 통과해야만 합격으로 판단하므로 시간 복잡도를 판단할 때는 최악일 때를 염두해둬야 합니다.
시간 복잡도 활용하기
알고리즘 선택의 기준으로 사용하기
우리가 이 책에서 정렬 부분의 학습을 완료했고, 버블 정렬과 병합 정렬의 시간 복잡도를 각각 알고있다고 가정하고 ...
예? 여기가 19페이지 아닌가요?
정렬은 93페이진데요...
아니 그러면 먼저 공부하고 오라고 하시지 ;;;
저 같은 댕청이들은 말 안 해주면 모른단말이예요ㅠㅠ...
개열받기 때문에
33페이지 자료구조부터 시작한다.
