구현(시뮬레이션 알고리즘)

완전탐색 : 모든 경우의 수를 다 계산하는 방법
시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 것

구현으로 묶이는 알고리즘 유형은 모든 경우를 하나씩 직접 수행해서 결과를 도출하는 것으로 문제에서 하라는대로만 잘 따라하면 답이 나온다. 머리로 생각한 것을 코드로 구현할 수 있는지 보는 문제들이다.

완전 탐색 알고리즘은 비효율적인 시간복잡도를 갖고 있기 때문에 데이터 개수가 100만개 이하일 때 적절하다.

1. 상하좌우

내 풀이

# n을 입력받음
n = int(input("n을 입력하시오 >> "))

# 명령을 입력받음
orders = input("명령을 입력하시오 >> ").split()

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

x, y = 1, 1

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

for order in orders:
    for i in range(len(codes)):
        if order == codes[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)

예외를 제외하는 조건문을 조건문 안에 넣었더니 제대로 검사하지 못하고 2,4라는 오답이 출력된다.

좀 더 나은 풀이

# n을 입력받음
n = int(input("n을 입력하시오 >> "))

# 명령을 입력받음
orders = input("명령을 입력하시오 >> ").split()

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

x, y = 1, 1

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

for order in orders:
    for i in range(len(codes)):
        if order == codes[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)

조건문을 반복문 밖으로 꺼내서 작성해야 모든 예외를 처리할 수 있다.

2. 시각

내 풀이

n = 5
time = [0, 0, 0]
count = 0

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 += 1
print(count)

완전 탐색으로 삼중for문을 이용했다. 전체 데이터의 최대 경우의 수가 24 60 60 = 86400이기 때문에 제한시간 내에 문제를 풀 수 있다.

3. 왕실의 나이트

내 풀이

# 현재 위치
x = int(input('x = '))
y = int(input('y = '))
count = 0

# 8가지 방향
all = [[-2, -1], [-2, 1], [-1, -2], [1, -2], [2, -1], [2, 1], [-1, 2], [1, 2]]

for step in all:
    nx = x + step[0]
    ny = y + step[1]

    if 1 <= nx <= 8 and 1 <= ny <= 8:
        count += 1

print(count)

(처음에 all을 잘못 설정해서 애먹었다ㅠㅠ 꼭 스케치 먼저 하고 코드로 옮기기)
알파벳을 처리할 때

input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0] - ord('a')) + 1)
# 먼저 데이터 입력을 받고나서 a로부터 떨어져있는 거리를 column으로 설정해놓은 방법도 알아두기