Implementation

Created : February 23, 2021

구현(Implementation) 유형: 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제들.

알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용됨.
시뮬레이션 & 완전탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용됨.

상하좌우 문제

N x N 크기의 정사각형 공간에서 (1, 1)시점에서 시작했을때, 계획서에 따라 움직이면 어디에 도달하는지 출력하기.

(정사각형 공간을 벗어나는 움직임은 무시됨.)

# Input
# 5
# R R R U D D

# Output
# 3 4

n = int(input())
plans = input().split()

x, y = 1, 1

move_types = ['L', 'R', 'U', 'D']
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

for plan in plans:
  i = move_types.index(plan)
  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)

시각 문제

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하기

→ 하루는 86,400초이므로 컴퓨터가 충분히 빠르게 계산할 수 있는 범위임. 단순하게 초를 1씩 증가시키면서 3이 포함되어 있는지 확인하면 됨.

→ 완전 탐색(Brute force) 유형 (가능한 경우의 수를 모두 검사해보는 탐색방법)

# Input
# 5

# Output
# 11475

h = int(input())

count = 0
for i in range(h + 1):
  for j in range(60):
    for k in range(60):
      if '3' in str(i) + str(j) + str(k):
        count += 1

print(count)

왕실의 나이트 문제

왕실의 정원은 8 x 8 좌표평면. 나이트는 L자 형태로만 이동할 수 있고, 정원밖으로는 못 나감.

특정 위치에서 2가지 경우로 이동할 수 있음.

수평으로 두 칸 이동 후 수직으로 한 칸 이동
수직으로 두 칸 이동 후 수평으로 한 칸 이동

나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하기.

(행 위치는 위에서부터 1부터 8, 열 위치는 a부터 h)

예) c2에 있을 때 이동할 수 있는 경우의 수는 6가지.

→ 총 가능한 8가지 경로를 하나씩 확인하며 각 위치로 이동이 가능한지 확인하면 됨.

# Input
# a1

# Output
# 2

# 나이트가 이동할 수 있는 8가지 방향 정의하기
steps = [
  (-2, -1),
  (-2, 1),
  (-1, -2),
  (-1, 2),
  (1, -2),
  (1, 2),
  (2, -1),
  (2, 1)
]

input_data = input()
row = int(input_data[1])
column = ord(input_data[0]) - ord('a') + 1

result = 0
for step in steps:
  # 이동하고자 하는 위치 확인
  next_row = row + step[0]
  next_column = column + step[1]

  # 해당 위치로 이동이 가능하다면 카운터 증가
  if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
    result += 1

print(result)

문자열 재정렬

알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 주어졌을때, 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤, 모든 숫자를 더한 값을 이어서 출력하기.

예) K1KA5CB7 → ABCKK13

→ 문자를 하나씩 확인해서 숫자면 따로 합계를 계산하고, 알파벳이면 별도의 리스트에 저장하기.

data = input()

value = 0
result = []

for x in data:
  # 알파벳이면 리스트에 삽입
  if x.isalpha():
    result.append(x)
  # 숫자는 따로 더하기
  else:
    value += int(x)

# 알파벳을 오름차순으로 정렬
result.sort()

# 숫자가 하나라도 존재하는 경우 가장 뒤에 삽입
if value != 0:
  result.append(value)

print(*result, sep='')