나의 파이썬 코딩테스트 여정_1

왜 파이썬인가
동일한 구현에 필요하며 코드가 짧은 편이라 시간이 제한적인 상황에서 용이하며, 특정한 서버로 요청을 보내는 request 라이브러리와 반환된 Json파일을 읽어오는 Json 라이브러리가 있어 API와 통신과 같은 부분을 개발할 때 효율적이다.

1차 문제풀이 충족 순서
1. 답맞추기
2. 성능 복잡도 줄이기
3. 시각적인 복잡도 줄이기

2차 문제풀이 충족 순서
1. 지문 파악 및 복잡도 분석
2. 풀이 설계
3. 풀이 작성

마스터 유형 순서
1. BFS/DFS
2. 그리디
...

성능평가(코테 문제는 명시되어있지않다면 시간제한이 1~5초)
복잡도

• 시간복잡도 : 입력에 대한 수행시간
• 공간복잡도 : 입력에 대한 메모리 사용량
• 시각적인 측면이 아닌 성능적 측면에서의 복잡도를 말함
• 빅오 표기법 : 가장 빠르게 증가하는 항만을 고려
• 상수시간, 로그시간, 선형시간, 로그선형시간, 이차시간, 삼차시간, 지수시간 등 존재

알고리즘 설계

• 일반 CPU 기반 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우 : C언어는 1~3초 가량, Python은 5~15초 가량 소요, PyPy의 경우 때로는 C언어보다 빠르게 동작하는 경우도 존재
• 시간제한 1초 기준으로 알고리즘 설계 기준
• N 범위가 500 : O(N3)
• N 범위가 2000 : O(N2)
• N 범위가 100,000 : O(NlogN)
• N 범위가 10,000,000 : O(N)

지수표현방식 공부하기

• e 또는 E 다음에 오는 수 : 10의 지수부
• 1e9 = 10의 9제곱(1,000,000,000)
• 유효숫자e지수제곱 = 유효숫자 * 10지수제곱
• 임의의 큰 수를 표현할 때 자주 사용
• 최단 경로 알고리즘에서는 도달할 수 없는 노드에 대한 최단거리를 무한(INF)로 설정
• 가능한 최댓값이 10억 미만이라면 무한(INF)의 값으로 1e9이용가능