[Algorithm] 구현 (Implementation)

구현(Implementation)은 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램 코드로 작성하는 것을 말합니다.

어떤 문제를 풀더라도 프로그램 코드 작성은 필수이기 때문에 구현 문제 유형은 모든 범위의 문제 유형을 포함하고 있습니다.

따라서, 대부분 구현 문제에 대한 별도의 유형을 정하기 어렵습니다. 보통 구현 문제는 풀이를 떠올리는 것은 쉽지만 코드로 옮기기 어려운 것들입니다. 결국 구현 문제는 자신의 프로그래밍 피지컬로 승부를 봐야합니다.

 

구현 문제를 잘 풀어내기 위해서는 자신의 주언어 라이브러리 사용법을 잘 숙지해야 합니다. 예를 들어 리스트에서 순열을 구해야 하는 문제를 만난다면 itertools 라이브러리로 쉽게 구현할 수 있습니다. 하지만 이것을 몰랐다면 많은 시간이 필요할 것입니다.

 

하지만 자주 출제되는 구현 문제는 다음과 같습니다.

• 어려운 알고리즘은 아니지만 조건이 많은 문제
• 실수 연산과 특정 소수점 자리까지 출력하는 문제
• 문자열을 조건에 따라 분리하거나 검색하는 문제
• 문제를 해결하기 위한 적절한 라이브러리를 사용하는 문제
• 2차원 좌표를 이용하는 문제(행렬)

 

개인적인 경험으로는 조건이 많은 문제, 문자열을 이용하는 문제, 2차원 좌표를 이용하는 문제를 자주 봤습니다.

 

그러면 구현 문제의 예제 '상하좌우' 문제를 보겠습니다.

 

<문제>

 

<해설>

요구사항대로 구현하면 연산 횟수는 이동 횟수에 비례하게 됩니다. 이런 문제는 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션(Simulation) 유형으로 분류될 수 있습니다.

 

구현은 L, R, U, D에 따라 2차원 좌표기반의 현재 좌표에서 다음 좌표로 이동하면 됩니다.

좌표를 이동시킬 때, N * N으로 구성된 좌표를 벗어나는 경우만 체크해 주면 됩니다.

 

<구현>

def solution(n, plans):
    x, y = 1, 1

    # 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

    return x, y


n = 5
plans = ['R', 'R', 'R', 'U', 'D', 'D']

print(solution(n, plans))

참고: https://www.youtube.com/watch?v=2zjoKjt97vQ&list=RDCMUChflhu32f5EUHlY7_SetNWw&index=3