구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 프로그래밍 언어 문법에 능숙하고 코드 작성 속도(타자)가 빠른 사람을 피지컬이 좋다고 하는데 구현 유형은 피지컬을 요구하는 문제이다.
사소한 조건 설정이 많은 문제일수록 코드로 구현하기 까다롭다. 교재에서는 완전탐색, 시뮬레이션 유형을 모두 구현 유형으로 다룬다.
-완전 탐색: 모든 경우의 수를 다 계산하는 방법
-시뮬레이션: 제시된 알고리즘을 한 단계씩 차례로 직접 수행해야하는 문제
예제 문제 1. 상하좌우
공간의 크기를 나타내는 N을 입력받고 둘째줄에 이동할 계획서 내용을 입력받는다. NxN 크기의 정사각형 공간에서 이동하며 시작 위치는 (1,1)이다.
입력받은 순서대로 L,R,U,D를 수행하며 설정한 정사각형을 벗어나면 이동할 수 없다.
풀이.
난이도 낮은 문제라고 써있지만 처음에 아예 어떻게 풀이해야할지 감이 안와서 다른 사람들의 풀이를 보고 도움을 받았다.
일단 그냥 생각하면 주어진 계획서대로 위,아래,왼쪽,오른쪽으로 이동을 하고 현위치에 1을 더해주는데, 각 이동 시마다 정사각형을 벗어나게 되는지 확인을 하고 최종적으로 더해진 위치를 출력하면 될 것 같다.
n = int(input()) #정사각형 크기를 입력받는다.
x,y = 1, 1 #최초 위치 x,y를 정사각형 첫 칸 1,1로 지정한다.
route = input().split() #이동할 루트를 입력받는데, 전에 했던 숫자 입력과 달리 문자열을 입력받을 때는 따로 list를 설정하지 않아도 알아서 list가 리턴된다.
#숫자입력을 할 때는 map함수가 객체를 리턴해서 그것을 따로 리스트로 감싸줘야한다.
for d in route : #그냥 간단하게 설정된 루트를 하나씩 for문으로 돌리면서 이동시킨다.
if d == 'R' : #만약 r이라면 오른쪽으로 이동하기 위해 x에 1을 더해준다.
if y+1 < n : #매번 이동한 위치가 설정된 정사각형을 벗어나는지 확인해줘야한다. 안벗어나면 이동시켜주기, 벗어나면 그냥 무시하기
y = y+1
elif d == 'L' :
if y-1 > 0 :
y = y-1
elif d == 'U' :
if x-1 > 0 :
x = x-1
else : #down일 경우
if x+1 < n :
x = x+1
print(x, y)
이렇게 하면 문제의 조건은 다 충족시킨다.
교재의 나온 해답도 공부해봤는데
n = int(input())
plans = input().split()
dx = [0,0,-1,1]
dy = [1,-1,0,0]
move_types = ['R','L','U','D']
px, py = 1,1
for i in plans :
for j in range(len(move_types)) :
if i == move_types[j] :
nx = px + dx[j]
ny = py + dy[j]
if nx < 1 or ny < 1 or nx > n or ny > n :
continue
else :
px, py = nx, ny
print(px, py)이런식으로 이동량을 계산하는 문제에서는 위와 같이 이동량을 미리 지정해두고 더하는 방식으로도 한다고한다. 뭔가 내가 한 것보다 훨씬 있어보이는 답안...
미리 nx, ny를 다 구해놓고 정사각형 안에 속한다면 원래 값에 대입시킨다는 의미이다.
흠 과연 내가 저렇게 짤 수 있을까
