(이코테 w/ Python) 구현: 시뮬레이션과 완전 탐색 이론

구현이란?

머릿속에 있는 알고리즘과 생각을 소스코드로 바꾸는 과정이다. 

아무리 알고리즘을 잘 세워도 실제 코드로 작성해서 프로그램으로 만들지 않으면 알고리즘은 동작하지 않는다. 

알고리즘 문제는 곧 소스코드로 구현해야 하므로 구현 문제이다. 

특정 문제를 구현 유형 문제라고 부를 때는 문제에서 요구하는 내용이 구현에 초점이 맞춰져 있거나 구현이 어려운 문제를 의미한다. 

 

알고리즘 대회에서 구현 유형의 문제란?

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

예를 들어,

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

 

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

출처: 유튜브 동빈나 채널

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

2D 게임을 개발할 때는 2차원 공간을 행렬과 같은 형태로 표현해서 내부적으로 처리한다.

다양한 시뮬레이션 문제에서 2차원 공간을 가정하는 상황이 많이 등장한다. 

예를 들어, '2차원의 한 좌표에 존재하는 캐릭터가 반복적으로 어떤 위치로 이동한다' 와 같은 문제 상황이 등장한다. 

 

행렬이란 2차원 데이터를 표와 같은 형태로 나타내는 수학 개념 중 하나이다.

프로그래밍 언어로는 2차원 배열이라고 불린다. (파이썬에서는 2차원 리스트)

 

행렬에서는 가장 왼쪽 위에 있는 원소가 첫 번째 원소이다.

완전 탐색, 시뮬레이션 문제를 접할 때 문제에서 정의하는 내용을 확인해보면 가장 왼쪽 상단의 위치를 (0, 0) 이라고 부른다. 

중,고딩때 배웠던 x, y축의 개념과 다를 수 있기 때문에 왼쪽 위가 일반적으로 행렬에서 첫 번째 원소다 라는 것을 명심해야 한다.

 

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

특정한 캐릭터나 사물이 특정 위치에 존재했다가 상, 하, 좌, 우로 움직일 수 있다 등으로 문제 상황이 정의되는 경우가 많다. 이러한 문제 해결을 위해 방향 벡터를 자주 사용한다.

 

# 동, 북, 서, 남
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)

출처: 유튜브 동빈나 채널

예를 들어, 특정 위치에서 위쪽으로 이동한다면 행 데이터가 1 만큼 감소하는 것을 확인할 수 있다. 

동 북 서 남은 차례대로 각각의 방향 벡터를 정의할 수 있다. (dx = [0, -1, 0, 1], dy = [1, 0, -1, 0])

여기에서 dx의 x는 세로축(행)을 의미하고 y는 가로축(열)을 의미한다.

그래서 동쪽은 행을 기준으로 가만히 있고(0) 열을 기준으로 1만큼 증가하는 것이기 때문에 오른쪽으로 이동하는 것이다. (2, 3)

북쪽의 경우 행을 기준으로 1만큼 빼기 때문에 위쪽으로(1, 2) 가는 것이다.

 

특정 위치가 x와 y 좌표로 정해져 있을 때 (# 현재위치 x, y = 2, 2)

다음 위치를 확인할 때 x 에 dx를 더해줌으로써 (nx = x + dx[i]) 행 방향을 어떤 방향으로 이동할 것인지 설정할 수 있고, 마찬가지로 열(y) 또한 dy[i] 를 이용해서 어떤 방향으로 이동할 것인지 설정할 수 있다. 

이렇게 상하좌우 위치를 살펴보면서 출력하고자 할 때 이러한 로직이 사용된다. 

현재 코드 순서는 동 북 서 남 순서대로 ‘다음 위치'가 출력된다.

 

dx와 dy는 (direction x, direction y) 방향성을 명시해주기 위해서 배열 혹은 리스트와 같은 형태로 사용된다.

 

 

문제 1: 상하좌우

출처: 유튜브 동빈나 채널

• 입력 조건: 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 <= N <= 100) 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. 
• 출력 조건: 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표(X, Y)를 공백을 기준으로 구분하여 출력한다.

문제 해결 아이디어

요구사항 대로 구현하는 문제이다. 

일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로도 분류되며 구현이 중요한 대표적인 문제 유형이다. 

(시뮬레이션 유형, 구현 유형, 완전 탐색 유형은 서로 유사한 점이 많아 다르게 구분될 수 있다)

 

답안 예시

#N 입력 받기

   현재 위치를 의미하는 x, y 변수를 사용한다.

 

# L, R, U, D에 따른 이동방향

    방향 벡터를 위해 dx, dy를 사용한다.

    이동 가능한 문자로 ['L', 'R', 'U', 'D']를 리스트에 담을 수 있도록 한다.

 

# 이동 계획을 하나씩 확인하기

    for plan in plans: 계획서(plans)에 있는 이동 계획을(plan) 하나씩 확인하면서

# 이동 후 좌표 구하기

    이동 후 좌표를 설정할 수 있도록 한다.

    즉, 현재 이동 계획이 move_types 중 어떤 것인지 확인해서 

    move_types에 맞는 다음 위치 값을 (nx, ny) 찾는다.

 

# 공간을 벗어나는 경우 무시

    nx, ny 값을 찾은 후 공간을 벗어나지 않는다면 #이동 수행을 수행한다. 

 

결과적으로 계획서에 있는 이동 계획을 하나씩 확인하면서 이동을 수행한 결과를 출력하면 된다.