구현 알고리즘

본문은 저자 나동빈님의 『이것이 취업을 위한 코딩테스트다 with 파이썬』 책을 공부하며 작성한 내용입니다. 글은 편의상 반말로 작성되었습니다.

최초 작성일 : 20.02.03
최종 수정일 : 20.02.04

개념

구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정으로, 구현 알고리즘이 따로 있다기보다 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다. 하지만 알고리즘은 간단하나 코드가 지나치게 길어지는 문제, 특정 소수점 자리까지 출력하는 문제, 문자열을 입력 받으면 한 문자 단위로 리스트에 넣어야 하는 문제 등은 까다로운 구현 유형의 문제라고 볼 수 있다.

특성

- 사용하는 언어의 문법을 잘 알아야 한다.

- 라이브러리 사용 경험이 많아야 한다.

- 이 책에서는 완전 탐색, 시뮬레이션 문제를 구현 유형으로 묶어 다룬다.

- 파이썬에서 리스트를 이용할 때는 메모리 제한을 신경쓰도록 하자.

예제

1. 상하좌우

작성 코드

import sys

# 맵의 크기와 이동할 계획을 입력받는다.
N = int(sys.stdin.readline())
movement = list(sys.stdin.readline().strip().split())
# 현재 위치는 (1, 1)
current_x = current_y = 1

# 이동 계획에 맞게 현재 위치를 계산해간다.
for direction in movement:
    if direction == "R":
        if current_y == N:
            continue
        current_y += 1
    elif direction == "L":
        if current_y == 1:
            continue
        current_y -= 1
    elif direction == "D":
        if current_x == N:
            continue
        current_x += 1
    elif direction == "U":
        if current_x == 1:
            continue
        current_x -= 1
print(current_x, current_y)

• 맵을 이중 리스트로 작성해야 하나 생각했다가, 굳이 리스트가 없어도 어렵지 않게 풀 수 있을 것 같아서 위와 같이 풀이
• 대신 코드가 좋아 보이지는 않음. 반복되는 것들을 합칠 수 있는 방법이 있을텐데 어떻게 해야할 지 잘 모르겠음

답안 예시

# 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_type = ['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)

• 대충 흐름은 이해가 되는 것 같은데 정확히 코드 한줄 한줄이 의미하는 바를 전부 이해하지는 못했다. 진도 나가다가 다시 돌아와서 보면 이해되는 부분이 있겠지. 일단 패스 

피드백

1. for문에서 range(len())을 사용하면 길이에 따라 반복할 수 있음
2. 좌표를 먼저 구하고, 범위가 벗어나지 않았을 때만 이동하도록 수행

2. 시각

작성 코드

• 코드 작성 실패. 이걸 하나하나 다 계산해야 하나? 하다가 나름 분, 초는 개수(1분간 0부터 59까지 15개)가 정해져 있으니 시간에 따라 결과물만 나오면 되겠다 싶었는데 구현할 수가 없었다.

답안 예시

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

• 답안 예시처럼 생각을 했었는데 (000000으로 만드는 것) 3중 반복문을 사용할 생각을 못했다. 분, 초 60이 될 때마다 0부터 다시 시작해야 하는데 어떻게 해야하는지 바로 생각이 떠오르지 않았다.
• 탐색해야 할 전체 데이터 수가 100만개 이하일 때 완전 탐색 사용

3. 왕실의 나이트

작성 코드

• 코드 작성 실패. 방향에 대해서도 답안 예시처럼 정의하지 않고 일일이 반복문으로 구해서 사용하려고 했더니 너무 복잡해져서 작성하지 못했다. 간단하게 생각하는 법을 익혀야겠다.

답안 예시

# 현재 나이트의 위치 입력받기
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

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

# 8가지 방향에 대해 각 위치로 이동이 가능한지 확인
result = 0
for step in steps:
    # 이동하고자 하는 위치 확인
    next_row = row + step[0]
    next_column = column + step[1]
    # 해당 위치로 이동이 가능하다면 카운트 증가
    if 1 <= next_row <= 8 and 1 <= next_column <= 8:
        result += 1

