[구현] 구현 (1) 개요 및 예제

구현

• 알고리즘은 쉽게 떠오르는데, 막상 코드로 작성하기 까다로운 문제 유형
• 시뮬레이션, 완전 탐색 등
• 문법만 잘 숙지한다면 난이도가 낮은 편

이코테 p.110 예제 4-1 상하좌우

내 소스코드

R, L, U, D에 따라서 행, 렬 좌표를 +1 혹은 -1 하는 방식으로 소스코드를 작성함. 만약 N x N 범위를 벗어날 경우 이동이 무시되도록 함.

N = int(input())
data = list(input().split())
col = 1
row = 1

# R은 row + 1
# L은 row - 1
# U은 col - 1
# D은 col + 1

for i in range(len(data)):
  if data[i] == 'R' and (row + 1) <= N:
    row += 1
  elif data[i] == 'L' and (row - 1) >= 1:
    row -= 1
  elif data[i] == 'U' and (col - 1) >= 1:
    col -= 1
  elif data[i] == 'D' and (col + 1) <= N:
    col += 1

print(col, row)

교재 소스코드

• 연산 횟수는 이동 횟수에 비례
  • 이동 횟수가 N번 이라면 시간 복잡도는 O(N)

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

# 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)

이코테 p.113 예제 4-2 시각

교재 소스코드

• 00시 00분 00초부터 23시 59분 59초까지의 모든 경우는 86,400가지밖에 안 되기 때문에 모든 경우의 수를 하나씩 세서 풀 수 있음.
  • 경우의 수가 100,000개도 되지 않으므로 시간 제한 2초 안에 해결 가능
• 시간을 1씩 증가시키면서 3이 하나라도 포함되어 있는지 확인
• 전체 시, 분, 초에 대한 경우의 수는 24 X 60 X 60이며, 3중 반복문으로 계산 가능
• 매 시각을 문자열로 바꾼 다음, 문자열에 '3'이 포함됐는지 검사하기
  • ex) 03시 50분 59초 -> 035059

N = int(input())
result = 0

for hour in range(N + 1):
  for minute in range(60):
    for second in range(60):
      time = str(hour) + str(minute) + str(second)
      if '3' in time:
        result += 1

print(result)