구현
(implementation)이란 머리속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.
어떤 문제를 풀건, 필수적인 과정이므로 모든 문제의 유형을 포함하는 개념이다.
문법을 정확하게 숙지하고 라이브러리 사용 경험을 기르는 등의 선행이 필요하다.
구현 유형 중, 완전 탐색과 시뮬레이션 유형을 풀어본다.
완전탐색
모든 경우의 수를 다 계산하는 해결방법이다.
때문에, 시간 복잡도를 생각해야 하는데 전체 데이터의 개수가 100만개 이하일때 적절하다.
(파이썬의 경우)
연습문제
시각
정수 N이 입력되면, 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중,
3이 하나라도 포함되는 경우의 수를 구하라
해설
모든 경우의 수를 세서 풀 수 있다.
최대 경우가 하루 86,400가지 이므로 완전탐색에 적합하다.
단순히 시각을 증가시키며 모든 시각에 대해 3이 있는지 판단한다.
def solution(n):
count = 0
for hour in range(n+1):
for min in range(60):
for sec in range(60):
if '3' in str(hour) + str(min) + str(sec):
count += 1
return count시뮬레이션
문제에서 제시한 알고리즘을 한단계씩 차례로 직접 수행한다.
별도의 알고리즘이 필요하기보다 문제에서 요구하는 내용을 오류없이 구현할 수 있다면 된다.
다만, 문제가 길고 바르게 이해하여 소스코드로 옮기는 과정이 어렵기에, 반복적인 숙달이 필요하다.
연습문제
게임 개발
캐릭터는 N X M으로 이루어진 직사각형 칸 중 한 곳에 있으며, 동서남북 중 한 곳을 바라본다.
맵의 각 칸은 (A,B) A는 북쪽에서 떨어진 칸의 개수, B는 서쪽에서 떨어진 칸의 개수이다.
- 캐릭터는 현재 위치에서 현재 방향을 기준으로, 왼쪽부터 갈 곳을 정한다.
- 왼쪽 방향에 가보지 않은 칸이 존재하면, 회전 후 이동한다. 없다면 회전만 수행하고 1단계로 돌아간다.
- 만약, 네 방향 모두 가본 칸이거나, 바다로 되있다면, 바라보는 방향을 유지하고 한칸 뒤로 가고 1단계로 돌아간다. 이때, 뒤쪽 방향이 바다라면 움직임을 멈춘다.
바라보는 방향은 (0 - 북, 1 - 동, 2 - 남, 3 - 서)로 주어지며,
맵에 대한 정보는 (0 - 육지, 1 - 바다)로 주어진다. 맵의 외각은 항상 바다이다.
해설
방향을 설정해서 이동하는 문제는 dx,dy라는 별도의 리스트를 만들어 방향을 정하면 효과적이다.
북쪽의 방향이 0이기 때문에 dx[0] = 0, dy[0] = -1로 설정하여, 방향을 이동한다.
이미 방문한 위치에 대한 정보가 필요하기 때문에, 2차원 배열을 만든다.
python의 2차원 배열은 '컴프리핸션'을 사용하여 초기화한다.
왼쪽 방향으로 갈 수 있는지 확인이 끝나도, 갈 곳을 못 찾았다면, 더 이상 갈 곳이 없으므로 뒤로 돌아간다.
모두 확인했는지 알 수 있는 변수를 설정한다.
뒤로 돌아가는 구현은 현재 방향의 이동을 빼주면 된다.
def solution(n,m,character,maps):
x,y,direction = character;
d = [[0]*m for _ in range(n)]
d[y][x] = 1
# 북, 동, 남, 서
dy = [-1,0,1,0]
dx = [0,1,0,-1]
count = 1
turn_count = 0
while True:
direction -= 1
if direction < 0: direction = 3
ny = y+dy[direction]
nx = x+dx[direction]
if(d[ny][nx]==0 and maps[ny][nx]==0):
y,x = ny,nx
d[y][x] = 1
turn_count = 0
count += 1
else:
turn_count += 1
if turn_count == 4:
ny = y-dy[direction]
nx = x-dx[direction]
if (maps[ny][nx]==0):
y,x = ny,nx
turn_count = 0
else:
break
return count
