TIL – 2024/10/25 Implementation(구현)

구현이란?

알고리즘을 만들 때, 머릿속에 있는 절차를 소스코드로 바꾸는 과정을 의미한다. 구현 유형의 문제는 보통 풀이를 떠올리는 것은 쉽지만, 그걸 실제 코드로 바꾸기엔 어려운 문제들을 많이 출제한다.

주로 많이 사용하는 구현 문제들은 완전 탐색 (모든 경우의 수를 다 탐색한다) 이거나 시뮬레이션 (문제에서 제시한 알고리즘을 한 단계씩 차례로 수행하게 만듦) 을 의미하는 경우가 많다.

구현 예시

N*N 격자 형식의 격자가 있다고 가정하자. L, R, U, D는 각각 왼쪽, 오른쪽, 위, 아래로 이동하라는 명령이 담긴 명령어들이다. 그럼 명령어가 주어졌고, 출발점은 (1,1)이라고 가정하면, 명령 수행 후 나의 위치는 어디인지 어떻게 알 수 있을까?

n = int(input())
steps = input().split()

x, y = 1, 1
for step in steps:
    if step == "R":
        if y + 1 <= n:
            y += 1
    elif step == "U":
        if x - 1 > 0:
            x -= 1
    elif step == "L":
        if y - 1 > 0:
            y -= 1
    else: # D
        if x + 1 <= n:
            x += 1

print(x, y)

이걸 조금 더 확정성 있게 구현한 예시는 다음과 같다

n = int(input())
x, y = 1, 1
plans  = input().split()

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)

이는 구현 중 시뮬레이션 유형의 문제가 어떻게 주어지는 지 보여준다.