[알고리즘] 시뮬레이션 - dx, dy 기법

목표

시뮬레이션 문제를 해결할 때 사용할 수 있는 dx, dy 기법이 무엇인지 알아본다.

과정

 시뮬레이션 문제란?

 시뮬레이션 문제는 주어진 문제의 조건을 구현하여 원하는 정답을 찾는 문제이다. 정답을 찾는 과정에서 DFS, BFS, 완전 탐색 등 다양한 기법을 사용할 수 있기 때문에 시뮬레이션 문제에 필요한 사전지식이 무엇인지 완전히 꼬집어 말할 수는 없다.

이 포스트에서는 그런 시뮬레이션 문제에서 사용할 수 있는 코딩 기법인 dx, dy 기법을 소개해보고자 한다.

 

 dx, dy란?

dx, dy는 미적분학에서 나오는 용어로 각각 x, y의 변화량을 의미한다. 알고리즘 문제를 푸는데 미적분학이 나왔다고 해서 겁먹을 필요 없다. dx, dy는 직관적인 이해를 위해 도입된 개념이기 때문이다. 예를 들어 다음과 같은 문제를 푼다고 해보자.

영식이는 지도 상에서 (0, 0)에 위치하고 있다.
총 N번 동안 영식이에게 명령을 내릴 것인데 명령은 방향을 의미하는 D와 거리를 의미하는 K로 이뤄져있다.
방향을 의미하는 D는 'U', 'D', 'L', 'R' 중 하나이며 각각 상, 하, 좌, 우를 의미한다. K는 영식이가 이동할 거리이다.
D와 K는 공백으로 구분되어 있으며 총 N번의 명령을 내린 뒤 영식이의 좌표를 출력하라.

위 문제를 풀기 위해서 이렇게 접근할 것이다.

for _ in range(n):
	# 입력을 받습니다.
    d, k = map(int, input().split())

    if d == 'U':
        y += k
    elif d == 'D':
        y -= k
    elif d == 'L':
        x -= k
    else:
        x += k

 

맞는 접근 방법이지만, 코드의 가독성이 좋지 않다고 느끼는 사람도 분명 존재할 것이다. 이것을 배열을 사용해 다음과 같이 변환할 수 있다.

 

# 상, 하, 좌, 우로 움직였을 때 x와 y의 변화량을 담습니다.
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

for _ in range(n):
	d, k = map(int, input().split())
	x, y = x + k * dx[d], y + k * dy[d]

이전 코드보다 훨씬 짧은 라인 내에 원하는 답을 얻을 수 있다.

 

 어떤 문제에서 이 기법을 사용할 수 있을까?

특별한 알고리즘이 아닌 코딩 기법이기 때문에 어떤 특별한 문제에서 사용할 수 있다! 라고 말하기는 애매모호 한 것 같다. 그렇지만 다음과 같은 백준 문제를 해결할 때 사용할 수 있을 것이다. 이 기법이 사용되는 문제는 대부분 격자 위에서 무언가를 진행하거나, 행렬에서 이동하는 문제이다.

 

https://www.acmicpc.net/problem/5212

5212번: 지구 온난화

https://www.acmicpc.net/problem/8911

8911번: 거북이