[이코테 알고리즘] - 구현

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

구현은 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.
코딩테스트에서 풀이를 떠올리기는 쉬우나 소스코드로 옮기기 어려운 문제를 지칭한다.

🔎 2차원 공간에서 방향벡터

왼쪽부터 순서대로 동, 북, 서, 남 방향의 이동이라고 보면 다음과 같이 나타낼 수 있다. ( x는 북/남 방향으로 이동, y는 동/서 방향으로 이동)

dx = [ 0, -1, 0, 1 ]
dy = [ 1, 0, -1, 0 ]

현재위치가 (2, 2)라고 했을 때 현재위치와 다음위치는 다음과 같이 표현한다.

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

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

📌 예제

• 예제 1 ) 상하좌우 - 시뮬레이션

# 공간의 크기가 N이고 이동계획이
#  L, R, U, D로 주어질 때 최종 도착 좌표는?
# (단, 시작 좌표 즉 왼쪽 맨 위는 (1, 1)이고
# 오른쪽 맨 아래는 (N, N)이며
# 공간을 넘어가는 이동의 경우 무시한다.)

n = int(input())            # 공간의 크기
x, y = 1, 1                 # 시작 좌표
plans = input().split()     # 이동 계획

dx = [0, 0, -1, 1]          # [L, R, U, D]
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 nx > n or ny < 1 or ny > n:
        continue
    x, y = nx, ny

• 예제 2 ) 시각 - 완전탐색

완전탐색인 시각 문제는 가능한 모든 시각의 경우를 하나씩 모두 세서 풀 수 있는 문제로 가능한 모든 경우의 수를 검사해보는 탐색 유형이다.
참고 ) 하루는 86,400초 (24 X 60 X 60)로 모든 경우는 86,400가지이다.
1초 2천만번 연산 수행하는 컴퓨터에서 이 정도는 식은 죽 먹기이다.

# 00시 00분 00초 ~ N시 59분 59초 사이
# 3이 들어가는 경우의 수는?

h = int(input())
cnt = 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):     # 시, 분, 초 문자열로
                cnt += 1

print(cnt)

• 예제 3 ) 왕실의 나이트 - 시뮬레이션 & 완전탐색 & 구현

# 8 X 8 좌표평면에서 나이트는 2가지 경우로 이동 가능하다 (정원 밖은 X)
# - 수평으로 두 칸 수직으로 한 칸
# - 수직으로 한 칸 수평으로 두 칸
# 이처럼 8 X 8 좌표평면상에서 나이트의 위치(ex. a1)가 주어졌을 때
# 나이트가 이동할 수 있는 경우의 수는?
# (단, 행 위치는 1-8로 열 위치는 a-h로 표현한다.)

input_data = input()
row = int(input_data[1])
col = int(ord(input_data[0])) - int(ord('a')) + 1   # 문자 -> 아스키코드: 컬럼의 위치 숫자로 변경 (1, 2, ...)
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

cnt = 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:     # 범위 안이면
        cnt += 1                # 카운트

print(cnt)

• 예제 4 ) 문자열 재정렬

# 문자열 S가 주어질 때 모든 알파벳은 오름차순 정렬
# 모든 숫자의 합은 그 뒤에 출력한다.
# ex. K1A5CB7 -> ABCK13

s = input()
ans = []
tmp = 0

for x in s:
    if x.isalpha():         # isalpha() : 알파벳이면 true 아니면 false
        ans.append(x)       # isdigit() : 숫자면 true 아니면 false
    else:
        tmp += int(x)

ans.sort()
if tmp != 0:
    ans.append(str(tmp))

print(''.join(ans))

🙏 참고

👉 이것이 취업을 위한 코딩테스트다 with 파이썬