[구현] 아이디어를 코드로 바꾸는 구현

피지컬로 승부하기

- 구현이란 '머리속에 있는 알고리즘을 소스코르도 바꾸는 과정'이다

- 구현 유형의 문제는 ' 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제' 이다

- 구현하기 어려운 문제란 ?

    1. 알고리즘은 간단하지만 코드가 지나치게 길어지는 문제

    2. 특정 소수점 자리 까지 출력하는 문제

    3.문자열이 이볅으로 주어졌을 때 한문자 단위로 끊어서(파싱하여) 리스트에 넣어야 하는 문제

- 사용 언어의 문법을 잘 이해하고 라이브러리 사용 경험이 많아야 한다.

    ex) N개의 원소중 R 개를 골라 리스트에 저장 하는 경우 

           - 반복목으로 기능을 전부 작성할 수 있지만 itertools같은 표준 라이브러리로 쉽게 짤수 있다

- 현 교재에서는 '완전 탐색', '시물레이션' 유형을 '구현' 유형으로 묶어서 다룬다. 

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

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

 

 

 

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

파이썬에서의 리스트 크기 

- 파이썬에서는 여러개의 원소를 다룰 때 리스트를 사용한다

- 대체로 코딩테스트에서는 128- 512MB로 메모리를 제한한다.

- 100만개 이상의 입력 데이터를 다룰 시에는 메모리 제한을 염두해 두고 로직을 생각해야한다.

- 대략 아래와 같은 크기의 리스트에 맞게 메모리가 사용 된다.

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

 

- 파이썬은 다른 언어에 비해 구현은 쉽지만, 데이터 처리량이 많은 경우 꼭 메모리 제한을 고려하자

- 1000만 이상인 리스트가 있다면 메모리 용량 제한으로 인해 문제를 풀 수 없게 되는 경우도 있음을 고려하자

- 하지만 실제 코딩테스트 시스템의 이유(입력값이 많으면 입력 받는 속도에도 제한이 생김)로 인해 위 메모리 사용량 이상은 굳이 고려 하지 않아도 된다.

 

채점 환경

- 파이썬으로 제출한 코드가 1초에 2,000만 번의 연산을 수행한다고 기억하면 된다.

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

 

구현 문제에 접근하는 방법

- 구현 유형의 문제는 사소한 입력 조건으로 인해 문제의 길이가 길다.

- 문제의 길이를 보고 지레 겁먹을 수 있지만 파이썬의 경우 기본 문법 사용에 익숙하다면 오히려 쉽다.