구현:시뮬레이션과 완전 탐색

구현이란?

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

 

구현 유형의 예시

 - 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제

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

 - 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제

 - 적절한 라이브러리를 찾아서 사용해야 하는 문제

 

 

일반적으로 실제 코딩테스트에서 시뮬레이션 문제로 2차원 공간 행렬을 많이 사용함.

행렬(Matrix)

 

 

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

 

 

구현 문제 예시(시뮬레이션)

 

<문제> 상하좌우

L : 왼쪽으로 한 칸 이동

R : 오른쪽으로 한 칸 이동

U : 위로 한 칸 이동

D : 아래로 한 칸 이동

 

 

[문제해결 아이디어]

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

- 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션(Simulation) 유형으로도 분류되며 구현이 중요한 대표적인 문제 유형이다. (코딩테스트에서의 시뮬레이션, 구현, 완전 탐색 유형은 서로 유사한 점이 많다는 것 알고있기)

 

[파이썬 코드]

n = int(input())
x, y = 1, 1
plans = input().split()

#L,R,U,D 에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L','R','U','D']

for plan in plans:

    for i in range(len(move_types)):
        if plan == move_types[i]:
            nx = x + dx[i]
            ny = y + dy[i]
    # 공간을 벗어나는 경우 무시
    if nx<1 or ny <1 or nx>n or ny>n:
        continue
    x,y = nx, ny

print(x, y)

 

 

 

<문제> 시각 : 완전 탐색

제한 시간 : 2초

 

 

[문제해결 아이디어]

- 이 문제는 가능한 모든 시각의 경루를 하나씩 모두 세서 풀 수 있는 문제

- 하루는 86400초이므로, 0시 0분 0초 부터 23시 59분 59초까지의 모든 경우는 86,400가지 이다.

파이썬은 1초에 약 2000만 번 연산을 수행하기 때문에 1초씩 확인해도 24*60*60 = 86400 번 수행가능

- 따라서 단순히 시각을 1씩 증가시키면서 3이 하나라도 포함되어 있는지 확인하면 됨

- 이러한 유형은 완전 탐색(Brute Forcing:가능한 경우의 수를 모두 검사해보는 탐색 방) 문제 유형이라고 불린다.