구현 알고리즘

구현 알고리즘이란 무엇일까?

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 알고리즘 문제를 풀이할 때 구현은 매우 필요하다. 거의 모든 문제가 '구현 문제'인데 가끔 구현이 어렵거나 구현에 초점이 맞추어진 문제들이 있다. 즉, 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제라고 알고 있으면 된다.

예시

실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
적절한 라이브러리를 찾아서 사용해야 하는 문제
알고리즘은 간단한데, 코드가 지나칠 만큼 길어지는 문제
ex) 파싱, 해싱, 정렬, 시뮬레이션

구현하기 어려운 문제

까다로운 구현 유형의 문제

알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
특정 소수점 자리까지 출력해야 하는 문제
문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야 하는) 문제

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

(c / c++ 에서 변수의 표현 범위 : int, long long, BigInteger )
Python에서 리스트 크기
- 코딩 테스트의 메모리 제한에 대한 고려가 필요하다
- 리스트를 여러 개 선언하고, 그 중 크기가 1000만 이상인 리스트가 있는 경우 메모리 용량 제한에 걸릴 수 있다

구현 문제에 접근하는 방법

보통의 구현 문제는 사소한 입력 조건 등을 명시해주며 문제의 길이가 긴 편이다
문자열을 처리하거나 큰 정수를 처리하는 문제가 출제되는 경우가 많다

1. 상하좌우 (Simulation 유형)

여행가는 n * n 크기의 정사각형 공간 위에 서 있다.

이 공간은 1 * 1 크기의 정사각형으로 나누어져 있다.

가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (n, n)이다.

여행가는 상, 하, 좌, 우 방향으로 이동할 수 있으며 시작 좌표는 (1, 1)이다.

정사각형 공간을 벗어나는 움직임은 무시된다.

계획서가 주어졌을 때, 여행가가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하라.

이동 방향에 대해 미리 리스트로 정의하여 활용

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

2. 시각 (Brute-Force 유형)

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

입력 예시

출력 예시

11475

00시 00분 00초 ~ 23시 59분 59초까지의 모든 경우는 86,400가지 밖에 존재하지 않기 때문에 모든 경우를 다 세서 풀 수 있는 문제
시, 분, 초에 대한 3중 반복문을 이용

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)

예시