구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
흔히 문제해결 분야에서 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미한다.
이 책에서는 완전탐색, 시뮬레이션 유형을 모두 '구현'유형으로 묶어 다루고 있다.
- 완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결방법
- 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계식 차례대로 직접수행해야하는 문제 유형
고차원적인 사고력을 요구하는 문제가 나오지 않는 편아라 문법에 익숙하면 오히려 쉽게 풀수 있다. ex) itertools
예제 4-1) 상하좌우
NxN 정사각형 공간, 1x1크기의 정사각형으로 나누어져있다.
가장 왼쪽 위 좌표는 (1,1)이고, 가장 오른쪽 아래 좌표는 (N,N)이다.
L,R,U,D은 이동방향이고, 각 한 칸식 이동한다.
이때, NxN크기의 정사각형 공간을 벗아나는 움직임은 전부 무시한다.
입력예시)
5
R R R U D D
출력예시)
3 4
예제 4-1) 답안
x,y = 1,1
#R R R U D D
N = int(input())
plans = input().split()
#RUDL
dx=[1,0,0,-1]
dy=[0,-1,1,0]
direction = ['R','U','D','L']
for plan in plans:
for i in range(len(direction)):
if plan == direction[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
# x : column, y : row
print(y, x)예제 4-2) 시각
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하라.
예제 4-2) 답안
N = int(input())
count = 0
# 경우의 수 : N+1, 60, 60
for i in range(N+1):
for j in range(60):
for k in range(60):
if '3' in str(i)+str(j)+str(k):
count += 1
print(count)이러한 유형을 완전탐색 유형으로 분류한다. 탐색 해야할 전체 데이터 개수가 100만개 이하일때 완전탐색을 사용하면 적절하다.
문제 2) 왕실의 나이트
왕국 정원은 8x8 좌표 평면이다. 왕실 정원 특정 한 칸에 나이트가 서 있다.
이동할 때는 L자 형태로만 이동할 수 있고, 정원 밖으로는 나갈 수 없다.
1. 수평으로 두 칸, 수직으로 한 칸
2. 수직으로 두 칸, 수평으로 한 칸
나이트의 위치가 정해졌을때, 나이트가 이동할 수 있는 경우의 수를 출력하라.
행은 1~8, 열은 a~h로 표현한다.
입력예시) a2
출력예시) 2
문제 2) 답안 ( 나의 풀이 )
N = 8
columns = ['a','b','c','d','e','f','g','h']
# col = a, row = 1
data = input()
y = columns.index(data[0]) + 1
x = int(data[1])
# 이동 경우의수 : 8가지
# 1 -> 2 순서, RL, DU
dx = [1,-1,1,-1,2,2,-2,-2]
dy = [2,2,-2,-2,1,-1,1,-1]
count = 0
for i in range(N):
nx = x + dx[i]
ny = y + dy[i]
if ( nx > N or ny> N or nx < 1 or ny < 1 ): continue;
else: count += 1
print(count)문제 2) 답안 (교재 풀이)
N = 8
data = input()
# ord 함수 : 유니코드 정수 반환
y = int(ord(data[0])) - int(ord('a')) + 1
x = int(data[1])
steps = [(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)]
count = 0
for step in steps:
nx = x + step[0]
ny = y + step[1]
if ( nx <= N and nx >= 1 and ny >= 1 and ny <= N ): count += 1;
print(count)문제 3) 게임 개발
1x1들로 이루어진 N x M 크기의 직사각형 맵이 있다.
각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.
맵의 각 칸은 (A,B)로 나타낼 수 있고, 시작점은 가장 왼쪽 맨위로 (0,0)이다.
캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다.
- 왼쪽방향(반시계방향 90도 회전)부터 차례대로 갈 곳을 정한다.
- 왼쪽방향에 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면 왼쪽방향으로 회전만 수행하고 다시 1번으로 돌아간다.
- 만약 네방향 모두 이미 가본 칸이거나 바다로 되어있는 경우에는 바라보는 방향을 유지한 채 한칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우는 움직임을 멈춘다.
캐릭터가 방문한 칸의 수를 출력하라.
입력첫째줄 (N,M) , 3<=N, M<=50
입력둘째줄 (y x) 방향 , 0:N, 1:E, 2:S, 3:W
그 외 0: 육지 , 1: 바다
*** 처음에 게임 캐릭터가 위차한 칸의 상태는 항상 육지이다.
문제 3) 답안
N, M = map(int,input().split())
x, y, dir = map(int,input().split())
# 방문 확인용 배열. 전부 방문하지 않았음(=0)으로 초기화.
d = [[0] * M for _ in range(N)]
d[x][y] = 1
# 맵
rows = []
for i in range(N):
rows.append(list(map(int,input().split())))
# 방향 ( NESW )
dy = [0,1,0,-1]
dx = [-1,0,1,0]
# 반시계방향 회전
def turn_left():
global dir
dir -= 1
if dir == -1:
dir = 3
# 최초의 위치 : 육지
count = 1;
# 방향 회전 횟수
turn_time = 0;
while True:
# 반시계회전
turn_left();
ny = y + dy[dir]
nx = x + dx[dir]
# 맵이 바다인경우 동시에 방문하지 않았던 맵
if( rows[nx][ny] == 0 and d[nx][ny] == 0):
count += 1
y = ny
x = nx
d[nx][ny] = 1
turn_time = 0
continue;
else:
turn_time += 1
# 모든 방향이 가본칸이거나 바다인경우
if turn_time == 4:
# 뒤로 한 칸 이동
ny = y - dy[dir]
nx = x - dx[dir]
# 육지인 경우
if rows[nx][ny] == 0:
x = nx
y = ny
# 바다인 경우
else:
break
# 새로운 위치에서 방향탐색을 해야하므로 0으로 초기화
turn_time = 0
print(count)