Implementation - 아이디어를 코드로 바꾸는 구현

Implementation

 코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 우리는 알고리즘 문제를 해결할 때, 문제를 읽고 문제 풀이 방법을 고민한다. 고민 끝에 문제에 대한 정확한 풀이 방법이 떠오르면 바로 정답 처리를 받을 수 있을까? 그렇지 않다. 생각해낸 문제 풀이 방법을 우리가 원하는 프로그래밍 언어로 정확히 구현해냈을 때 비로소 정답 처리를 받을 수 있다. 이를 위해 프로그래밍 언어의 문법을 정확히 알고 있어야 하며 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 한다.
 
 어떤 문제가 구현하기 어려운 문제일까? 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제, 특정 소수점 자리까지 출력해야 하는 문제ㅡ 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱) 문제 등이 까다로운 구현 유형의 문제라고 할 수 있다. 대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기가 까다롭다.
 
 N개의 원소가 들어 있는 리스트에서 R개의 원소를 뽑아 한 줄로 세우는 모든 경우를 구해야 하는 문제는 무작정 기능을 전부 작성할 수도 있다. 하지만 파이썬의 itertools와 같은 표준 라이브러리로 쉽게 짜는 방법도 있다. 이는 언어의 문법을 잘 이해하고 경험이 있어야만 바로 떠올릴 수 있는 해결 방법이다.
 
 이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다루고 있다. 완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다.
 
 

- Part 02 _ Chapter 04 구현 104p

---

연습 문제: 상하좌우, 시각
실전 문제: 왕실의 나이트, 문자열 재정렬
 

- 예제 1. 상하좌우

 여행가 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를 만나면 무시된다.
 
 계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.
 
입력 조건

● 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 ≤ N ≤ 100)
● 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1 ≤ 이동 횟수 ≤ 100)
 
입력 예시
5
R R R U D D
 
출력 예시
3 4

---

접근

 이동할 계획서의 문자를 하나씩 추출하면서 여행자를 이동시키는데, 이동할 수 있는 범위가 아니라면 그 행위는 무시하는 방법으로 코드를 작성했다.
 

구현

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

for d in data:
    if d == 'R':
        y += 1
        if y > n:
            y = n
    elif d == 'U':
        x -= 1
        if x < 1:
            x = 1
    elif d == 'D':
        x += 1
        if x > n:
            x = n
    elif d == 'L':
        y -= 1
        if y < 1:
            y = 1

print(x, y)

  분기점을 나누는 것은 올바른 방법이지만 과하게 사용하면 코드를 들여다 보았을 때 복잡하다는 생각이 들 수 있다. 조건 분기점을 줄여나가는 방법은 없을까?

---

해설

 이 문제를 요구사항대로 구현하면 연산 횟수는 이동 횟수에 비례하게 된다. 
 

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

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)

 
 L, R, U, D에 따라 dx, dy 리스트를 선언하여 2차원 좌표에서 여행자를 움직인 모습을 볼 수 있다. 가로 축은 x, 세로 축은 y이며 제 4사분면이 +, +임을 인지하자.
 
 입력 받은 이동 계획서의 문자를 move_types 리스트의 요소와 하나씩 대조하면서 해당하는 이동을 실행시킨다. 그리고 이동할 때 마다 nx, ny를 확인하며 잘못된 값이 나왔을 경우, 그 이동은 인정하지 않는다.

---

- 예제 2. 시각

 

 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세야 하는 시각이다.

• 00시 00분 03초
• 00시 13분 30초

 반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다.

• 00시 02분 55초
• 01시 27분 45초

입력 조건

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

입력 예시

5
 

출력 예시
11475

---

접근

 완전 탐색 방법을 사용했다. 시간을 1초 단위로 증가시키면서 매 초마다 시, 분, 초로 나누어 모든 값에서 문자 '3'이 있는지 찾는다. 발견 되었으면 횟수를 세고, 발견되지 않았다면 반복문의 조건으로 돌아가 다시 초를 센다.
 

구현

n = int(input())
t = 0
cnt = 0

