구현이란?
구현(Implemantation)이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.
결국에는 모든 유형의 문제가 소스코드로 구현하는 과정이기에 구현 문제라고 할 수 있겠다. 하지만 일반적으로 특정 문제를 구현 유형이라고 지칭할 때는 문제에서 요구하는 내용이 구현에 초점이 맞춰있거나 구현이 어려운 문제를 의미한다.
구현 유형의 예시로는 아래와 같다.
- 알고리즘은 간단하지만 코드가 지나치게 길어지는 문제
- 실수 연산을 다루고, 특정 소수점 자리까지 출력하는 문제
- 문자열을 특정한 기준에 따라서 끊어 처리해야하는 문제
- 적절한 라이브러리를 찾아서 사용해야 하는 문제
완전 탐색과 시뮬레이션
구현에는 완전 탐색 유형과 시뮬레이션 유형이 있다.
- 완전 탐색(Exhaustive Search)은 모든 경우의 수를 모두 다 계산하는 해결 방법이며
Brute Force라고도 한다. - 시뮬레이션(Simulation)은 일련의 명령에 따라서 개체를 차례대로 이동시키는 유형의 방법을 의미한다.
일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미이며, 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향벡터가 자주 활용된다.
<문제 유형1> 상하좌우
여행가 A는 N X N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 X 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N X N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시각좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다.
계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다. 각 문자의 의미는 다음과 같다.
- L : 왼쪽으로 한 칸 이동
- R : 오른쪽으로 한 칸 이동
- U : 위로 한 칸 이동
- D : 아래로 한 칸 이동
이때 여행가 A가 N X N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다.
계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성해라.
해결 아이디어
이러한 유형들의 문제는 요구사항대로 충실히 구현하는 문제의 유형이다. 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로도 분류되며 구현이 중요한 대표적인 문제 유형이다.
<문제 유형2> 시각
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성해라.
해결 아이디어
이러한 유형들의 문제는 가능한 모든 시각의 경우를 하나씩 모두 세서 풀 수 있는 문제이다. 하후는 86,400초 이므로, 00시 00분 00초부터 23시 59분 59초까지의 모든 경우는 86,400가지이다. 이러한 유형은 완전 탐색 문제 유형이다.
<문제 유형3> 왕실의 나이트
해결 아이디어
요구 사항대로 충실히 구현하면 되는 문제이다. 나이트의 8가지 경로를 하나씩 확인하면서 각 위치로의 이동이 가능한지 확인한다. 리스트를 이용하여 8가지 방향에 대한 방향벡터를 정의한다.
참고
유튜브 채널인 나동빈님의 '이코테2021'강의를 참고했다.
