구현이란
코딩 테스트에서 구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 것이다.
흔히 '풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제'이다.
구현 문제는 사실상 모든 범위의 코딩 테스트 문제 유형이라,
알고리즘 교재에서는 잘 다루지 않지만 이 책에서는 다루고 있다.
구현하기 어려운 문제는 다음과 같다.
- 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
- 특정 소수점 자리까지 출력해야 하는 문제
- 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제
이렇듯 사소한 조건 설정이 많은 문제이다.
구현의 예시
완전 탐색과 시물레이션을 이 책에서 구현 알고리즘으로 다루고 있다.
완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법이며,
시물레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제 유형이다.
## 구현 문제에 접근하는 방법 구현 문제는 문제의 길이가 긴 편이지만, 고차원적인 사고력을 요구하지 않기 때문에 문법에 익숙하면 쉽게 풀 수 있다. c나 c++보다 python을 사용하면 쉽게 풀 수 있다.
구현의 예시 - 상하좌우 문제
여행자 A는 N x N 크기의 정사각형 공간 위에 서 있는데, 이 공간은 1 x 1크기아 정사각형으로 나눠졌다.
가장 왼쪽 위 좌표는 (1, 1), 가장 오른쪽 아래 좌표는 (N, N).
여행자 A는 상, 하, 좌, 우 방향으로 이동 가능하며 시작 좌표는 항상 (1, 1)이다.
출처:
나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2020), 110p.
L, R, U , D중 하나의 문자가 반복적으로 적혀 있으며 다음의 의미와 같다.
- L : 왼쪽으로 한 칸 이동
- R : 오른쪽으로 한 칸 이동
- U : 위로 한 칸 이동
- D : 아래로 한 칸 이동
(여행자 A가 N X N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다.)
다음은 N 5인 지도와 계획서이다.
출처:
나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2020), 111.
이 경우, 여행가가 움직이게 되는 위치는
(1, 2), (1, 3), (1, 4), (1,4), (2, 4), (3, 4)이므로,
최종적으로 여행가 A가 도착하게 되는 곳의 좌표는 (3, 4)이다.
입력 예시 :
5
R R R U D D
출력 예시 :
3 4
# N을 입력받기
n = int(input())
x, y = 1, 1
plans = input().split()
# L, R, U, D에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']
# 이동 계획을 하나씩 확인
for plan in plans:
# 이동 후 좌표 구하기
for i in range(len(move_types)):
if plan == move_types[i]:
nx = x + dx[i]
ny = y + dy[i]
# 공간을 벗어나는 경우 무시
if nx < 1 or ny < 1 or nx > n or ny >n:
continue
# 이동 수행
x, y = nx, ny
print(x, y)이 경우 얀산 횟수는 이동 횟수에 비례하게 되며,
이동 횟수가 N 번인 경우 시간 복잡도는 O(N)이다.
해당 포스팅의 개념, 코드, 이미지는 밑 책을 바탕으로 작성되었습니다.
