[알고리즘] 구현(Implementation) 알고리즘과 예제

미남잉·2021년 12월 3일

📌 강의 바로가기

개념과 코드, 이미지는 해당 책과 강의를 참고하였습니다.

구현(Implementation)

구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정입니다.

[problem] - [thinking] - [solution]

흔히 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭합니다.

예시는 다음과 같습니다.

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

여기서는 완전 탐색과 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미합니다.

둘 다 구현이 핵심이 되는 경우가 많기 때문에 이 두 유형을 모두 묶어서 구현 장에서 다루고 있습니다.

행렬(Matrix)

일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용된다.

행렬은 2차원 데이터를 일종의 표와 같이 나타날 수 있게 해주는 개념입니다. 파이썬에서는 2차원 리스트와 동일합니다.

for i in range(5):
    for j in range(5):
        print('(', i, ',', j, ')', end=' ')
        print()

실행값
( 0 , 0 ) 
( 0 , 1 ) 
( 0 , 2 ) 
( 0 , 3 ) 
( 0 , 4 )
( 1 , 0 )
( 1 , 1 )
( 1 , 2 )
( 1 , 3 )
( 1 , 4 )
( 2 , 0 )
( 2 , 1 )
( 2 , 2 )
( 2 , 3 )
( 2 , 4 )
( 3 , 0 )
( 3 , 1 )
( 3 , 2 )
( 3 , 3 )
( 3 , 4 )
( 4 , 0 )
( 4 , 1 )
( 4 , 2 )
( 4 , 3 )
( 4 , 4 )

시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용됩니다.

여기서 x는 세로축, y는 가로축입니다. dx는 행으로의 이동, dy는 열로 이동합니다.

dx, dy가 위치를 이동시켜줍니다.

# 동, 북, 서, 남
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

# 현재 위치
x, y = 2, 2

for i in range(4):
    # 다음 위치
    nx = x + dx[i]
    ny = y + dy[i]
    print(nx, ny)

이제 이 방향 벡터를 이용한 예제를 풀어보도록 하겠습니다.

<문제> 상하좌우

문제 설명

여행가 A는 $N$ X $N$ 크기의 정사각형 공간에 서 있고, 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있습니다.

가장 왼쪽 위 좌표는 (1, 1)이고 가장 오른쪽 아래 좌표는 (N, N)에 해당합니다.

여행가 A는 상하좌우로 이동할 수 있으며, 시작 좌표는 항상 (1,1)입니다.

우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있스비다.

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

L: 왼쪽으로 한 칸 이동
R: 오른쪽으로 한 칸 이동
U: 위로 한 칸 이동
D: 아래로 한 칸 이동

만약 공간을 벗어나는 움직임이 있다면 그 움직임은 무시하고 다음으로 넘어갑니다.

입력 조건

첫째 줄에 공간의 크기를 나타내는 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)