구현 Implementation

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

그런 의미에서 알고리즘 교재에서는 대부분 구현을 별도의 유형으로 다루지 않는다. 하지만 취업을 목표로 하는 코딩 테스트에서는 구현이 중심이 되는 문제가 자주 출제되기에 다른 알고리즘을 배우기 전에 먼저 다루고자 한다. 

 

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

 

완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 방법

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

이 둘은 구현이 핵심이 되는 경우가 많다.

 

1. 상하좌우 문제

여행가가 N x N 크기의 정사각형 공간 위에 서 있다. 가장 왼쪽 위 좌표가 (1, 1)이며 가장 오른쪽 아래가 (N, N)이다. 상화좌우로 이동할 수 있는 4종류의 명령이 주어질 때, 여행가가 최종적으로 위치하게 되는 좌표를 출력하는 프로그램을 작성하시오. (정사각형 공간을 벗어나는 움직임은 무시된다.)

 

이러한 유형은 일련의 명령을 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로 분류되며 구현이 중요한 대표적인 문제 유형이다. 

 

2. 시각

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

 

이러한 유형은 완전 탐색 유형으로 분류되기도 한다. 완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법이다. 일반적으로 완전 탐색 유형은 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 큰 경우에 정상적으로 작동하지 않을 수 있다. 때문에 주로 데이터가 100만개 이하일 때 완전 탐색을 이용한다.

 

 

3. 왕실의 나이트

8x8 좌표 평면의 정원의 한 칸에 나이트가 서 있다. 나이트는 다음과 같이 2가지 방법으로만 움직일 수 있다. 

1. 수평으로 2칸 이동한 뒤 수직으로 한 칸 이동

2. 수직으로 2칸 이동한 뒤 수평으로 한 칸 이동

나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오

입력 예시: a1

 

ord() :  특정 문자를 아슽키코드로 변환

 

4. 게임 개발

* map() 함수는 map 클래스를 리턴하므로 list()로 캐스팅해줘야 한다.

*global = 전역변수 선언

*[[0] * m for _ in range(n)] = 리스트 내포 또는 리스트 컴프리헨션

맵:  N행 x M열

1. 현태 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 갈 곳을 정한다. 

2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸 전진. 왼쪽 방향에 가보지 않은 칸이 없다면 회전만 하고 1단계로 되돌아감.

3. 만약 네 방향 모두 이미 가본 칸이거나 바다인 경우 방향을 유지한 채로 뒤로 1칸 이동. 이때 뒤쪽 방향이 바다인 경우 움직임을 멈춘다. 

이때 캐릭터가 방문한 칸의 수를 출력하시오