알고리즘 이론 - 구현

구현(Implementation)

• 구현이란, 머릿속의 알고리즘을 소스코드로 바꾸는 과정.
• 일반적으로, 코딩테스트에서 구현 문제는, 풀이는 쉽지만 소스코드로 바꾸기는 까다로운 문제를 칭한다.

1. 시뮬레이션

• 시뮬레이션 - 일련의 명령에 따라서 개체를 차례로 이동시키는 문제. 단순 구현 문제이기 때문에 어떻게 구현할지의 아이디어를 소스코드화 하는 것이 중요하다.

내 답안.

#상하좌우
#첫줄에 공간의 크기 N * N 을 나타내는 N 입력!
#둘째줄에 A가 이동할 계획을 공백단위로 입력!
#최종 도착좌표 (X, Y)를 공백단위로 출력
#시작위치 = (1,1)
N = int(input())
A_move = list(input().split())
#travel_map =[[i for i in range(1, N+1)] for j in range(1, N+1)]

# 만약 배열 밖을 벗어나는 범위 예외처리
#A의 현재 위치
A_x = 1
A_y = 1
for i in A_move:
    if i == 'R':
        if A_x == N:
            pass
        else:
            A_x += 1
    if i == 'U':
        if A_y == 1:
            pass
        else:    
            A_y -= 1
    if i == 'D':
        if A_y ==N:
            pass
        else:
            A_y += 1
    if i == 'L':
        if A_x == 1:
            pass
        else:
            A_x -= 1
    

print(f'{A_y} {A_x}')

사실 이렇게 풀어도 정답이 나오지만, 세련되게 위에 주석처리한 2차원 배열을 선언해 풀어내도 된다.

모범답안

# 입력받기
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)):
        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. 브루트포스(완전 탐색)

• 브루트포스는 완전탐색으로 모든 경우의 수를 전부 탐색한다. 파이썬은 초당 2천만번 이상의 연산을 수행할 수 있으므로, 시간복잡도에 의한 경우의 수를 잘 따져보고 사용해야 시간 초과가 나지 않는다.

#시각
#24이하의 정수 N 입력
#모든 시각에서 3이 하나라도 포함되는 모든 경우의 수를 구함.
# 00시 00분 00초 ~ N시 59분 59초까지

#풀이 ->N이 1을 입력받으면
#00.00.03, 00.00.13. 00.00.23.. 00.00.30~39 ... 00.00.53 -> 매 분 확정 15개
#00.03.xx 일 때, 00~59까지 -> 60개
#... 모든 경우의 수를 나눌 수 없으니 완전 탐색(브루트포스)으로 풀어야한다.

N = int(input())

count_result = 0
#시간 분 초 단위를 3중 반복문으로 돌려서 문자열로 바꿔줘 3을 포함하면 경우의 수 count_result에 1을 추가해준다.
for i in range(N+1):
    for j in range(60):
        for k in range(60):
            if '3' in str(i) + str(j) + str(k):
                count_result += 1

print(count_result)

오늘의 교훈? 너무 다차원적으로 생각하기보다

1.먼저 전부 무식하게 탐색이 되는가?

2.좌표나 이동하는 시뮬레이션 문제는 이동할 수 있는 행동자체를 리스트 등으로 할당해버리자!