구현 (implementation) 정복하기
유형 설명
코딩테스트에서 구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.
추상적인 설명과 같이, 모든 범위의 코딩 테스트 문제 유형을 포함한다.
대부분의 구현 문제는 풀이를 떠올리기는 쉽지만, 소스코드로 옮기는 과정이 어려운 문제를 의미한다.
(문제의 알고리즘의 설계를 했음에도, 구현은 먼저 풀 수 있는 문제가 없을 때 마지막으로 푸는 것이 좋다.)
구현 문제의 경우, 사소한 조건이 많을수록 어려운 문제로 평가된다.
(간단한 알고리즘에 비해 코드가 길어지는 경우, 특정 소수점 자리까지 출력해야되는 경우, 문자열을 문자 단위로 파싱해야되는 경우 등...)
대부분 구현 문제는 언어의 문법을 잘 이해하고, 다양한 활용 경험이 동반되어야 비로소 체감 난이도가 내려간다.
따라서, 많이 경험하고 이해하고 있어야 바로 떠올릴 수 있는 문제 유형이다.
본 설명에서 의미하는 구현의 경우, 아래의 유형도 포함한다.
완전 탐색 : 모든 경우의 수를 다 계산하는 방법
시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 방법
(두 유형이 구현의 핵심인 경우가 많다 !)
주의사항
파이썬의 경우, 자료형에 따른 공간 복잡도를 고려해야 한다.
입력의 길이가 많거나, 큰 경우 파이썬은 메모리 사용량에 대한 고려를 포함해야 한다.
(대부분의 구현 문제들은 입력이 긴 편이다.)
파이썬의 리스트 자료형의 경우, 메모리를 꽤나 차지한다.
int 형의 리스트 의 경우 아래와 같은 메모리 사용량을 갖는다.
| 데이터의 개수(리스트 길이) | 메모리 사용량 |
| 1,000 | 약 4KB |
| 1,000,000 | 약 4MB |
| 10,000,000 | 약 40MB |
파이썬은 다른 언어에 비해 구현상 복잡도는 적지만, 데이터 처리량이 많을 때는 항상 메모리 사용량을 고려해야한다.
(하지만, 웬만해선 메모리 사용량으로 문제되는 경우는 많지 않다. 그래도 숙지해두도록 하자)
또한 파이썬의 경우, 1초에 2000만번의 연상을 수행한다고 가정하고 해결하자.
(파이썬의 경우, 타 코드보다 실행 속도가 느리기 때문에 C++이나 타 언어 대비 2배 정도의 시간을 추가로 부여한다.)
예를 들어서 시간 제한이 1초이고, 입력 데이터가 최대 100만개일 때,
시간 복잡도 O(NlogN) 내의 알고리즘을 활용하여 문제를 해결해야 한다.
실제로 N = 1,000,000 일 때, NlogN은 20,000,000 정도이며, 이는 1초를 의미하기 때문이다.
따라서 문제를 해결할 때는, 시간 제한과 데이터의 개수를 먼저 확인하고
활용할 알고리즘을 결정하는 것을 습관화하는 것이 좋다.
문제 풀어보기
그렇다면, 구현의 문제는 어떤식으로 출제되는지 한 번 확인해보자
대부분의 구현 문제는 유형이 정해진 것이 없기 때문에, 직접 풀어보면서 감을 익혀 나가야 한다.
예제문제
상하좌우
| 문제 여행가 A는 N x N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적인 계획서가 놓여 있다. 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D중 하나의 문자가 반복적으로 적혀있다. 각각 좌, 우, 상, 하의 이동을 의미한다. 이 때, 여행가 A가 N x N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어 (1, 1)의 위치에서 L혹은 U를 만나면 무시된다. 계획서가 주어졌을 때 여행가 A가 최종적으로 도달하는 지점의 좌표를 출력하는 프로그램을 작성하시오 입력 첫 줄에 공간의 크기를 나타내는 N이 주어진다. (1 ~ 100 사이의 정수) 다음 줄에는 A가 이동할 계획서 내용이 주어진다. 출력 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력하라 |
| 입력 예시 |
| 5 R R R U D D |
| 출력 예시 |
| 3 4 |
본 문제는 간단하게 문자를 읽어서 순서대로 이동하면 되는 문제이다.
각 좌표를 토대로 이동 불가 지역으로의 이동을 무시해주면 해결할 수 있다.
1. 간단히 구현한 코드
n = int(input())
plan = input().split()
cur = [1, 1]
for move in plan:
if (move == 'R') & (cur[1] + 1 <= n):
cur[1] += 1
elif (move == 'L') & (cur[1] - 1 >= 1):
cur[1] -= 1
elif(move == 'U') & (cur[0] - 1 >= 1):
cur[0] -= 1
elif (move == 'D') & (cur[0] + 1 <= n):
cur[0] += 1
print(cur)
위 코드는 각 무빙의 경우를 고려하여 밖으로 벗어나지 않는 경우에만 좌표를 이동시키는 코드이다.
하지만, 보통 이러한 문제는 dx, dy의 개념으로 해결할 수 있다.
이동 방향에 따라 상, 하, 좌, 우로 구분된 값으로 정리하는 것이다.
코드를 더욱 직관적으로 알 수 있고, 실제로 후에 배우게 될 그래프나, 탐색 문제에서 적용하기 쉽다.
2. dx, dy를 활용한 코드
n = int(input())
x, y = 1, 1
plans = input().split()
# L, R, U, D에 따른 이동방향 정리 (dx dy)
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)dx, dy는 변화하는 이동 값이며, nx, ny는 이동 후의 좌표 값으로 이해하면 된다.
본 문제에서의 좌표 값은 좌 상단이 1, 1이고 우측 하단이 N, N이기 때문에, L R U D 각각의 dx, dy값이
[0, 0, -1, 1]과 [-1, 1, 0, 0]으로 정리된다.
( U, D의 이동값이 x값이며, L과 R의 이동값이 y값으로 적용된다.)
위와 같은 방식으로 문제를 해결할 수 있다.
이참에 dx, dy와 친해져 보는 것도 좋을 것 같다.