#2 Implementation

구현

코딩 테스트에서 구현(Implementation)이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정' 이다. 즉 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제이다. 여기서 구현하기 여려운 문제들의 예시를 들어보자면

• 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
• 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
• 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
• 적절한 라이브러리를 찾아서 사용해야 하는 문제

대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기가 까다롭다.

 

여기서 다룰 구현 유형은 두 가지이다.

• 모든 경우의 수를 주저 없이 다 계사하는 해결 방법을 의미하는 완전 탐색
• 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 시뮬레이션

구현 시 고려해야 할 메모리 제약 사항

C/C++에서 변수의 표현 범위

전통적으로 프로그래밍 언어에서 정수형(Integer)를 표현할 때는 int 자료형을 사용하고, 크기는 4바이트다. 기본 int 자료형의 표현 범위는 -2,147,483,648 ~ 2,147,483,647이고, 더 큰 수를 처리하기 위한 long long 자료형은 9,223,372,036,854,775,807까지 처리할 수 있다. 이보다 더 큰 수를 처리하기 위해서는 BigInteger 클래스를 구현하거나 이용해야 한다. Java에서는 표준 라이브러리로 지원하지만, C++경우 지원하지 않는다. 

 

반면 파이썬에서는 프로그래머가 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본으로 지원한다. 따라서 파이썬을 선택한다면 정수형 변수의 연산 때문에 머리 아프게 고민해야 할 일은 거의 없을 것이다. 다만, 파이썬에서의 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라 연산 결과가 원하는 값이 나오지 않을 수 있다는 점을 기억해야 한다.

 

 

 

파이썬에서 리스트 크기

파이썬에서 여러 개의 변수를 사용할 때 리스트를 이용한다. 리스트를 이용할 때 고려사항이 있는데, 바로 코딩테스트의 메모리 제한이다. 대체로 코딩테스트에서는 128 ~ 512MB로 메모리를 제한하는데 알고리즘 문제 중 때로는 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제된다. 이럴 때는 메모리를 염두에 두고 코딩해야 한다.

 

하지만 이런 문제는 드물기 때문에 일반적인 코딩 테스트에서는 메모리 사용량 제한보다 더 적은 크기의 메모리르 사용해야 한다는 점 정도만 기억하면 된다.

 

 

채점 환경

보통 코딩테스트 환경에서는 다음과 같은 채점 시스템의 시간 제한 및 제한 정보가 적혀있다.

• 시간 제한: 1초
• 메모리 제한: 128MB

파이썬은 C/C++에 비해 동작 속도가 느리다. 2020년을 기준으로 파이썬 3.7로 코드를 작성할 때, 자신의 코드가 1초에 2000만 번의 연산을 수행한다고 가정하고 문제를 풀면 실행 시간 제한에 안정적이다. 일반적인 기업 코딩 테스트 환경에서는 파이썬으로 제출한 코드가 1초에 2000만 번의 연산을 수행한다고 가정하면 크게 무리가 없다는 점만 기억하면 된다.

 

시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제가 있다면 일반적으로 시간 복잡도 O(NlogN)이내의 알고리즘을 이용하여 문제를 풀어야 한다. 실제 N이 100만일 때 NlogN은 약 2000만이기 때문이다. 따라서 알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 확인하고 문제를 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 지 예측할 수 있어야 한다.

 

 

구현 문제 접근 방법

보통 구현 문제는 사소한 입력 조건 등 문제에서 명시해주며 문제의 길이가 꽤 긴 편이다. 문제의 길이를 보고 지레 겁먹기 보다, 고차원적인 사고력을 요구하는 문제는 나오지 않는 편이라 문법에 익숙하다면 오히려 쉽게 풀 수 있다.

 

구현 유형의 문제는 C/C++나 자바로 문제를 풀 때 더 어렵게 다가온다. 문자열을 처리하거나 큰 정수를 처리하는 문제가 출제되는 경우가 많은데, C/C++나 자바에서는 문자열 처리가 파이썬에 비하여 까다롭고, 큰 정수를  처리하는 라이브러리를 별도로 사용해야 한다. 반면 파이썬은 기본 문법만 아라도 상대적으로 구현 문제를 쉽게 해결할 수 있다.

 

API 개발 문제 또한 구현 유형과 상당히 맞닿아 있다. 예를 들어 카카오 공채 때 API 개발 문제가 출제된 적이 있는데, 이 때 카카오 문제 풀이 서버와 통신하는 프로그램 모듈을 작성해야 했다. 이는 알고리즘 문제와 별개로 웹 서버나 데이터 분석에 대한 기초 지식도 필요하다. 이런 기능 구현에 있어서도 파이썬이 C/C++ 자바에 비해 유리하다. 

 

 

 

<예제>

문제 - 상하좌우

 

여행가 A는 N × N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 × 1 크기의 정사각형으로 나누어져 있다.
가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다.

여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가
이동할 계획이 적힌 계획서가 놓여 있다

계획서에는 하나의 줄에 띄어쓰기를 기준으로 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다.
각 문자의 의미는 다음과 같다

 

L: 왼쪽으로 한 칸 이동

R: 오른쪽으로 한 칸 이동

U: 위로 한 칸 이동

D: 아래로 한 칸 이동

 

이때 여행가 A가 N × N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다
예를 들어 (1, 1)의 위치에서 L 혹은 U를 만나면 무시된다
다음은 N = 5인 지도와 계획이다

 

이 경우 6개의 명령에 따라서 여행가가 움직이게 되는 위치는 순서대로 (1, 2), (1, 3), (1, 4), (1, 4), (2, 4), (3, 4)이므로, 최종적으로 여향가 A가 도착하게 되는 곳의 좌표는 (3, 4)이다. 다시 말해 3행 4열의 위치에 해당하므로 (3, 4)라고 적는다. 계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오

 

<입력 조건>

• 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 <= N <= 100)
• 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1 <= 이동 횟수 <= 100)

<출력 조건>

• 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력한다.

 

<입력 예시>

5
R R R U D D

<출력 예시>

3 4

 

 

<코드>

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)