[이것이 취업을 위한 코딩 테스트다 with 파이썬] (한빛미디어, 나동빈) Chapter4. 구현

 포스팅 개요

 '혹시나 책에 있을 모든 실수와 오류는 온전히 제 책임이며, 책에 실린 좋은 아이디어와 표현은 모두 리뷰어님들의 조언 덕분입니다. 정말 고맙습니다.'라는 지은이의 글은 나동빈 저자님의 인품을 느낄 수 있는 한 줄이었습니다.

 

 저도 저런 마인드를 가진 사람이 되겠다고 다짐하며 책과의 여정을 떠나보겠습니다.

 

이것이 취업을 위한 코딩 테스트다

---

 포스팅 본문

  구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기는 어려운 문제를 칭합니다. 흔히 '피지컬을 요구하는' 문제라고 할 수 있습니다.

 

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

등이 있습니다. 사소한 조건 설정이 많은 문자일수록 코드로 구현하기가 까다롭습니다.

 이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다루고 있습니다.

 

• 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
• 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 수행하는 문제 유형

 저도 늘 코딩을 하다 보면 풀이법은 떠오르는 데 어떻게 써 내려가야 할지 모를 때가 많았습니다. 이번 Chapter가 많은 도움이 될 듯합니다.

 

 본 코드는 모두 제 Github에 올려두었습니다. (https://github.com/herjh0405/Coding_Test)

---

4-1. 상하좌우

 여행자 A는 N X N 크기의 정사각형 공간 위에 서 있다.
이 공간은 1 X 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행자 A는 상하좌우로만 이동할 수 있고, 시작은 항상 (1, 1)이다. 우리 앞에는 A의 이동 계획서가 놓여 있고, N X N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다.
 계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

n = int(input()) # n=5
plans = input().split() # plans = ['R', 'R', 'R', 'U', 'D', 'D'] 

x, y = 1, 1

# 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) # x=3, y=4

 

L, R, U, D로 이동하기 위해서 dx와 dy를 잡는 것이 이 문제의 핵심이다. 그 개념을 위한 간단한 예제였다. 

---

4-2. 시각

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

h = int(input()) # h=5

count = 0
for i in range(h+1):
    for j in range(60):
        for k in range(60):
            # 3이 포함된다면 count증가
            if '3' in str(i) + str(j) + str(k):
                count += 1
                
print(count) # count=11475

 완전 탐색이란 무엇인지 직관적으로 와 닿은 문제였다. 경우의 수가 크지 않기(100만 개 이하)에 이렇게 해결하는 것이 가장 적절한 방법이라 함.

---

4-3. 왕실의 나이트

 행복 왕국의 왕실 정원은 체스판과 같은 8 X 8 좌표 평면이다. 왕실 정원의 특별한 한 칸에 나이트가 서 있다.
나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다.
나이트의 위치가 주어졌을 떄 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오.
 이때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현한다.

# 현재 나이트의 위치 입력받기
loc = list(input()) # input = a1
to_num = ['a', 'b', 'c', 'd', 'e', 'f']

col = to_num.index(loc[0]) + 1
row = int(loc[1])

# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [
    (-2, -1), (-2, 1), (2, 1), (2, -1),
    (-1, -2), (-1, 2), (1, 2), (1, -2)
]

# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0 
for step in steps :
    next_row = row + step[1]
    next_col = col + step[0]
     
    # 해당 위치로 이동이 가능하다면 카운트 증가
    if next_row >=1 and next_row <=8 and next_col >=1 and next_col <= 8 :
        result += 1
        
print(result) # result = 2

  상하좌우 문제와 비슷하다. 경로를 확인해주는 과정이 꼼꼼하게 필요, (dx, dy)와 steps 모두 코딩 테스트에서 주로 쓰이는 형태로 알아두면 좋다고 함.

---

4-4. 게임 개발

 캐릭터가 있는 장소는 1 X 1 크기의 정사각형으로 이루어진 N X M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다. 맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다.

 캐릭터의 움직임은 아래처럼 설정 된다.

1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 갈 곳을 정한다.
2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 못한 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수없는 경우에는 움직임을 멈춘다.
   

 매뉴얼에 따라 캐릭터를 이동시킨 뒤에, 캐릭터가 방문한 칸의 수를 출력하시오.

 방향 d의 값은 다음과 같다. [0:북쪽, 1:동쪽, 2:남쪽, 3:서쪽]
 맵의 상태에서 0은 육지를, 1은 바다를 의미한다. 맵의 외곽은 항상 바다이고, 맨 처음 캐릭터가 위치한 곳은 항상 육지이다. 

# 맵 크기 설정
n, m = map(int, input().split()) # n=4, m=4
# 유저의 위치 설정
x, y, direction = map(int, input().split()) # x=1, y=1, direction=0
# 맵 생성 : list comprehension(2차원 리스트 선언 시 상당히 효율적)
d = [[0]*m for _ in range(n)]

# 서 있는 곳 표시
d[x][y] = 1
# 맵 정보 입력
array = []
# matrix = [[1,1,1,1], [1,0,0,1], [1,1,0,1], [1,1,1,1]]
for i in range(n):
    array.append(list(map(int, input().split())))
    
# 북, 동, 남, 서 방향 정의
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 왼쪽으로 회전하는 함수
def turn_left():
    global direction
    direction -= 1
    if direction == -1 :
        direction = 3
        
# 시물레이션 시작
count = 1 # 결과값
turn_time = 0 # 회전하는 횟수
while True :
    turn_left()
    nx = x + dx[direction]
    ny = y + dy[direction]
    # 육지이며 가본 적이 없는 지 체크
    if d[nx][ny]==0 and array[nx][ny] ==0 :
        d[nx][ny] = 1
        x = nx
        y = ny
        count += 1
        turn_time = 0
        continue
    else :
        turn_time += 1
    # 네 방향 모두 갈 수 없을 경우 
    if turn_time == 4 :
        nx = x - dx[direction]
        ny = y - dy[direction]
        if array[nx][ny] == 0 :
            x = nx
            y = ny
        else :
            break
        turn_time = 0
        
print(count) # count=3

 

나만의 풀이 연상법
1. 우선 방문을 한 장소와 바다/육지인 맵은 따로 분리하여 생성해두어야 한다. -> 3번 과정에 의해 방문한 곳이라 하더라도 다시 움직일 수 있으므로.
2. 뒤로 갈 수 없을 때까지 작동해야하기에 while문으로 처리한다.
3. 왼쪽 방향으로 계속 돌기에 turn_left 함수를 만들어준다.

4. 그 다음은, 문제 설정에 따라 진행

 

 전형적인 시뮬레이션 문제이다. 삼성전자 공채 코딩 테스트에서 자주 출제되는 대표적인 유형이라 한다.

 문제 풀이에 중요한 테크닉 : 방향을 설정해서 이동하는 문제이기에 dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것.

---

 이 책의 문제 구성에 감탄했습니다. 앞의 쉬운 예제로 테크닉들을 익히게 한 후 어려운 문제에서 응용을 시킵니다. 

 

 분명 코드를 보면 다 이해가 되는데, 아무것도 없이 던져진다면 쉽게 풀어낼 수 있을까 걱정이 듭니다. 숙달될 때까지 더 증진하겠습니다.!

 

Chapter5에서 뵙겠습니다. :)