구현: 시뮬레이션과 완전 탐색

구현이란, 머릿속에 있는 알고리즘을 실제 코드로 바꾸는 과정이다. 하지만, 알고리즘 대회에서 구현 유형은 풀이를 떠올리는 것은 쉽지만, 코드로 옮기기는 어려운 문제를 지칭한다. 

• 알고리즘은 간단하지만, 코드가 지나칠만큼 길어지는 문제
• 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
• 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
• 적절한 라이브러리를 찾아서 사용해야 하는 문제

또한, 일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(matrix)를 의미한다. 시뮬레이션 및 완전 탐색 문제의 경우 2차원 공간에서의 방향 벡터가 자주 활용된다.

# 동, 북, 서, 남
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

# 현재 위치
x, y = 2, 2

for i in range(4):
	# 다음 위치
    nx = x + dx[i]
    ny = y + dy[i]
    print(nx, ny)

이 때 x는 행의 값(= 세로축) 이고, y는 열의 값(=가로축)이다.

 

ex) 상하좌우 문제(시뮬레이션 유형)

여행가 A는 N x N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 )1,1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1,1)이다. 우리 앞에 여행가 A가 이동할 계획이 적힌 계획서가 있다. 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L,R,U,D 중 하나의 문자가 반복적으로 적혀 있다.

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

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_type[i]:
        	nx = x + dx[i]
            ny = y + dy[i]
    # 공간을 벗어나면 무시
    if nx < 1 or ny < 1 or nx > x or ny > n:
    	continue
    
    x, y = nx, ny # 이동 수행

print(x, y)

 

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

가능한 모든 시각의 경우를 하나씩 세서 풀 수 있는 문제이다. 하루는 (24 * 60 * 60) 86,400초 이다. 00시 00분 00초부터 시각을 1씩 증가시키면서 3이 하나라도 포함되어 있는지 확인한다. 이런 유형을 완전 탐색(Brute Forcing) 유형(가능한 경우의 수를 모두 검사해보는 탐색 방법)이라고 부른다.

n = int(input())

count = 0
for i in range(n+1):
	for j in range(60):
    	for k in range(60):
        	if '3' in str(i) + str(j) + str(k): #시,분,초를 나열
            	count += 1

print(count)

문제 2) 행복 왕국의 왕실 정원은 체스판과 같은 8x8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다. 나이트는 이동 시 L자 형태로만 이동할 수 있으며, 정원 밖으로는 나갈 수 없다. 나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동한다.

  1. 수평으로 두 칸 + 수직으로 한 칸

  2. 수직으로 두 칸 + 수평으로 한 칸

이와 같은 좌표 평면에서 나이트의 위치가 주어졌을 때, 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. (1 ~8은 행 위치로, a ~ h는 열 위치로 표현함)

input_data = input()
row = int(input_data[1])
col = 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)]

#각 위치로 이동 가능한 지 확인
result = 0
for step in steps:
	next_row = row + step[0]
	next_col = col + step[1]
    
    if next_row >= 1 and next_row <= 8 and next_col >= 1 and next_col <=8:
    	result += 1

print(result)

문제 3) 알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어진다. 이 때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력한다. 예를 들어, K1KA5CB7이라는 값이 들어오면 ABCKK13을 출력한다.

• 숫자는 따로 합계 계산
• 알파벳의 경우 별도의 리스트 계산

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