[알고리즘/Algorithm]구현(Implementation)

🔷 구현(Implementation)

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

 

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

◼ 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단께씩 차례대로 직접 수행

---

"이것이 코딩테스트다 with 파이썬"에 나온 예제를 통하여 알아보자.

 

🔷 예제(Example)

 

◼ 문제

여행가 A 는 N x N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1) 이며, 가장 오른쪽 아래 좌표는 (N, N) 이다.  여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1) 이다. 계획서에는 하나의 줄에 띄어쓰기를 기준으로하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다.

 

- L : 왼쪽으로 한 칸 이동

- R : 오른쪽으로 한 칸 이동

- U : 위로 한 칸 이동

- D : 아래로 한 칸 이동

 

이 때 여행가 A 가 N x N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

 

◼ 해설

이 문제는 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션(Simulation) 유형으로 분류된다.

여기서의 문제 해결의 Key 포인트는 방향에 대하여 dx, dy 를 이용하여 배열을 선언해주는 것이다.

 

이것이 취업을 위한 코딩테스트다 with Python 4-1.py

💡 dx, dy 를 이용하여 좌표이동에 대한 접근을 수월하게 할 수 있다. 이 유형은 좌표이동에 자주 이용되니 필수적으로 알아두도록 하자.

 

◼ 참고

• 이것이 취업을 위한 코딩 테스트다 with 파이썬