while (t < ((n + 1) * 3600) - 1):
    t += 1
    h = t // 3600
    if (h // 10 == 3) or (h % 10 == 3):
        cnt += 1
        continue
    m = t % 3600 // 60
    if (m // 10 == 3) or (m % 10 == 3):
        cnt += 1
        continue
    s = (t % 3600) % 60
    if (s // 10 == 3) or (s % 10 == 3):
        cnt += 1
        continue

print(cnt)

 
 시, 분, 초를 각각 나누어 확인하는 방법이 정당하다고 생각하는데, 풀면서도 '한  번에 찾아낼 수 있는 다른 방법이 있지 않을까'라는 생각이 떠나질 않았다. 해답은 어떻게 풀었는지 궁금했다.

---

해설

 이 문제는 모든 시각의 경우를 하나씩 모두 세서 풀 수 있는 문제다. 하루는 86,400초로, 00시 00분 00초부터 23시 59분 59초까지의 모든 경우는 86,400가지 밖에 없기 때문이다. 경우의 수가 10만개도 되지 않으므로 파이썬에서 문자열 연산을 이용해 3이 시각에 포함되어 있는지 확인해도 시간 제한 2초 안에 문제를 해결할 수 있다.

 

 따라서 단순히 시각을 1씩 증가시키면서 3이 하나라도 포함되어 있는지 확인하면 될 것이다. 전체 시, 분, 초에 대한 경우의 수는 24 x 60 x 60이며 3중 반복문을 이용해 계산한다.
 

h = int(input())

count = 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):
                count += 1
                
print(count)

 

 나 역시, 시, 분, 초를 문자열로 생각해서 '3'이 존재하는 지를 찾는 방법을 생각했다. 그런데 시도하지 않은 이유는 시간이 2개로 표현되었기 때문이다. 예를 들어 3시는 03시와 3시로 표현되므로 문자열의 글자가 1, 2중 무엇인지 판단을 하고 찾아야 한다고 생각했기 때문이다. 하지만 이 문제에서 그것은 중요하지 않았던 것 같다. 3이 존재하는지만 판단하면 됐고, 내 바람대로 시, 분, 초를 모두 문자열로 바꾸어 붙인다음 한번에 확인하는 방법을 사용하고 있다. 문자열 인덱스를 하나하나 들여다 볼 필요 없이, 저런 구문으로 해결할 수 있었던 것이다.

---

왕실의 나이트

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

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

 이처럼 8 x 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 이때 왕실의 정원에서 행 위치를 표현할 때는 1 ~ 8이며, 열 위치를 표현할 때는 a ~ h이다.

입력 조건

• 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다.   (1 ≤ N, M ≤ 100)
• 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.

입력 예시
a1

 

출력 예시
2

---

접근

 앞의 문제에서 사용했던 move_types를 이용해 보려고 했다. 이동할 수 있는 모든 경우의 수를 리스트에 저장한 뒤, 이동 행위 연산을 실행하고 이동한 x와 y가 가능한 위치인지를 확인하는 방법으로 문제를 풀어보았다.
 

구현

start = input()
move_types = [(-2, -1), (-2, 1), (2, -1), (2, 1), (1, 2), (-1, 2), (1, -2), (-1, -2)]
cnt = 0

x = ord(start[0])   #행 (아스키코드로 변환)
y = int(start[1])   #열
for i in range(len(move_types)):
    dx = x + move_types[i][0]
    dy = y + move_types[i][1]
    if (ord('a') <= dx <= ord('h')) and (1 <= dy <= 8):
        cnt += 1

print(cnt)

 

 덧셈 연산을 하기 위해서 ord() 함수를 이용해 정수로 바꾸었고, 나중에 다시 알파벳으로 바꾸려고 하였다. start(시작 위치)에서 모든 이동 행위를 연산시켜 보며, 가능한 위치에 존재하는가를 확인하고 가능하다면 횟수를 센다.

---

해설

 왕실의 나이트 문제는 앞서 다루었던 예제 4-1 '상화좌우' 문제와 유사하다. 나이트가 이동할 수 있는 경로를 하나씩 확인하여 이동하면 된다. 다만, 8 x 8 좌표 평면을 벗어나지 않도록 꼼꼼하게 검사하는 과정이 필요하다.
 

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

# 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 리스트를 선언하여 이동할 방향을 기록할 수 있었지만, 이번 문제에서는 steps 리스트의 요소인 튜플이 그 역할을 대신하여 수행한다. 두 가지 풀이에 익숙해져야 하겠다.
 

---

문자열 재정렬
 

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

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

입력 예시
AJKDLSI412K4JSJ9D

 

출력 예시
ADDDIJJJKKLSS20

---

접근

 입력 받은 문자열의 문자를 하나씩 확인해 보면서 알파벳과 숫자를 따로 구분을 한다. 그 다음에 알파벳은 정렬하여 먼저 출력하고 숫자를 출력하면 조건에 맞게 출력문이 완성될 것이라 생각했다.
 

구현

s = input()
lstr = []
sum = 0
for c in s:
    if 'A' <= c <= 'Z':
        lstr.append(c)
    else:
        sum += int(c)
lstr.sort()

for i in range(len(lstr)):
    print(lstr[i], end = '')
if sum != 0:
    print(sum)

 문자열에서 알파벳을 만났으면 리스트에 저장한 뒤, 정렬 함수를 사용하였다. 정렬을 사용하기 위해 리스트를 선언해야 겠다고 판단했지만, 정렬 함수를 사용하지 않는다면 정렬을 문자열 내에서 진행할 수 있게 버블 정렬을 사용해 풀었을 것이다. 시간이 많이 걸리겠지만 말이다.

---

해설

 해설도 크게 다르지 않았다. 다만 출력하는 방법이 차이가 있어서, 얻어갈 것이 있나 살펴보았다.

 

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

 
 

 이 풀이는 숫자 부분까지도 리스트에 넣었다는 것과 출력할 때 join() 함수를 이용한 것이 차이가 있다. join 함수는 문자열을 합치는데에 쓰이고, 인자로 리스트를 받는다. 해설 코드에서 ''.join(리스트) 꼴로 쓰인 것을 볼 수 있는데, ''(작은 따옴표) 안에는 구분자를 넣는다. 즉, 리스트의 요소를 구분자를 넣어서 문자열을 합치는 함수이다. 현재는 구분자가 존재하지 않기 때문에 리스트 요소(문자 = 알파벳)이 전부 붙어서 출력된다.

---

마치며

 구현 문제의 시작할 때 들었던 것처럼, 문제를 풀 아이디어는 금방 떠오르지만 이를 코드 작성으로 바로 이어지는 것에 어려움을 느꼈다. 문제에서 요구하는 대로 하나하나 처리하면서 풀어내게 되면 풀 수 있지만 코드가 길어지거나 예외 처리를 하지 확실히 하지 못하게 된다. 이것이 구현 문제의 난이도를 가르는 척도라고 생각한다.
 
 현재는 처음 학습하는 단계이니까 어떻게든 스스로 풀어내는 것에 집중하고 있다. 훗날 난이도 있는 문제를 접하게 되면 반짝 떠오른 방법으로 바로 시도했다가 돌이킬 수 없게 시간을 낭비하고 재코딩할지도 모르겠다.