구현

구현이란 '머리속에 있는 알고리즘을 소스코드로 바꾸는 과정' 이다. 

즉, 1) 문제를 보고 2) 풀이를 떠올리고, 3) 소스코드로 옮겨야 한다. 

즉, 마치 게임에서 손 빠른 사람을 '피지컬'이 좋다고 하듯이, 구현 유형 문제는 소스 코드로 구현을 하는 코딩 '피지컬'을 요구한다고 볼 수 도 있다. 

 

소스코드로 옮기는 과정이 원할하기 위해서는 기본적으로 다음의 능력이 필요하다. 

1) 충분한 라이브러리 사용 경험 

2) 충분한 문법 숙지 

 

완전 탐색과 시뮬레이션은 구현에 포함한다고 가정하였다. 

때로 기업 공채에서는 웹 서버나 데이터 분석 기초 지식이 필요하기도 하다. 

 

몇개의 구현 알고리즘을 풀어보자. 

 

1) 상하좌우 

N X N 정사각형의 한 블럭(1 X 1)위에 여행가가 서 있다. 가장 왼쪽  (1,1) 가장 오른쪽 하단을 (N,N)이라 하고 여행가는 (1,1)에서 시작하여 상하좌우(U,D,L,R)로 이동할 수 있다. 주어진 여행 계획서에 따라 이동하자. 

N X N 정사각형 크기를 벗어나는 움직임은 무시 된다. 최종 도착 지점을 찾아라. 

 

import sys 
input = sys.stdin.readline

N = int(input())
lst = input().split()

x,y = 1,1 
direction = {'L': [0, -1], 'R': [0, 1], 'U': [-1,0], 'D': [1,0]}

for c in lst:
    dx, dy = direction[c]
    if x + dx < 1 or y + dy < 1 or x + dx > 5 or y + dy > 5:
        continue
    else:
        x += dx 
        y += dy

print(x, y)

 

2) 시각 

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

 

import sys 
input = sys.stdin.readline

N = int(input())

def one_hour(n):
    cnt = 0
    m = 0 
    for i in range(60):
        s = 0
        for j in range(60):
            if '3' in str(100 * m + s):
                cnt += 1 
            s += 1 
        m += 1
    cnt *= n 
    return cnt 

if N < 3:
    print(one_hour(N+1))
else:
    print(one_hour(N) + 60*60)

3시를 제외하고는 반복이기에 00시 00분 00초부터 00시 59분 59초까지 구한 값에 N 배해주면 되고, 3시인 경우에만 계속 3이 포함되므로 개수가 60 * 60 이다. 

 

00시 00분 00초 부터 23시 59분 59초까지 경우의 수가 86,400 개밖에 안되므로 그냥 3중 for 문으로 작성해도 별 문제는 없다. 

그리고 나처럼 수를 수로 보고 더하지 않고 

for i in range(60):
	for j in range(60):
    	if '3' in str(i) + str(j):
        	cnt +=1

str 처리해서 더해도 순서가 유지됨을 기억하자. 

 

3) 왕실의 나이트 

8 X 8 좌표 평면이 주어졌다. 특정 한 칸에 나이트가 서 있다. 나이트는 좌표 평면 밖으로는 나갈 수 없다. 

나이트 위치가 주어졌을 때, 나이트가 이동할 수 있는 경우의 수를 출력하자. 

행은 1 ~ 8, 열은 a ~ h 이다. 

 

import sys 
input = sys.stdin.readline

tmp = input()
column, row = tmp[0], int(tmp[1])

column = ord(column) - 96 

knight = [[2,1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2]]

cnt = 0

for dx, dy in knight:
    if column + dx < 1 or column + dx > 8 or row + dy < 1 or row + dy > 8:
        continue
    else: 
        cnt +=1 

print(cnt)

 

ord(column) - 96 의 경우 ord('a')값이 기억이 나지 않을 수 있다. 

이를 위해 

column = ord('column') - ord('a') + 1

으로 하면 더 쉽게 기억 할 수 있다. 

list of list 로 하지말고 sets in list 로 하자. 

 

4) 게임 개발 

맵은 N X M (육지와 바다 존재), 캐릭터는 1 X 1 크기를 차지한다. 맵의 각 칸은 (A, B)로 나타낸다. 왼쪽 상단이 (0,0) 이다. 

캐릭터는 상하좌우로 움직일 수 있고, 바다 공간은 갈 수 없다. 다음의 메뉴얼을 따른다.

 

