Ch4.구현

1. 아이디어를 코드로 바꾸는 구현

피지컬로 승부하기

• 구현 유형의 문제 = 피지컬을 요구하는 문제
• 까다로운 구현 문제 유형
  • 코드가 길어지는 문제
  • 특정 소수점 자리까지 출력해야 하는 문제
  • 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제
    => 사소한 조건 설정이 많은 문제일수록 코드로 구현하기 까다로움.
• 유형:
  
  1. 완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방안
  2. 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

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

C/C++에서 변수의 표현 범위

• int
  • 4바이트
  • -2,147,483,648 ~ 2,147,483,648
• long long
  • 8바이트
  • -9223372036854775808 ~ 9223372036854775808
• BigInteger
  • 외부 라이브러리로 제공

⭐파이썬에서는 신경 쓸 필요X

파이썬에서 리스트 크기 ⭐코딩 테스트에서는 128 ~ 512 MB로 메모리 제한

|데이터의 개수(리스트의 길이)|메모리 사용량| |——|—| |1000|약 4KB| |1000000|약 4MB| |10000000|약 40MB| => 크기가 1,000만 이상인 리스트는 이용할 수 X

채점 환경

• 코딩 테스트 환경의 채점 시스템에서의 시간 제한과 메모리 제한 정보 확인!
• ⭐파이썬으로 제출한 코드가 1초에 2000만 번의 연산을 수행한다고 가정
  ex) 시간 제한이 1초 / 데이터의 개수가 100만 개 -> 일반적으로 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용해야 한다.

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

구현 문제에 접근하는 방법

• Pypy3 이용! -> 1초에 1억 번 정도의 연산 처리