python 코테 준비 - 개괄

https://www.youtube.com/watch?v=m-9pAwq1o3w&t=5367s

 

 

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

 

---

온라인 코테를 위한 개발환경 준비

repl, 파이썬 튜터, 파이참

개발과는 차이점이 있기 때문에 온라인 개발 환경이용 + 깃헙에 올리는 방

---

그리디

구현

DFS/BFS를 이용한 탐색

탐색

DP

구현

문자

가 주로 나온다고 함.

---

복잡도

- 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석

- 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

일반적으로 복잡도가 낮을수록 좋은 알고리즘

빅 오 표기법(Big-O Notation)

가장 빠르게 증가하는 항 만을 고려하는 표기법

- 함수의 상한만을 나타내게 된다.

- 차수가 가장 큰 항만 남긴다.

예시는 다음과 같다.

C언어가 Python 보다 빠름.

Python 코드를 잘 작성했고, 시간 복잡도를 고려했음에도 불구하고 느리게 나온다면 -> Pypy

요구사항에 따른 적절한 알고리즘 설계

파이썬 기준, 1초에 2000만번의 연산 안정적 수행 가정했을때,

시간 제한이 1초인 문제를 만났을때

- N 의 범위 500 : 시간 복잡도가 O(N^3)인 알고리즘 설계

- N 의 범위 2000 : 시간 복잡도가 O(N^2)인 알고리즘 설계

- N 의 범위 100,000 : 시간 복잡도가 O(NlogN)인 알고리즘 설계

- N 의 범위 100,000,000 : 시간 복잡도가 O(N)인 알고리즘 설계

 

수행시간 측정 소스코드 예제

import time
start_time = time.time() # 측정 시작

# 프로그램 소스코드
end_time = time.time() # 측정 종료
print("time:", end_time - start_time) # 수행 시간 출력