[Algorithm] Implementation (구현법)

우리는 알고리즘 문제를 해결할 때, 문제를 읽고 문제 풀이 방법을 고민한다. 고민 끝에 문제에 대한 정확한 풀이 방법이 떠오르면 바로 정답 처리를 받을 수 있을까? 그렇지 않다. 생각해낸 문제 풀이 방법을 프로그래밍 언어로 정확히 구현해냈을 때 비로소 정답 처리를 받을 수 있다. 이를 위해 프로그래밍 언어의 문법을 정확히 알고 있어야 하며 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 한다. 흔히 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다. 

그렇다면 어떤 문제가 구현하기 어려운 문제일까? 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제, 특정 소수점 자리까지 출력해야 하는 문제, 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야 하는) 문제 등이 까다로운 구현 유형의 문제라고 할 수 있다. 대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기가 까다롭다. 초보자 입장에서는 실제로 코딩 테스트에서 구현 문제를 만나면 당황할 수 있다. 어떻게 풀면 될지 대략 감은 오는데, 막상 코드로 옮기려니 무엇부터 작성해야 할지 모를 수 있기 때문이다. 또한 프로그래밍 문법을 정확하게 숙지하지 못했거나, 라이브러리 사용경험이 부족하면 구현 유형의 문제를 풀 때 불리하다. 무작정 기능을 전부 작성할 수도 있지만 파이썬의 표준 라이브러리를 쉽게 짤 수 있는 방법이 많다. 이는 언어의 문법을 잘 이해하고 경험이 있어야만 바로 떠올릴 수 있는 해결 방법이다. 알고리즘 문제의 유형 중에서 완전탐색, 시뮬레이션 유형의 문제는 모두 '구현 유형' 유형으로 묶을 수 있다. 둘 다구현이 핵심이 되는 경우가 많이 때문이다.

 

구현 문제와 관련된 예제문제를 몇가지 살펴보자.

 

문제 1

여행가 A는 NxN 크기의 정사각형 공간에 서 있고, 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다.
가장 왼쪽 위 좌표는 (1, 1)이고 가장 오른쪽 아래 좌표는 (N, N)이다.
상하좌우로 이동할 수 있으며, 시작 좌표는 (1,1)이다. 여행가는 계획서에 따라 움직이며 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있다.

 

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

 

만약 공간을 벗어나는 움직임이 있다면 그 움직임은 무시하고 다음으로 넘어간다.

 

입력 조건

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

출력 조건

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

입력 예시

5
R R R U D D

출력 예시

3 4

 

Solution

이 문제의 요구사항대로 구현하면 연산 횟수는 이동 횟수에 비례하게 된다. 예를 들어 이동 횟수가 N번인 경우 시간 복잡도는 O(N)이다.

이러한 문제는 일련의 명령에 따라 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로 분류되며 구현이 중요한 대표적인 문제 유형이다.

 

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

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)

 

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

 

출력 조건

00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다. 시간 제한은 2초, 메모리 제한은 128MB로 한다.

 

입력 예시

5

 

출력 예시

11475

 

Solution

이 문제는 모든 시각의 경우를 하나씩 모두 세서 쉽게 풀 수 있는 완전 탐색 유형의 문제이다.

단순히 시각을 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)