구현

구현

• 머릿 속에 떠오르는 아이디어를 소스코드로 바꾸는 과정이다.
• 어떤 문제든 모든 범위의 코딩 테스트 문제는 구현 문제에 포함된다.
• 보통, 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미한다.
  • 알고리즘은 간단한데 코드가 길어지는 문제
  • 특정 소수점 자리까지 출력하는 문제
  • 문자열을 한 문자 단위로 끊어서 파싱해야 하는 문제
• 완전 탐색, 시뮬레이션은 둘 다 구현이 핵심이 되는 경우가 많기 때문에 이 장에서 다룬다.

구현 시 고려해야 할 메모리 제약 사항 (Python)

• 파이썬에서 리스트 크기데이터 개수(리스트 길이) 메모리 사용량

  1,000	약 4KB
  1,000,000	약 4MB
  10,000,000	약 40MB

  크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다는 점을 기억한다.
• 대체로 코딩테스트에서 128 ~ 512MB로 메모리를 제한하기 때문에 수백만 개 이상의 데이터를 처리할 때는 메모리 제한을 염두해야 한다.
• 입출력 소요 시간
• 채점 환경

채점 환경 (Python)

• 파이썬은 c/c++ 보다 동작 속도가 느리다.
• 일반적으로 시간 복잡도가 O(NlogN) 이내의 알고리즘을 사용해 풀어야 한다.
• 알고리즘 문제를 풀 때는 시간제한, 데이터 개수를 먼저 확인하자.

 

(계속 추가 중)