-
머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정.
-
구현이 중심이 되는 문제가 자주 출제된다.
-
풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제.
-
완전 탐색, 시뮬레이션 유형 -> '구현' 유형으로 분류한다.
-
피지컬 요구하는 문제...
-
완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행
-
코딩 테스트에서는 어떤 환경에서 문제를 풀어야 하는지를 알고 그 환경에 맞게
프로그래밍 언어를 적절히 사용하여 구현하는 것이 중요
-
실수형 변수는 유효숫자에 따라서 연산 결과가 원한는 값이 않나올 수 있음. (0.3+0.6=0.899..)
-
보통 코테 128~512MB로 메모리 제한, 수백만 개 이상 데이터 처리시 메모리 염두.
-
리스트의 길이 1,000,000 = 약4MB / 1,000 = 약4KB / 10,000,000 = 약40MB
-
리스트를 여러 개 선언하고, 그중에서 크기가 1,000만 이상인 리스트가 있다면 주의(드물다)
-
애초에 대회 문제가 아니면 복잡한 최적화를 요구x
-
2020년 파이썬3.7 기준, 자신의 코드가 1초에 2,000만 번의 연산을 수행한다고
가정하고 문제를 풀면 실행 시간 제한에 안정적이다.
-
시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제가 있다면
일반적으로 시간 복잡도O(NlogN)이내의 알고리즘을 이용하여 문제를 풀어야 한다.
N =1,000,000일 때 NlogN이 약20,000,000
-
코딩테스트 환경에 Pypy3가 있다면 파이썬3 보다 Pypy3를 선택하자. 최대 5배 빠르다.
-
API 개발 문제 또한 구현 유형과 상당히 맞닿아 있음. (ex.카카오-웹서버,데이터 분석 기초 지식)
