구현 :: 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기

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

생각해낸 문제 풀이 방법을 우리가 원하는 프로그래밍 언어로 정확히 구현해냈을 때 비로소 정답 처리를 받을 수 있다.

이를 위해 프로그래밍 언어의 문법을 정확히 알고 있어야 하며 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 한다.

 

* 어떤 문제가 구현하기 어려운 문제일까? 

-> 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제

-> 특정 소수점 자리까지 출력해야하는 문제

-> 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야하는(파싱을 해야하는) 문제 등

 

 

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

 

예시로, (프로그래밍 언어는 파이썬) N개의 원소가 들어 있는 리스트에서 R개의 원소를 뽑아 한 줄로 세우는 모든 경우(순열)를 구해야 하는 문제를 만나면 어떻게 해야하나? 

 

1) 무작정 기능을 전부 작성

2) 파이썬의 itertools와 같은 표준 라이브러리로 쉽게 짜는 방법

 

 

---

 

* 완전 탐색, 시뮬레이션 유형을 '구현'으로 묶어서 다뤄본다.

 

 완전 탐색

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

 

 시뮬레이션

문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형

 

 

 

* 파이썬에서 리스트 크기 고려해야할 사항

-> 코딩 테스트의 메모리 제한, 대체로 128~512MB로 메모리를 제한

 

시간 제한이 1초이고, 데이터의 개수가 100만 개 인 문제가 있다면 일반적으로 시간 복잡도는 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야 한다. 

 

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

 

 

 

* 구현 문제에 접근 하는 방법

자동 채점 방식을 이용하는 코딩 테스트 환경에서는 Pypy3를 지원하는 곳이 늘고 있다.

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

코딩 테스트에서 Pypy3를 선택한다면 파이썬3와 동일한 코드를 제출해서 실행 시간을 줄일 수 있다.

 

삼성전자 공채에서는 코딩테스트 채점에 Pypy3를 이용하는데, 지원자가 파이썬3로 제출하면 Pypy3를 이용해 채점한다.

Pypy3 실행 속도는 C/C++와 견줄 만큼 빠르다.

 

 

 

 

---

출처: [이것이 취업을 위한 코딩 테스트다 with 파이썬] 서적