1) 현재 위치, 방향 기준 왼쪽 방향 부터 차례대로 갈 곳을 정한다. 

2) 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸 존재시, 왼쪽 방향으로 회전 후 왼쪽으로 한칸 전진한다. 왼쪽 방향에 가보지 않은 칸이 없으면 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다. 

3) 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 경우, 바라보는 방향을 유지한 채 한칸 뒤로 가고 1단계로 돌아간다. 만약 뒤쪽 방향이 바다라면 움직임을 멈춘다. 

(바다 1 육지 0)

캐릭터가 방문한 칸의 수를 구하여라. 

import sys 
input = sys.stdin.readline

row, column = map(int, input().split())

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

map_ = []
for i in range(row): 
    map_.append( list(map(int, input().split())) )

change = {0: 3, 1: 0, 2: 1, 3: 2}

go = {0 : (-1, 0), 1: (0, 1), 2: (1, 0), 3: (0, -1)}

visited= [[0]*5 for i in range(5)]
visited[y][x] = 1 
print("visited", visited)
#visited = [[0] * column] * row  이거 절대 안됨 


while(True):
    for i in range(4):
        dir = change[dir]
        dy, dx = go[dir]
        if dx + x < 0 or dy + y < 0 or dx + x > column or dy + y > row:
            continue
        elif map_[dy+y][dx+x] == 1:
            continue
        else:
            if visited[y+dy][x+dx] == 0:
                x += dx
                y += dy
                visited[y][x] = 1 
                print("visited: ", visited)

            else: 
                continue
            break
    else:
        #4번의 시도를 실패한 경우 바라보는 방향의 뒤로 가기 
        dy, dx =  go[dir]
        x -= dx 
        y -= dy 
        if map_[y][x] == 1: #뒤로 돌아 간 곳이 바다면 stop 
            break 
        visited[y][x] = 1  # 처음부터 뒤로 가는 경우에는 방문하지 않았을 수도 있다. 
        print("visited: ", visited)

    
print(sum([sum(i) for i in visited]))
#sum(map(sum, visited))

 

정답과 비교했을 때 유의점 

 

1. 왼쪽으로 회전을 나의 경우 dictionary 로 정의했는데 잘 살펴보면 사실상 방향의 value 가 1씩 낮아지다가 -1 될 때 3이 된다. 

def turn_left():
    direction -= 1 
    if direction == -1:
        direction = 3

위와 같이 처리해도 된다. 하지만 이 경우 dictionary 가 좀 나았던 것으로 보인다. 

 

동서남북 방향 정의를 내 경우 

특정 방향일 때 한번에 가독성이 좋도록 dictionary 를 사용했다. 

go = {0 : (-1, 0), 1: (0, 1), 2: (1, 0), 3: (0, -1)}

반면 정답은 아래와 같이 처리했다. 

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

사실상 완전 같지만, 아래처럼 처리하는 것도 눈에 익혀야겠다. 

 

내 경우 4번 돌다가, 앞으로 전진이 가능한 경우 break 로 빠져나오고 못 빠져나온 경우 for 문의 else 로 들어가도록 처리했다. 

 

하지만, 정답의 경우 turn_time 이라는 변수를 하나 놓고 turn_time 이 4가 될 때 까지 돌면서 전진 가능한지 확인하도록 했다. 

사실상 같은 방식이지만, 개인적으로는 내 방식이 가독성이 좀더 높다고 생각한다. 다만 정답 방식이구현시 실수가 더 적을 것 같다. 

 

그리고 정답은 count 를 직접했다. 해당 방법의 발생 가능한 문제는 시작 지점에서 갈 수 있는 곳이 없어 뒤로 갈 경우, 도착 지점이 방문 한적이 없을 때 count 를 +1 해줄 수 없다는 단점이 있다. 이 경우 count 를 사용한다면 manual 하게 뒤로 돌아 도착한 곳도 방문 한적이 있나 확인해주고 더해주면 되긴하다. 

memory 면에서 count 를 사용하는 것이 더 효율적으로 보인다. 

 

※ 실수하기 좋은 것 

visited = [[0] * 5 for i in range(4)]

[[0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0]]

 

visited = [[0]* 5] * 4

[[0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0]]

 

둘의 출력결과는 같으나 이는 대 참사를 불러일으킬 수 있다 .

아래의 visited = [[0]*5] * 4 는 

[0,0,0,0,0] 를 5번 깊은 복사하여 한 list의 element 를 수정할시 각 list 마다 모두 반영이 된다.