구현 (Implementation)

정의 및  특징

코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩테스트 문제 유형을 포함하는 개념이다.

떠오른 풀이방법을 구현하기 위해서는 프로그래밍언어의 문법을 알아야며 요구사항에 맞게 실수없이 코드를 작성하여야한다.

구현은 흔히 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미한다.

문자열을 파싱하여 처리하는 문제, 코드가 길어지는 문제, 사소한 설정이 많은 문제 등이 구현문제의 예이다.

크게 완전탐색,시물레이션 문제가 코딩테스트에 자주 출제된다.

구현문제의 경우 문자열처리가 쉽고 기본적으로 메소드를 많이 지원해주는 파이썬이 유리할 수 있다.

API개발문제 또한 구현 유형과 상당히 관련이 있다.

 

문제 예시

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오

#H를 입력받기
h= int(input())

count =0
for i in range(h+1):
	for( j in range(60):
    	for k in ragne(60):
        	if '3' in str(i) +str(j) +str(k):
            	count+=1
                
print(count)

 

 

구현시 고려해야할  문제

1. 변수문제: c나c++에서는 long long 보다 큰 수를 기본적으로 지원하지 않는다. 하지만 파이썬은 자료형을 지정할 필요가 없으며 매우 큰수를 자체적으로 지원한다. 

 

2. 파이썬의 리스트 크기: 코딩테스트에서는 128~512메가바이트로 메모리를 제한한다. 가끔 아주 큰 크기의 데이터를 처리해야 할 수도 있는데 이때에는 메모리용량크기도 생각을 해야한다.

 

3.채점환경: 메모리제한뿐만 아니라 시간제한도 있다. 파이썬의 경우 C,C++에 비해 동작 속도가 느리다. 그래서 파이썬을 선택했을 때는 C/C++에 비해 2배의 시간을 주기도 한다. 파이썬의 경우 보통 1초에 2000만번의 연산을 수행한다. 이것을 고려하여 코드를 작성해야한다.

 

만약 시간제한이 1초이고 데이터의 개수가 100만개인 문제가 있다면 시간복잡도 O(NlogN)이내의 알고리즘을 이용하여 문제를 물어야한다. 계산을 해보면 백만 log(백만) 은 이천만이다. 이러한 방식으로 시간복잡도를 대략적으로 추측해볼 수 있다.

 

 

 

 

참고문헌

이것이 코딩테스트다(나동빈 지음)