구현

알고리즘 테스트에서 구현 문제란

풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 

즉, 프로그래밍 언어/문법/라이브러리에 대한 이해도가 높아야 함 

* Java로 알고리즘을 공부하고 있다면 이 사이트를 추천한다. 

https://codingbat.com/java

CodingBat Java

 

 

예) 

• 알고리즘은 간단한데 코드가 지나치게 긴 문제
• 특정 소수점 자리까지 출력해야하는 문제
• 문자열이 입력으로 주어졌을 때 한문자 단위로 끊기(Parsing) 

 

 

분류

완전 탐색 : 모든 경우의 수를 전부 다 계산해야하는 방법

시뮬레이션 :  문제에서 제시한 알고리즘을 한 단계씩 차례로 직접 수행해야하는 문제 

 

 

제약사항

언어적 제약 

구현 문제는 언어적 제약을 간과하여 100% 정답에 달성되지 못하는 경우가 있다

자료형	범위
int(4byte)	-2,147,483,648 ~ 2,147,438,647 (20억)
long long (8byte)	- 9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,808
BigInteger(class)	제한없음 (java only)

int의 범위(20억 이상)내에 걸려서 long long을 사용해야하는 경우를 잘 확인하자 (그 이상은 거의 출제되지 않음) 

 

속도적 제약 

파이썬은 C++에 비해 동작 속도가 느리다.

시간 제한과과 데이터의 갯수를 먼저 확인한 뒤에 문제를 어느정도 시간 복잡도의 알고리즘으로 작성할 수 있을지 예측

( N  = 1,000,000일 때 NlogN = 20,000,000이다 )

 

 

 

팁

• 문자열 처리
• 큰 수를 처리하는 문제

에 대해 스스로의 라이브러리와 방식이 정확하게 정리되어 있어야 한다