[이코테] ch4. 구현

Ch4. 구현

완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결방법

시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

변수

파이썬에서는 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본으로 지원

리스트 크기

 💡 코딩 테스트의 메모리 제한을 고려해야 한다.

 

메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야 한다.

채점 환경

알고리즘 문제를 풀 떄는 시간 제한과 데이터의 개수를 먼저 확인한 뒤 이 문제를 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 지 예측할 수 있어야 한다.

• 대부분의 코딩 테스트 환경
  • 시간 제한 : 1초
  • 메모리 제한 : 128MB
• 일반적으로 시간 복잡도 O($NlogN$) 이내의 알고리즘 이용해서 문제풀기

구현 문제에 접근하는 방법

사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 긴 편.

PyPy3는 파이썬3의 문법을 그대로 지원하며 파이썬3보다 실행 속도가 빠르다. 따라서 PyPy3를 지원하면 이를 이용하도록 하자.

코테나 알고리즘 대회에서 가장 난이도가 낮은 1~2번 문제는 대부분 그리디 알고리즘이나 구현 문제이다.