구현(Implementation)이란?

이것이 코딩 테스트다 with 파이썬 - Ch. 4 구현을 공부하고 기록했습니다.

구현(Implementation) 이란?

- 특정 알고리즘을 의미하는 것이 아니라 머릿속에 있는 알고리즘을 소스코드로 바꾸는 문제 유형을 의미한다.

 

요즘 많은 기업들이 코딩테스트 문제 유형으로 구현을 많이 내는 트렌드라 구현 문제들을 몇 번 풀어봤는데, 이게 뭔 문제인가 싶었다. 늘 그렇듯 어떤 알고리즘 유형이고 어떻게 풀어야할까 고민했지만 못 풀었었다.

 

구현 문제는 해결책을 떠올리는 것은 어렵지 않지만 정확히 구현하는 것이 어렵다. 사용하는 언어의 정확한 문법과 라이브러리 등을 활용해 구현하는 것이 실력으로 결국 많은 문제를 풀어보면서 실력을 키우는 것이 중요하다.

 

구현 문제에서 고려해야할 것 중 하나는 메모리 용량이다. 파이썬은 int 자료형을 자동으로 조절해주기에 값의 크기를 걱정할 필요는 없지만 실수 자료형은 고려해야한다. 또한, 리스트의 길이가 약 1,000만 이상이라면 메모리 초과로 인해 문제를 해결할 수 없다는 것을 알고 조심해야한다.

 

실전 문제 1. 왕실의 나이트

목표 : 8 X 8 체스판에서 나이트의 이동 가능한 경로 갯수를 찾는다.

특징 : 나이트는 수평, 수직 2칸 이동후 상하, 좌우로 이동 가능

입력 조건 : a1(열은 알파벳, 행은 숫자로 표현)

 

Sol ) 이동가능한 방향은 2칸 이동하는 방향(4개) * 상하 or 좌우(2)개로 총 8가지 경우의 수이다. 이 8가지 경우의 수 중 체스판을 넘어가거나 이동할 수 없는 경우들을 확인하면 되는 문제이다.

 

import sys
input = sys.stdin.readline

place = input()
row = int(place[1])
# ord 함수는 해당 문자에 대한 유니코드 정수를 반환하는 함수
col = int(ord(place[0]) - ord('a')) + 1  # a는 1, 그 이후 알파벳은 1씩 증가


dir = [(-2, 1), (-2, -1), (2, 1), (2, -1), (-1, -2), (1, -2), (-1, 2), (1, 2)]
count = 0

for x, y in dir:
    nx = row + x
    ny = col + y
    if 1 <= nx <= 8 and 1 <= ny <= 8:
        count += 1
        
print(count)

 

 

실전 문제 2. 게임 개발

목표 : N X M 맵에서 상하좌우로 이동하며 특정 조건에 맞춰 방문할 수 있는 육지의  수를 찾는다.

특징 :

1. 왼쪽으로 회전하며 이동 가능한 육지인 경우 해당 방향을 유지한채 1칸 이동, 이동 불가시 왼쪽으로 회전

2. 네 방향 전부 방문했거나 바다인 경우 => 방향 유지한채로 뒤로 1칸 이동

2- 1. 뒤로 이동할 수 없는 경우 모든 과정을 멈추고 방문한 육지 갯수 출력

 

입력 : N, M(3 <= N, M <= 50), d (0, 1, 2, 3, 북, 동, 남, 서 순서), 맵의 정보 (0은 육지, 1은 바다)

 

Sol ) 왼쪽 회전방향을 기반으로 반복문을 돌려 조건들을 따져가며 이동하면 되는 구현 문제다. 복잡한 내용은 없지만 질문을 이해하는 것과 코드로 구현하는 것이 관건이었다. BFS 문제를 풀 때처럼 방향을 설정하는 리스트(dx, dy)를 선언하는 방법으로 보는 방향을 설정했고 그 이외에는 반복문내에서 모든 조건을 처리하는 식으로 구현했다.

 

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
x, y, dir = map(int,input().split())

map = [list(map(int, input().split())) for _ in range(N)]

dx = [-1, 0, 1, 0] # 북 동 남 서 방향
dy = [0, 1, 0, -1]
curdir = dir
count = 1 # 방문한 영토의 갯수
map[x][y] = 1  # 시작점 방문 처리

def turnleft():   # 복 서 남 동 방향으로 왼쪽 방향 회전 함수
    global curdir
    # 0 1 2 3
    if curdir == 0:
        return 3
    else:
        return curdir - 1


while True:
    back = False  # 뒤로 이동 여부 기록용 변수
    for i in range(4):
        curdir = turnleft()
        nx = x + dx[curdir]
        ny = y + dy[curdir]
        if 0 <= nx < N and 0 <= ny < M:
            if map[nx][ny] == 0: # 방문 안한 육지일때,
                x = nx
                y = ny
                map[nx][ny] = 1
                count += 1
                back = True
    if not back:  # 4방향 확인 이후 뒤로 가야하는 경우
        nx = x - dx[curdir]
        ny = y - dy[curdir]
        if 0 <= nx < N and 0 <= ny < M and map[nx][ny] != 1: # 바로 뒤가 육지인 경우
            x = nx
            y = ny
            map[x][y] = 1
            count += 1
        else:  # 뒤로 이동할 수 없는 경우 반복문 완료
            break
        
        

print(count)