[알고리즘]구현 알고리즘

seongwonchung·2021년 1월 15일

구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이라고 할 수 있다.

따라서, 사실 특정한 '구현' 알고리즘이 있는 것은 아니고, 모든 알고리즘 문제가 구현의 문제라고 할 수 있다. 하지만, 『이것이 취업을 위한 코딩테스트다 with 파이썬』 에서는 완전탐색, 시뮬레이션 과 같은 문제를 구현으로 묶어서 다루고 있다. 이 유형은 풀이 자체를 떠올리는 것은 어렵지 않으나, 소스코드로 구현하는 과정이 어려운 유형이다.

또, 고려해야하는 사항은 시간/메모리 제한사항이다.

파이썬의 경우, 정수 리스트라고 가정할 때, 크기가 1000만 이상인 경우 약 40MB를 초과할 수 있으므로 용량 제한에 주의가 필요한 수준이다.

또, 2020년 파이썬 3.7기준으로 일반적인 코딩테스트 환경(대회와 같은 경우 제외) 에서 1초에 약 2000만 번 연산을 수행한다면 무리가 없다고 한다.

따라서 구현 문제를 풀 때는 위와 같은 사항을 고려하여 시간제한과 데이터의 개수에 주의하여야 한다.