구현(Implementation)

코딩 테스트에서 구현(implementation)이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다
따라서, 모든 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 의미로도 볼 수 있다. 따라서, 구현을 하나의 '유형'이다..라고 보기에는 애매한 점이 있지만, 이러한 구현이 중심이 되는 문제들도 종종 출제되기 때문에 기초단계에서 다루고자 한다.

구현은 흔히 '피지컬'을 요하는 문제라고도 함...
즉, 사소한 조건 설정이 많은 문제일 수록 구현부분에 있어서 까다로운 문제라고 할 수 있고, 기본적인 언어의 문법과 method, library 사용에 익숙해지기 위해 많은 문제 풀이가 필요하다..!

구현의 유형

1) 완전탐색

모든 경우의 수를 주저없이 다 계산하는 해결 방법

2) 시뮬레이션

문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형

구현 알고리즘의 대표적 예시인 상하좌우 문제와 시각문제

상하좌우 문제

   
# N 입력받기
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)

일련의 명령에 따라 개체를 차례대로 이동시키는 시뮬레이션 유형

시각문제

# H를 입력받기
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)

N시 59분 59초까지의 3이 들어간 모든 시간, 가능한 모든 경우의 수를 검사해보는 완전 탐색 알고리즘

일반적으로, 탐색해야할 전체 데이터의 개수가 100만개 이하일때는 완전 탐색을 사용하면 적절함.