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

구현이란?

구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.
풀이를 떠올리는 것은 쉽지만 코드로 옮기기 어려운 문제를 지칭한다.
보통 알고리즘은 간단하지만 코드가 길게 나오는 문제, 실수 연산을 다루고 특정 소수점 자리까지 출력해야 하는 문제, 문자열을 특정한 기준에 따라 끊어 처리해야 하는 문제, 적절한 라이브러리를 찾아서 사용해야 하는 문제 등이 있다.

시뮬레이션 및 완전탐색문제에서는 2차원 공간의 방향벡터가 자주활용

구현 시뮬레이션 예제 1 <상하좌우>

• 크기가 N*N, 시작위치가 (1,1)인 지도에서 여행가가 여행을 시작한다. 이동은 여행 계획서에 따라 이동하는데 L,R,U,D 를 입력받아서 값에 따라 이동할 수 있다. 반경을 벗어나면 무시한다. (LEFT, RIGHT, UP, DOWN)

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

dx = [0, 0, -1, 1] # 행에서의 LRUD 이동방향
dy = [-1, 1, 0, 0] # 열에서의 LRUD 이동방향
move_types = ['L', 'R', 'U', 'D'] # 방향정의

# 입력받은 plan 확인
for plan in plans:
    # 방향확인
    for i in range(len(move_types))
        입력받은 방향과 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)

구현 완전탐색(가능한 모든 경우의 수 탐색) 예제 2 <시각>

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

h = int(input())

count = 0
for i in range(h + 1):
    for j in range(60):
        for k in range(60):
        # 매 시각 3이 포험되어 있다면 카운트 증가
        if '3' in str(i) + str(j) + str(k):
            count += 1
            
print(count)

구현 예제 3 <왕실의 나이트>

• 8*8 체스판을 가진 왕실 정원의 특정한 한칸에 나이트가 서있다. 나이트는 말을 타고있어서 이동은 L자 형태로만 이동할 수 있고 밖으로 나갈 수 없다. 특정위치에서 다음과 같은 2가지 경우로만 이동할 수 있다.

1. 수평으로 두 칸 이동 후 수직으로 한 칸 이동
2. 수직으로 두 칸 이동 후 수평으로 한 칸 이동
   나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하라 행은 1~8로, 열은 a부터 h로 표현한다.

input_data = input()
row = int(input_data[1])
# 열값은 알파벳이기때문에 아스키코드로 변환하여 숫자좌표를 받는다
column = int(ord(input_data[0])) - int(ord('a')) + 1 

# 갈 수 있는 모든 방향 정의
steps = [(-2,-1),(-2,1),(2,-1),(2,1),(-1,-2),(1,-2),(-1,2),(1,2)]

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)

구현 예제 4 <문자열 재졍렬>

• 알파벳 대문자와 숫자(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))
    
# join함수는 리스트를 문자열로 변환해준다
print(''.join(result))