[이것이 코딩테스트다] 구현 문제
이번에는 시뮬레이션과 완전 탐색에 중점을 둔 구현 문제에 대해 알아보겠습니다.
구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
(사실상 모든 문제가 구현 문제라고 생각할 수 있습니다;^^)
그러나 일반적으로 구현 유형의 문제는 문제에서 요구하는 내용이 구현에 초점이 맞춰있거나, 구현이 어려운 문제를 의미합니다.
즉, 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭합니다.
- 알고리즘은 간단한데 코드가 지나칠만큼 길어지는 문제
- 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
- 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
- 적절한 라이브러리를 찾아서 사용해야 하는 문제
이러한 구현 문제의 경우, 다양한 라이브러리를 익히는 등 많은 연습이 필요한 문제입니다.
행렬은 파이썬에서 2차원 리스트와 동일합니다.
오른쪽으로 이동하면 열 인덱스가 증가하며, 아래쪽으로 이동하면 행 인덱스가 증가하는 것입니다.
그렇기 때문에 실제로 완전탐색 혹은 시뮬레이션 문제를 접할 때,
가장 왼쪽 위를 (0, 0)로 제공하는 경우가 많습니다.
또한, 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용되고 있습니다.
즉, 캐릭터나 사물 등이 특정 위치에 존재하며 상하좌우로 움직이는 등의 경우가 많습니다.
이러한 경우에는 방향 벡터가 사용되게 됩니다.
즉, 아래와 같이 방향을 나타내게 되죠.
# 동, 북, 서, 남
dx = [0, -1, 0, 1] # 세로축(행)
dy = [1, 0, -1, 0] # 가로축(열)
동쪽 방향의 경우 세로는 이동하지 않고, 가로는 오른쪽으로 이동하므로 [0, 1]의 형태를 띄게 되는 것입니다.
또한, 북쪽의 경우 가로는 이동하지 않고, 세로는 위로 이동하므로 -1을 해주게 됩니다.
저는 여기서 왜 위로 이동하는데 +1이 아니지? 라고 궁금했었는데요,
이는 위에서처럼 아래로 갈수록 인덱스가 증가하고, 오른쪽으로 갈수록 인덱스가 증가하기 때문입니다.
즉, 우리가 일반적으로 생각하는 수학적인 방향으로 생각하면 안되는 것이지요!
예제 문제) 상하좌우
: 아래 문제는 가장 대표적인 구현 문제 (시뮬레이션 유형) 입니다.
일반적으로 (0, 0)부터 출발을 합니다.
그러나 위의 문제에서처럼 (1, 1)부터 시작한다고 명시한다면
가장 첫 번째 인덱스는 사용하지 않는 방식을 사용하거나, (1, 1)을 (0, 0)으로 고려하여 문제를 풀어볼 수 있습니다.
지도에는 R -> R -> R -> U -> D -> D 가 적혀있습니다.
R -> R -> R 까지는 움질일 수 있지만, 그 위치에서 U (위쪽)으로 이동할 수 없기 때문에 무시가 됩니다.
그 후, D -> D 로 이동을 하면, 여행가의 위치는 (3, 4)가 됩니다.
풀이
이 문제는 요구사항대로만 충실히 구현하면 되는 문제입니다.
일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로도 분류되며,
구현이 중요한 대표적인 문제 유형입니다.
다만, 알고리즘 문제 풀이 사이트에 따라 정의하는 문제 유형이 다를 수 있기 때문에,
시뮬레이션 유형, 구현 유형, 완전 탐색 유형은 서로 유사한 점이 많다는 정도로만 기억해야 합니다.
# N 입력받기
n = int(input())
x, y = 1, 1
plans = input().split()
# 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)
문제) 시각
문제
풀이
모든 가능한 시각은 86,400가지 입니다.
이와 같은 수는 컴퓨터 입장에서 그다지 많은 경우의 수가 아니기 때문에,
단순히 시각을 1씩 증가시키면서 매 순간마다 3이 하나라도 포함되어 있는지 확인하면 되는 것입니다.
즉, 이러한 문제는 가능한 경우의 수를 모두 검사해보는 완전 탐색 문제 유형이라고 설명할 수 있습니다.
# H를 입력받기
h = int(input())
count = 0
# i는 시
for i in range(h + 1):
# j는 분
for j in range(60):
# k는 초
for k in range(60):
# 매 시각 안에 '3'이 포함되어 있다면 카운트 증가(문자열 형태로 만들어 나열함)
if '3' in str(i) + str(j) + str(k):
count += 1
print(count)
문제) 왕실의 나이트
문제
예를 들어, c2에 있을 때는 행렬상에서 (2, 3)에 위치한다고 볼 수 있습니다.
이 경우에는 빨간색으로 표시한 위치에만 이동할 수 있으므로, 이동할 수 있는 경우의 수는 6가지 입니다.
위와 같이 a1으로 입력이 주어지게 되면, 이동할 수 있는 위치는 2가지가 됩니다.
풀이
이 문제 역시 전형적인 시뮬레이션, 완전 탐색 문제입니다.
요구사항대로 충실히 구현하면 되는 문제이며,
특정 위치에서 이동 가능한 나이트의 8가지 경로를 하나씩 확인하며, 매번 각 위치로 이동이 가능한지 확인합니다.
따라서 리스트를 이용하여 8가지 방향에 대한 방향 벡터를 정의하면 되는 것입니다.
# 현재 나이트의 위치 입력받기
input_data = input()
row = int(input_data[1]) # 두 번째 문자가 행의 위치
column = int(ord(input_data[0])) - int(ord('a')) + 1
# 컬럼은 문자 값을 아스키 값으로 바꾸고, 이 값에서 'a'를 아스키 값으로 바꾼 값을 뺀 값
# 나이트가 이동할 수 있는 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)
즉, 앞서 했던 것처럼 dx, dy를 정의하지 않고,
단순히 이동가능한 범위 (8가지)를 하나의 리스트로 정의해서 문제를 풀 수 있습니다.
문제) 문자열 재정렬
문제
풀이
이 문제 역시 요구사항대로 충실히 구현하면 되는 문제입니다.
문자열이 입력되었을 때 문자를 하나씩 확인하며,
숫자인 경우 합을 계산하며, 알파벳의 경우 별도의 리스트에 저장합니다.
그 후, 리스트에 저장된 알파벳을 정렬해 출력하고, 합계를 뒤에 붙여 출력하면 되는 문제입니다.
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))
참고문헌 : "이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저) 의 유튜브 강의
https://www.youtube.com/watch?v=2zjoKjt97vQ&t=674s