구현 : 시뮬레이션과 완전 탐색 - 상하좌우 문제

구현 ( implementation )

: 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

 

 

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

 

 

구현 유형의 예시

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

 

 

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

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

( 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 )

 

# 동, 북, 서, 남
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는 NxN 크기의 정사각형 공간위에 서 있다. 이 공간은 1x1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1,1) 이며, 가장 오른쪽 아래 좌표는 (N,N)에 해당한다. 여행가 A는 상하좌우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1,1)이다. 여행가 A의 이동 계획서에는 L, R, U, D가 반복적으로 적혀있다. ( Left, Right, Up, Down ) 정사각형을 벗어나는  움직임은 무시된다.

# 입력 조건

• 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. ( 1<=N<=100 )
• 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. ( 1<=이동 횟수<=100 )

# 출력 조건

• 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X,Y)를 공백을 기준으로 구분하여 출력한다.

입력 예시	출력 예시
5 R R R U D D	3 4

 

 

문제 해결 아이디어

• 요구사항대로 충실히 구현

 

풀이 : O(N)의 시간 복잡도

n = int(input('공간의 크기 입력'))
x,y=1,1
plan = input().split()

dx=[0,0,-1,1]
dy=[-1,1,0,0]
move = ['L','R','U','D']

for i in plan:
    for j in range(len(move)):
        if i==move[j]:
            nx = x+dx[j]
            ny = y+dy[j]
    if nx < 1 or ny <1 or nx>n or ny>n:
        continue
    x,y=nx,ny
    
print(x,y)