구현 알고리즘 (Implementation Algorithm)

구현(Implementation)

• 코딩 테스트에서 구현이란 머릿 속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.
• 구현 문제는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제이다.
• 구현 문제를 풀기 위해서는 프로그래밍 언어의 문법을 정확히 알고 있어야 한다.
• 또한 적절한 라이브러리를 찾아서 사용해야 한다.
• 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다.

2차원 행렬(Matrix)

 

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

---

문제 1 : 상하좌우

난이도: 하 | 제한시간: 15분  |  시간제한: 2초 | 메모리 제한: 128MB

여행가 A는 N x N 크기의 정사각형 공간 위에 있습니다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있습니다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당합니다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)입니다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있습니다.

 

계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있습니다. 각 문자의 의미는 다음과 같습니다.

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

이때 여행가 A가 N x N 크기의 정사각형 공간을 벗어나는 움직임은 무시됩니다.

예를 들어 (1, 1)의 위치에서 L 혹은 U를 만나면 무시됩니다.

입력 조건

첫째 줄에 공간의 크기를 나타내는 N이 주어집니다. (1 <= N <= 100)
둘째 줄에 여행가 A가 이동할 계획서 내용이 주어집니다. (1 <= 이동 횟수 <= 100)

출력 조건

첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백을 기준으로 구분하여 출력합니다.

풀이

# 아이디어 : 각 움직임 마다 무브타입과 비교하여 이동

n = int(input())    # 5
plans = list(map(str, input().split())) # R R R U D D

x,y = 1, 1
    # R, L, D, U
dx = [0, 0, 1, -1]  # row
dy = [1, -1, 0, 0]  # col
move_types = ['R', 'L', 'D', 'U']

for plan in plans:
    for move in range(len(move_types)):
        if plan == move_types[move]:
            nx = x + dx[move]
            ny = y + dy[move]
    # 공간을 벗어나는 경우
    if nx < 1 or ny < 1 or nx > n or ny > n: 
        continue
    x,y = nx, ny

print(x, y) # 3 4

나만의 해결 순서
1. 현재 위치 입력
2. 방향벡터 및 이동유형 만들기
3. 아이디어 적용 (아이디어 : 각 움직임 마다 무브타입과 비교하여 이동)

---

문제 2 : 시각

난이도: 하 | 제한시간: 15분  |  시간제한: 2초 | 메모리 제한: 128MB

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

 

입력 조건

• 첫째 줄에 정수 N이 입력된다. (0 ≤ N ≤ 23)

출력 조건

• 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포하모디는 모든 경우의 수를 출력한다.

# 아이디어 : 가능한 시각의 경우를 모두 세서 풀 수 있음 / 완전 탐색 문제

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) or '3' in str(j) or '3' in str(k):
            # if '3' in str(i)+str(j)=str(k):
                count += 1
print(count)

---

문제 3 : 왕실의 나이트

난이도: 하 | 제한시간: 20분  |  시간제한: 1초 | 메모리 제한: 128MB

행복 왕국의 왕실 정원은 체스판과 같은 8 x 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있다. 나이트는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.

1. 수평으로 두 칸 이동한 뒤 수직으로 한 칸 이동하기
2. 수직으로 두 칸 이동한 뒤 수평으로 한 칸 이동하기

이때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현한다.

입력 조건

• 첫째 줄에 8 x 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1처럼 열과 행으로 이뤄진다.

출력 조건

• 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오.

풀이

# 아이디어: 각 방향마다 움직일 수 있는지 체크하기

data = input()
row = int(data[1])
col = int(ord(data[0])) - int(ord('a')) + 1

# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [(2,-1), (2,1), (1,2), (1,-2), (-2,-1), (-2,1), (-1,2), (-1,-2)]

cnt = 0
for step in steps:  # 각 방향으로 움직이기(8가지)
    nrow = row + step[0]    # 가로
    ncol = col + step[1]    # 세로
    
    if nrow >= 1 and nrow <=8 and ncol >= 1 and ncol <= 8:  # 이동 가능하면 cnt += 1
        cnt += 1
print(cnt)

---

문제 4 : 문자열 재정렬

 

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

입력 조건

• 첫째 줄에 하나의 문자열 S가 주어집니다. (1 <= S의 길이 <= 10,000)

출력 조건

• 첫째 줄에 문제에서 요구하는 정답을 출력합니다.

풀이

data = input()
value = 0
result = []

for i in data:
    if i.isalpha():     # 알파벳이면 리스트 삽입
        result.append(i)
    else:
        value += int(i) # 숫자면 따로 더해두기

# 알파벳 오름차순 정렬
result.sort()

# 숫자는 가장 뒤에 삽입
if value > 0:
    result.append(str(value))

print(''.join(result))

 

나의 풀이 

data = input()
nums= [i for i in range(0,10)]
alphas = [chr(i) for i in range(65,91)] # ASCII 코드 활용

value = 0
result = []
for i in data:
    if i in alphas:
        result.append(i)
    else:
        value += int(i)

result.sort()

if value > 0:
    result.append(str(value))

print(''.join(result))

isalpha()라는 함수를 몰라 어렵게 풀었다.