print(result)

• 이동할 방향을 steps에 정의해두고 for문으로 하나씩 접근하여 계산
  (1번 상하좌우 문제에서는 dx, dy로 정의해뒀던 부분. 그 두가지 형태 모두 자주 사용됨)
• 문자의 아스키 코드 값을 반환해주는 내장함수 ord()를 사용
  (입력받은 문자의 아스키 코드 값 - 문자 a 아스키 코드값 + 1 = 입력받은 문자의 순서. a는 1, b는 2 이런 식)

4. 게임 개발

작성 코드

N, M = map(int, input().split())
x, y, d = map(int, input().split())
count = 1 # 움직인 맵의 수
loopCnt = 0 # 다음으로 전진하지 못할 경우, 왼쪽 방향으로 돌면서 1회씩 증가하고 
            # 4가 되면 갈 곳이 없다는 뜻으로 게임이 종료 
gameMap = []
direction = [0, 1, 2, 3]
movement = [[-1, 0], [0, 1], [1, 0], [0, -1]] # 0, 1, 2, 3 방향으로 전진할 때 위치값
currentPosition = [x, y]
nextPosition = []

# 변수 gameMap에 현재 맵 저장
for i in range(N):
    gameMap.append(list(input().split()))

while 1:
    # 다음 위치를 저장 (현재 위치에서 이동할 위치를 더해서 계산)
    nextPosition = [currentPosition[0] + movement[d - 1][0], currentPosition[1] + movement[d - 1][1]]
    # 다음 위치 값이 0일 경우 (전진 가능)
    # 왼쪽으로 한 칸 전진하고 count 1 상승, 현재 위치 값 1로 변경
    if gameMap[nextPosition[0]][nextPosition[1]] == '0':
        d = direction[d - 1]
        currentPosition = nextPosition
        count += 1
        loopCnt = 0
        gameMap[currentPosition[0]][currentPosition[1]] = 1
    # 다음 위치 값이 1일 경우 (전진 불가능)
    # 왼쪽 방향으로 회전하고 loopCnt 1 상승
    else:
        if loopCnt == 4:
            break
        d = direction[d - 1]
        loopCnt += 1

print(count)

• 마지막 조건 하나를 이해를 못해서 못 넣었다. 아무리 고민해봐도 말이 좀 이상한 것 같은데..
  조건 : 네 방향 모두 전진이 불가능할 경우, 바라보는 방향을 유지한 채 한 칸 뒤로 가고 1단계로 돌아간다. 뒤로 갈 수 없는 경우 움직임을 멈춘다 -> 네 방향 모두 전진이 불가능하다는 것은 곧 뒤로 갈 수도 없다는 말과 같은 말 아닌가? 이상하네..
• 현재 자리에서 동서남북 모든 방향으로 전진이 불가능할 경우(loopCnt == 4) 게임 종료하도록
• 방향과 위치값을 list에 입력해두고, 필요한 것을 꺼내 사용

답안 예시

# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

# 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
d = [[0] * m for _ in range(n)]
# 현재 캐릭터의 X 좌표, Y 좌표, 방향을 입력받기
x, y, direction = map(int, input().split())
d[x][y] = 1 # 현재 좌표 방문 처리

# 전체 맵 정보를 입력받기
array = []
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)

• 방향 회전하는 코드를 함수로 따로 선언
• x, y를 나누어 방향 정의하고 계산 (더 정리되어 보임)
• [기초] 함수 밖에서 선언된 전역 변수를 함수 내에서 사용할 때는 global 붙여서 사용

피드백

1. 코드가 여러가지 기능으로 너무 길어질 때는 함수를 선언하여 사용해보자.
2. 변수명을 간단하게 지으면 코드가 좀 더 간단해 보인다.