[알고리즘] 구현 알고리즘 (Implementation Algorithm)

• 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념
• 프로그래밍 언어의 문법을 정확히 알고 있어야 함
• 라이브러리 사용 경험을 늘려야 함
• 파이썬의 경우 자료형의 표현 범위 제한에 대해 깊게 생각하지 않아도 되지만 실수형 변수는 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있음
• 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있음
• 일반적인 기업 코딩 테스트 환경에서는 파이썬으로 제출한 코드가 1초에 2,000만 번의 연산을 수행한다고 가정하면 크게 무리가 없음
• 알고리즘 문제를 풀 때는 시간제한과 데이터의 개수를 먼저 확인한 뒤에 이 문제를 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측할 수 있어야 함
• 코딩 테스트 환경이 만약 Pypy3을 지원한다면 이를 이용하자

---

 

코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다.

 

어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다.

 

정확한 풀이 방법을 떠올리고 생각해낸 문제 풀이 방법을 우리가 원하는 프로그래밍 언어로 정확히 구현해냈을 때 비로소 정답 처리를 받을 수 있다. 이를 위해 프로그래밍 언어의 문법을 정확히 알고 있어야 하며 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 한다.

 

대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기가 까다롭다.

 

어떻게 풀면 될지 대략 감은 오는데, 막상 코드로 옮기려니 무엇부터 작성해야 할지 모를 수 있기 때문에 구현 문제를 만나면 당황할 수 있다.

 

또한 프로그래밍 문법을 정확하게 숙지하지 못했거나, 라이브러리 사용 경험이 부족하면 구현 유형의 문제를 풀 때 불리하다.

메모리 제약사항

파이썬에서는 프로그래머가 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본으로 지원한다. 따라서 파이썬을 이용한다면 자료형의 표현 범위 제한에 대해 깊게 이해하고 있지 않아도 괜찮다.

 

다만, 파이썬에서의 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있다는 점을 기억하자.

 

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

 

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

 

이런 경우가 드물지만 리스트를 여러 개 선언하고, 그중에서 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다는 점을 기억하자.

채점 환경

파이썬은 C/C++에 비해 동작 속도가 느리다. 그래서 파이썬을 선택했을 때는 C/C++에 비해 2배의 수행 시간제한을 적용하기도 한다.

 

2020년, 파이썬 3.7로 코드를 작성할 때 기준으로, 채점 시스템의 컴퓨터 사양, 사용하는 알고리즘 등의 변수가 있지만 일반적인 기업 코딩 테스트 환경에서는 파이썬으로 제출한 코드가 1초에 2,000만 번의 연산을 수행한다고 가정하면 크게 무리가 없다.

 

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

접근 방법

보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편이다.

 

Pypy3는 파이썬3의 문법을 그대로 지원하며, 대부분 파이썬3보다 실행 속도가 더 빠르다.

 

대략 1초에 2,000만 번에서 1억 번 정도의 연산을 처리할 수 있다. 코딩 테스트 환경이 만약 Pypy3을 지원한다면 이를 이용하자.