[알고리즘] 구현 (Implementation)

구현 알고리즘(Implementation Algorithm)이란, 어떤 특별한 공식이나 방법이 아닌 코딩테스트 문제 해결을 위한 개념으로, 단순히 머릿속에 있는 알고리즘을 소스코드로 풀어내는 과정을 말한다. (Problem-Thinking-Solution)

 

어떤 문제를 풀든 소스코드를 작성하는 과정은 필수이기 때문에 대부분의 알고리즘 문제가 '구현 문제'이다. 그 중 구현이 어렵거나 초점에 맞춰져있는 문제들이 있다. 즉, 풀이를 떠올리는 것이 쉽지만 소스코드로 옮기기 어려운 문제가 구현문제 라고 생각하면 된다.

 

예시

• 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
• 문자열을 특정한 기준에 따라서 끊어 처리해야하는 문제
• 적절한 라이브러리를 찾아서 사용해야 하는 문제
• 알고리즘은 간단한데, 코드가 길어지는 문제

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

 

구현에 속하는 알고리즘

• 완전 탐색: 모든 경우의 수를 다 계산하는 해결 방식
• 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 수행해야하는 문제 유형

---

코딩 테스트에서는 어떤 환경에서 문제를 풀어야 하는지 알고, 그 환경에 맞게 프로그래밍 언어를 사용하여 구현하는 일이 포인트 이다.

 

구현 시 고려해야 할 제약사항 1, 메모리

전통적인 프로그래밍 언어는 정수형을 표현할 때 int 자료형을 사용하고 크기는 4 btye 이다.

정수형 종류	자료형 크기	자료형의 범위
int	4 byte	-2,147,483,648 ~ 2,147,438,647
long	8 byte	-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

 

구현 시 고려해야 할 제약사항 2, 채점 환경

문제에서 요구하는 메모리 제한과 실행 시간 제한은 코딩 테스트를 출제하는 기관마다, 문제마다 조금씩 다르다.

보통 코딩테스트 환경에서는 채점 시스템의 시간 제한 및 메모리 제한 정보가 적혀있다.

 

ex)

시간 제한: 1초
메모리 제한: 128MB

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

실제로 N = 1,000,000 일 때, Nlog2(N)은 약 20,000,000이기 때문이다.

 

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

 

---

결론적으로 구현의 핵심은 숙련이다. 위에서 언급한 대부분의 내용은 어떤 알고리즘 문제를 만나도 나타날 수 있기 때문에, 많은 문제를 해결해보는 것이 답인 것 같다.

관련 문제

[C#][프로그래머스] 점프와 순간 이동

 

[C#][프로그래머스] 예산

 

---

참고 사이트

https://hardworkingini.tistory.com/150

https://www.itsmo.dev/implementation-algorithm/