[Algorithm] 구현(Implementation)

아이디어를 코드로 바꾸는 구현

코딩 테스트에서 구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.

완전 탐색은 모든 경우의 수를 다 계산하는 해결방법을 의미하고.

시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형을 의미한다.

 

상하좌우

n * n 크기의 정사각형 공간을 입력 받고 다음 라인에 L, R, U, D 중 하나의 문자를 연속적으로 입력받는다.

시작하는 포인트는 (1, 1) 이며 n * n 크기의 정사각형 공간을 벗어나는 움직임은 무시된다.

해당 계획서가 주어졌을 때 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하는 문제이다.

• L : 왼쪽으로 한 칸 이동
• R : 오른쪽으로 한 칸 이동
• U : 위로 한 칸 이동
• D : 아래로 한 칸 이동  

n = int(input())
arrs = input().split()
ping = ['L', 'R', 'U', 'D']
x_mov = [0, 0, -1, 1]
y_mov = [-1, 1, 0, 0]

x, y = 1, 1
for j in range(len(arrs)):
  for i in range(len(ping)):
    if arrs[j] == ping[i]:
      nx = x + x_mov[i]
      ny = y + y_mov[i]
      if nx < 1 or ny < 1 or nx > n or ny > n:
        continue
x, y = nx, ny

print(x, y)

시각

정수 N이 입력되면 00시 00분 00초 부터 N시 59분 59초 까지의 모든 시각중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하는 문제이다.

해당 문제는 int 를 문자열로 치환한뒤 '3'을 찾는 방식으로 풀이하였다.

h = int(input())

count = 0
for i in range(h + 1):
 for j in range(60):
   for z in range(60):
    # 모든 수를 문자열로 변환한 뒤 확인 후 카운트 증가
    if '3' in str(z) + str(i) + str(j):
      count += 1
print(count)

왕실의 나이트

체스판이 주어지고 현재 나이트가 있는 위치를 입력하면

나이트 말을 이동할 수 있는 경우의 수를 리턴하는 함수를 구현하는 것이다.

위치 값은 abcdefgh / 12345678 로 입력을 받으며 문자인 col은 아스키 코드로 변환하여 주었다.

knight = input()
col = int(ord(knight[0])) - 96
row = int(knight[1])

steps = [(-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)]
result = 0
for step in steps:
  n_row = row + step[0]
  n_col = col + step[1]
  if n_row > 0 and n_row < 9 and n_col > 0 and n_col < 9:
    result += 1
print(result)

게임개발

게임캐릭터가 맵 안에서 움직이는 프로그램을 구현하는 문제이다.

M * N 크기의 직사각형을 입력받고 각각의 칸은 육지와 바다로 나뉘어진다.

육지는 0 바다는 1로 정의되며 현재 캐릭터의 위치와 바라보고 있는 방향을 입력 받는다.

1. 현재 위치에서 현재 방향을 기준으로 왼쪽방향 부터 차례대로 갈 곳을 정한다.

2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면 왼쪽 방향으로 회전한 다음 왼쪽으로 한칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.

3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단 , 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

0 : 북쪽

1 : 동쪽

2 : 남쪽

3 : 서쪽

n, m = map(int, input().split())
a, b, d = map(int, input().split())
# 동서남북 방향 정의
move = [[-1, 0], [0, 1], [1, 0], [0, -1]]
​
_map = []
for i in range(n):
  _map.append(list(map(int, (input().split()))))
​
answer = 1
turn = 0
_map[a][b] = 2
​
while True:
    turn += 1
    d -= 1
    if d == -5:
        d = 3
    if _map[a + move[d][0]][b + move[d][1]] == 0:
        a += move[d][0]
        b += move[d][1]
        _map[a][b] = 2
        turn = 0
        answer += 1
    if turn == 4:
        a -= move[d][0]
        b -= move[d][1]
        turn = 0
    if _map[a][b] == 1:
        break
print(answer)
​