[이코테] 구현(Implementation)

📌구현이란?

구현(Implementation)이란 머릿속에서 구상한 알고리즘을 실제 소스코드로 옮기는 과정을 의미한다. 코딩테스트에서 ‘구현 문제’란 단순히 코드 작성 능력을 넘어 주어진 조건을 정확하게 해석하고 실수 없이 그대로 구현하는 능력을 평가하는 유형을 말한다.

✔️ 구현 문제 특징

구현 문제는 알고리즘자체는 쉽지만 코드로 옮기는 과정이 복잡한 경우가 많다.
고차원적인 알고리즘 지식이 필요한 편은 아니지만 아래와 같은 특징이 있다. 

• 조건이 많고
• 처리해야 할 경우의 수가 다양하며
• 인덱스나 시뮬레이션 과정에서 실수하기 쉽다

따라서 문법에 익숙하고 꼼꼼하게 코드를 짜는 능력이 있다면 비교적 수월하게 풀 수 있는 편이다.

✔️ 구현 문제의 예시

• 알고리즘은 간단하지만 코드 길이가 지나치게 길어지는 문제
• 문자열을 한 문자씩 잘라 리스트에 넣거나(파싱) 조건을 다수 체크해야 하는 문제
• 여러 단계의 움직임이나 규칙을 그대로 시뮬레이션해야 하는 문제
• 구현 문제의 대표 유형
  • 완전 탐색 : 모든 경우의 수를 빠짐없이 탐색하여 정답을 찾는 방식으로 특별한 최적화 없이 모든 조합을 시도해보는 것이 특징
  • 시뮬레이션 :문제에서 제시된 과정을 그대로 따라가며 단계별로 수행하는 방식으로 주어진 규칙을 코드로 옮겨 한 단계씩 실행하는 해결법

구현 문제는 알고리즘보다는 로직 구성 능력과 실수 없이 처리하는 꼼꼼함이 핵심이다.
 

---

📝예제> 시각 (완전탐색)

[문제]

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다. 

• 00시 00분 03초
• 00시 13분 00초

반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다.

• 00시 02분 55초
• 01시 27분 45초

[답안 예시]

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)

---

 

📝예제> 상하좌우 (시뮬레이션)

[문제]

여행가 A는 N x N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는(N x N)에 해당한다. 여행가 A는 상, 하,좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1,1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다. 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있다. 각 문자의 의미는 다음과 같다.

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

이때 여행가 A가 N x N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어(1,1)의 위치에서 L 혹은 U를 만나면 무시된다.

 
이 경우 6개의 명령에 따라서 여행가가 움직이게 되는 위치는 순서대로 (1, 2), (1, 3), (1, 4), (1, 4), (2, 4), (3, 4)이므로 최종적으로 여행가 A가 도착하게 되는 곳의 좌표는 (3, 4)이다. 
다시말해 3행 4열의 위치에 해당하므로 (3, 4)라고 적는다. 계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.
 

[답안 예시]

# 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)

🔴Reference

이것이 취업을 위한 코딩테스트다 with 파이썬 - 나동빈 저