구현이란

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.

코딩 테스트에서 어떤 문제를 출던 이러한 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다.

그렇다면 구현을 따로 배워야할 필요가 있나하는 생각이 들 수 있다.

우리는 알고리즘을 해결할 때 해결방안을 떠올린다. 문제를 풀 수 있는 정확한 해결법을 떠올렸다고 가정하자. 그럼 풀이는 끝난걸까 ?
아니다. 우리는 이 풀이를 프로그래밍 언어로 정확히 풀어냈을 때 풀이를 끝냈다고 할 수 있다. 따라서 언어의 문법을 정확히 알고 있어야 하고 요구사항에 어긋나지 않도록 해야한다.

하지만 그렇다고 해도 구현은 너무 광범위하고, 제대로 특정지을 수 없지 않을까.

흔히 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다.

그렇다면 소스코드로 옮기기 어려운 문제란 무엇인지 생각해봐야한다.

대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기 까다롭다. 초보자 입장에서는 문법에 익숙하지 않기 때문이다.

구현의 유형을 둘로 나눠보자.

• 완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
• 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형

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

흔히 코딩 테스트에서 많이 사용하는 C와 C++에 대해 생각해보자. C나 C++은 정수형을 사용할 때 자료형을 지정해줘야한다. 기본으로 int를 많이 지정하는데 int로는 표현하지 못하는 범위가 있을 수 있다. 이때는 더 큰 long long이나, BigInteger등을 사용해야한다.

하지만 이에 비해 파이썬은 프로그래머가 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본으로 지원한다. 따라서 이에 대해 고민할 사항은 없다.

다만 실수형 변수는 파이썬도 유효숫자에 따라 연산 결과가 원하는 값이 나오지 않을 수 있다.

파이썬에서 리스트 크기

파이썬에서 리스트를 이용할 때에 고려해야할 사항은 코딩 테스트의 메모리 제한이다.

파이썬은 정수데이터를 사용할 때 별도의 자료형을 명시해줄 필요는 없으나 시스템 내부적으로는 아래의 표에서 보여주는 것과 유사한 크기 만큼 메모리를 차지한다.

리스트의 길이	메모리 사용량
1000	약 4KB
1000000	약 4MB
10000000	약 40 MB

파이썬은 다른 언어에 비해 구현상의 복잡함이 적은 편이지만 데이터 처리량이 많을 때는 꼭 메모리 제한을 고려해야한다.

하지만 메모리 제한으로 문제를 풀 수 없게 되는 문제는 드물다. 메모리 제한 때문이 아니라 수천만개 이상의 데이터를 입력해야하면 입출력에 너무 많은 시간이 소요되며 채점환경에서도 다양한 문제가 발생할 수 있기 때문이다.

따라서 일반적인 코딩 테스트 수준에서는 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야한다는 점 정도만 기억하면 된다.

채점 환경

일반적인 기업 코딩 테스트 환경에서는 파이썬으로 제출한 코드가 1초에 2000만번의 연산을 수행한다고 가정하면 크게 무리가 없다.

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

구현 문제에 접근하는 방법

보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주고, 문제의 길이가 꽤 긴 편이다. 하지만 고차원적인 사고력을 요구하는 문제는 나오지 않는 편이라 문법에 익숙하다면 오히려 쉽게 풀 수 있다.

Pypy3는 파이썬 3의 문법을 그대로 지원하는데, 대부분 파이썬3보다 실행속도가 더 빠르다. 반복문이 많을 수록 속도 차이가 많이 나는데 때론 C/C++과 견줄만큼 빠르다. 요즘 자동 채점 방식을 이용하는 코딩 테스트 환경에서는 점점 Pypy3를 지원하는 곳이 늘고 있으므로 Pypy3를 지원하는지 확인하고 이용하는 것도 좋은 방법이다.