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

코딩 테스트에서 구현(implementation)이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 

어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을

포함하는 개념이다.

그런 의미에서 알고리즘 교재에서는 대부분 구현을 별도의 유형으로 다루지 않지만, 취업을 목표로 하는

코딩 테스트에서는 구현이 중심이 되는 문제가 자주 출제되기에 다른 알고리즘을 배우기 전에 먼저 다루고자 한다.

 

이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다루고 있다. 완전 탐색은 모든 경우의 수를 

주저 없이 다 계산하는 해결 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계식 차례대로 직접 

수행해야 하는 문제 유형을 의미한다. 

 

구현 문제에 접근하는 방법

보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편이다. 

문제의 길이를 보고 지레 겁먹는데, 고차원적인 사고력을 요구하는 문제는 나오지 않는 편이라 문법에 익숙하다면 

오히려 쉽게 풀 수 있다.

 

예제 4-1 상하좌우 (책 110페이지)

 

내가 푼 답:

N = int(input())
move = list(map(str, input().split()))

trav = [1, 1]

for i in range(len(move)):
    if move[i] == 'L':
        if trav[1] == 1:
            continue
        trav[1] -= 1
    elif move[i] == 'R':
        if trav[1] == N:
            continue
        trav[1] += 1
    elif move[i] == 'U':
        if trav[0] == 1:
            continue
        trav[0] -= 1
    elif move[i] == 'D':
        if trav[0] == 5:
            continue
        trav[0] += 1

print(trav[0], trav[1])

책의 답:

n = int(input())
x, y = 1, 1
nx, ny = 0, 0
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_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)

책에서는 확실히 나보다 더 스마트하게 풀었다고 볼 수 있다.

dx, dy, move_types을 선언하고 이를 사용 하며 예외처리 방법도 더 간단하게 수행한다.

이 방법을 숙지해놓고 써먹어야겠다.

 

예제 4-2 시각 (책 133페이지)

 

내가 푼 답:

N = int(input())

cnt = 0

for i in range(N+1):
    for j in range(60):
        for k in range(60):
            # print(i, j, k)
            if((i // 10 == 3) or (i % 10 == 3) or (j // 10 == 3) or (j % 10 == 3) or (k // 10 == 3) or (k % 10 == 3)):
                cnt += 1
                # print(cnt)

print(cnt)

책의 답:

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)

책의 답에서는 'in'이라는 포함연산자를 사용했다. 각 시간을 문자열로 처리하여 3이 들어있는 경우 카운트가 되도록

했다. 이 방법 역시 내가 사용한 방법보다 더 깔끔하고 길이도 짧다. 

 

예제 4-3 왕실의 나이트 (책 115페이지)

 

내가 푼 답:

knight = input()

row = ord(knight[0]) - 96
column = int(knight[1])

nx, ny = 0, 0

row_steps = [2, 2, -2, -2, 1, -1, 1, -1]
column_steps = [1, -1, 1, -1, 2, 2, -2, -2]

count = 0

for i in range(8):
    nx = row + row_steps[i]
    ny = column + column_steps[i]

    if (nx > 0 and nx < 9) and (ny > 0 and ny < 9):
        count += 1

print(count)

책의 답:

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)

책의 답에서는 이동할 방향을 기록하는 리스트를 2차원 리스트 하나로 만들었다. 확실히 깔끔하고 내가 짠 코드보다

수준 높은 코드라는 생각이 든다. 위와 같이 2차원 리스트를 활용하는 방법도 있다는 것을 숙지해두자.

 

예제 4-4 게임개발 (책 118페이지)

 

책 풀이:

# N,M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

# 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
d = [[0] * m for _ in range(n)]
# 현재 캐릭터의 X 좌표, Y 좌표, 방향을 입력받기
x, y, direction = map(int, input().split())
d[x][y] = 1  # 현재 좌표 방문처리

# 전체 맵 정보를 입력받기
array = []
for i in range(n):
    array.append(list(map(int, input().split())))

# 북, 동, 남, 서 방향 정의
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 왼쪽으로 회전


def turn_left():
    global direction
    direction -= 1
    if direction == -1:
        direction = 3


# 시뮬레이션 시작
count = 1
turn_time = 0
while True:
    # 왼쪽으로 회전
    turn_left()
    nx = x + dx[direction]
    ny = y + dy[direction]
    # 회전한 이후 정면에 가보지 않은 칸이 존재하는 경우 이동
    if d[x][y] == 0 and array[nx][ny] == 0:
        d[nx][ny] = 1
        x = nx
        y = ny
        count += 1
        turn_time = 0
        continue
    # 회전한 이후 정면에 가보지 않은 칸이 없거나 바다인 경우
    else:
        turn_time += 1
    # 네 방향 모두 갈 수 없는 경우
    if turn_time == 4:
        nx = x - dx[direction]
        ny = y - dy[direction]
        # 뒤로 갈 수 없다면 이동하기
        if array[nx][ny] == 0:
            x = nx
            y = ny
        # 뒤가 바다로 막혀있는 경우
        else:
            break
        turn_time = 0

# 정답 출력
print(count)

이 문제는 난이도도 있고 문제 이해가 잘 안 되어서 책 풀이를 바로 봤다. 코드를 살펴보니 구현 문제는 정말 문제 조건을 코드로 옮기면 되는 문제라는 생각이 들었다. 백준에서 구현 문제를 더 풀어보면서 실력을 좀 더 올리고 이 문제를 

다시 풀어보면서 이해 할 생각이다.