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

• 구현(implementation)이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.
• 흔히 문제 해결 분야에서 구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만 코드로 옮기기 어려운 문제를 의미한다. 대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기가 까다롭다.
• 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
• 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형

구현 시 고려해야 할 메모리 제약 사항

• 파이썬에서는 프로그래머가 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산도 지원한다.
• 메모리를 제한하는 알고리즘 문제에서는 이를 염두에 두고 코딩을 해야 한다.

채점 환경

• 파이썬은 C/C++에 비해 동작 속도가 느리다.
• 일반적으로 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야 한다.

구현 문제에 접근하는 방법

• 보통 구현 유형의 문제는 사소한 조건을 문제에서 명시해주며 문제가 길다.
• 문자열 처리가 덜 까다로운 파이썬은 구현문제를 쉽게 해결할 수 있다.
• PyPy는 파이썬과 문법이 동일하지만 속도가 매우 빠르다.

예제 1. 상하좌우

문제

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

계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다. 이때 여행가 A가 N*N 크기의 공간을 벗어나는 움직임은 무시된다. 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

해설

요구사항대로 구현하면 연산 횟수는 이동 횟수에 비례하게 된다. 즉 시간복잡도는 O(N)이다. 코딩 테스트나 알고리즘 대회에서 가장 난이도가 낮은 1-2번은 대부분 그리디나 구현 문제이다.

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

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move = ['L', 'R', 'U', 'D']

for plan in plans :
    for i in range(4):
        if plan == move[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이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오.

해설

하루는 86,400초로 제일 큰 경우의 수는 86,400가지뿐이다. 다시 말해 경우의 수가 100,000개도 되지 않으므로 파이썬에서 문자열 연산을 하더라도 2초 안에 문제를 해결할 수 있다. 이러한 유형은 완전 탐색 유형으로 분류되기도 한다. 완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사하는 탐색이다. 일반적으로 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색을 사용하면 적절하다.

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)

2. 왕실의 나이트

난이도 하

문제

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

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

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

해설

나이트가 이동할 수 있는 경로를 하나씩 확인하여 이동하면 된다. 다만 좌표 평면을 벗어나지 않도록 꼼꼼하게 검사하는 과정이 필요하다.

코드

# 현재 나이트의 위치
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)]

# 각 위치로 이동이 가능한지 확인
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)

3. 게임 개발

문제

캐릭터가 있는 장소는 1*1 크기의 정사각형으로 이뤄진 N * M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다. 맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 이러하다.

1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 갈 곳을 정한다.
2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

현민이는 위 과정을 반복적으로 수행하면서 캐릭터의 움직임에 이상이 있는지 테스트하려고 한다. 메뉴얼에 따라 캐릭터를 이동시킨 뒤에 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.

해설

전형적인 시뮬레이션 문제이다. 별도의 알고리즘이 필요하다기보다는 문제에서 요구하는 내용을 오류 없이 성실하게 구현만 할 수 있다면 풀 수 있다는 특징 있다. 다만, 문제가 길고 문제를 바르게 이해하여 소스코드로 옮기는 과정이 간단하지 않다. 반복적인 숙달이 중요하다.

일반적으로 방향을 설정해서 이동하는 문제 유형에서는 dx dy라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적이다.

코드

n, m = map(int, input().split())

d = [[0] * m for _ in range(n)]
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[nx][ny] == 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)

참고자료 : 이것이 코딩 테스트다 (나동빈 저)