구현 이론

구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

• 어떤 문제든 소스코드로 바꿔야 하므로 구현 문제라고 할 수 있다. 하지만 구현 문제라고 하면, 일반적으로 소스코드로 바꾸는 과정이 어렵거나 구현에 초점이 맞춰져있는 문제를 말한다.
• 흔히 알고리즘 대회에서 구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 말한다.
  1. 알고리즘은 간단한데 코드가 지나치게 길어지는 문제
  2. 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
  3. 문자열을 특정 기준에 따라 끊어서 처리해야 하는 문제
  4. 적절한 라이브러리를 찾아 사용해야 하는 문제
• 미리 알고 있는 함수들이 많다면 쉽게 문제를 풀 수 있을 것이다.
• 시뮬레이션 유형, 구현 유형, 완전탐색 유형은 서로 유사한 점이 많다.

문제 예시로는 다음 시각 문제가 있다.

시각 문제 : 00시 00분 00초부터 N시 59분 59초까지의 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 코드를 구현하는 문제이다.

하루는 86400초이므로 따로 알고리즘적 요소를 적용시키거나 최적화를 시키지 않아도 충분히 빠르게 계산할 수 있다. 이러한 유형을 완전 탐색(Brute Forcing)이라고 부른다.