[구현] 시뮬레이션, 완전탐색 -이코테, 이것이 코딩 테스트다

구현

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

 

코딩테스트에 빗대어 생각해보기

- 풀이를 떠올리는 건 쉽지만 코드로 옮기기 어려운 문제

- 실수 연산을 다루고 특정 소수점 자리까지 출력해야 하는 문제

- 문자열을 특정 기준에 따라 끊어서 처리해야하는 문제 -> 파이썬은 문자열 문제 편함 :)

- 적절한 라이브러리를 찾아 사용해야하는 문제 -> 모든 순열 및 조합을 찾아야하는 문제를 파이썬에선 편하게 구현 가능

 

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

행렬 좌표 위치

 

시뮬레이션 및 완전 탐색 문제에서는 아래와 같이 2차원 공간에서의 방향 벡터가 자주 활용됨

동북서남으로 이동하는 경우의 좌표

연습문제 풀어보기

- 범위 밖을 벗어날 수 없음 (이 때는 무시)

- 시간제한 2초, 메모리제한 128MB

구현 연습 문제 [상하좌우]

 

문제 조건

- 요구사항대로 충실히 구현하면 되는 문제

- 명령에 따라 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로 분류 가능

- n이 최대 100이니까 최대 10,000의 공간 크기

 

* 처음 풀었던 방법 

- 좀 더 깔끔하게 풀 수 있었던 방법을 두고 지저분하게 푼 것 같다. 

n = int(input()) #공간의 크기 nxn
plan = input().split()

# 동서남북 정의 (R,L,D,U)
dx = [0,0,1,-1]
dy = [1,-1,0,0]

x,y = 1,1

for i in plan:
    if i == 'R' and y < n:
        x = x+dx[0]
        y = y+dy[0]
    elif i == 'L' and y > 1:
        x = x+dx[1]
        y = y+dy[1]
    elif i == 'U' and x > 1:
        x = x+dx[3]
        y = y+dy[3]
    elif i == 'D' and x < n:
        x = x+dx[2]
        y = y+dy[2] 

print(x,y)

* 그 후, 수정한 코드

n = int(input()) #공간의 크기 nxn
plans = input().split()

print(plans)

# 동서남북 정의 (R,L,D,U)
dx = [0,0,1,-1]
dy = [1,-1,0,0]

plan_type = ['R','L','D','U']

x,y = 1,1

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

    x , y = nx, ny

print(x,y)