[알고리즘] 구현

구현

• 구현 유형의 문제들 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'
• 까다로운 구현 유형의 문제들
  • 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
  • 특정 소수점 자리까지 출력해야 하는 문제
  • 문자열이 입력으로 주어졌을 때 한 문자 단위로 큲어서 리스트에 넣어야하는 문제
• 구현 유형: 완전 탐색, 시뮬레이션 유형
  • 완전 탐색: 모든 경우의 수를 주저 없이 다 계산해야하는 해결 방법
  • 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계식 차례대로 직접 수행
• 코딩 테스트에서는 어떤 환경에서 문제를 풀어야하는지를 알고 그 환경에 맞게 프로그래밍 언어를 적절히 사용하여 구현하는 일이 중요하므로, 먼저 코딩 테스트 채점 시스템의 제약에 대해 설명한 후 문제를 다루겠다.

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

• 파이썬에서 리스트 크기

  • 데이터 처리량이 많을 때는 리스트를 여러 개 선언

  • 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야 한다는 것!

    데이터의 개수(리스트의 길이)	메모리 사용량
    1,000	약 4KB
    1,000,000	약 4MB
    10,000,000	약 40MB

구현 문제에 접근하는 방법

• Pypy3는 파이썬3의 문법을 그대로 지원하며 대부분 파이썬 3보다 실행 속도가 더 빠르다. 반복문이 많을수록 파이썬3과 Pypy3의 속도가 차이가 난다. Pypy3도 지원한다면 이를 이용하라