Ⅰ. 구현 유형 알고리즘
-
풀이를 떠올리는 것은 쉽지만 코드로 옮기기 어려운 문제 유형
-
완전 탐색, 시뮬레이션 등등
-
문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제.
Ⅱ. 예제
① 특정 숫자를 포함한 시각
❔ 문제 설명
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하라.
💡 문제 해결 아이디어
-
가능한 경우를 하나씩 모두 일일이 세서 풀 수 있는 문제이다.
-
따라서 단순히 시각을 1씩 증가시키면서 3이 하나라도 포함되어 있는지 확인
-
가능한 모든 경우의 수를 검사하는 탐색 = 완전 탐색
✔️ 풀이
Python
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)② 상하좌우
❔ 문제 설명
여행가 A는 N * N 크기의 정사각형 공간 위에 있다.
이 공간은 1 * 1크기의 정사각형으로 나누어져 있다.
가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N,N)에 해당한다.
여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1,1)이다.
우리 앞에는 여행가 A의 이동 계획이 적힌 계획서가 놓여 있다.
계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L,R,U,D 중 하나의 문자가 반복적으로 적혀있다.
L : 왼쪽 한 칸 이동
R : 오른쪽 한 칸 이동
U : 위로 한 칸 이동
D : 아래로 한 칸 이동💡 문제 해결 아이디어
- 명령에 따라서 개체를 이동시킨다는 점에서 시뮬레이션 유형으로 분류
✔️ 풀이
Python
n = int(input())
x, y = 1, 1
plans = input().split
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) ③ 문자열 재정렬
❔ 문제 설명
알파벳 대문자와 숫자로만 구성된 문자열이 입력으로 주어진다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력한다.
💡 문제 해결 아이디어
-
문자열 입력시 문자를 하나씩 확인.
-
숫자인 경우 따로 합계 계산, 알파벳은 별도의 리스트에 저장
-
리스트에 저장된 알파벳 정렬하고 출력, 뒤에 합계 붙여 출력
✔️ 풀이
Python
data = input()
result = []
value = 0
for x in data:
if x.isalpha():
result.append(x)
else:
value += int(x)
result.sort()
if value != 0:
result.append(str(value))
print(''.join(result))④ 왕실의 나이트
❔ 문제 설명
행복 왕국의 왕실 정원은 체스판과 같은 8 * 8 좌표 평면입니다. 왕실 정원의 특정한 한 칸에 나이트가 서있습니다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마합니다.
나이트는 말을 타고 있기 때문에 이동할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없습니다.
나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있습니다.
1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기8 * 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하세요.
💡 문제 해결 아이디어
-
나이트의 8가지 경로를 하나씩 확인하며 각 위치로 이동이 가능한지 확인
-
리스트를 이용하여 8가지 방향에 대한 방향 벡터를 정의
✔️ 풀이
Python
# 현재 나이트의 위치 입력받기
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1
# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]
# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
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)