구현이란?
머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정.
'이것이 코딩테스트다'에서는 완전 탐색, 시뮬레이션을 구현이라고 봄.
- 완전 탐색 : 모든 경우의 수를 다 계산
- 시뮬레이션: 문제에서 제시한 알고리즘을 차례로 직접 수행
파이썬으로 제출한 코드가 1초에 2000만번의 연산을 수행한다고 가정하면 메모리와 시간에는 크게 무리가 없음을 기억.
예제 4-1 [p.110]
문제
여행가 A는 nxn 크기의 정사각형 공간 위에 서 있다. 이 공간은 1x1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N,N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다. 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다. 각 문자의 의미는 다음과 같다.
L : 왼쪽으로 한 칸 이동
R: 오른쪽으로 한 칸 이동
U: 위로 한 칸 이동
D: 아래로 한 칸 이동
how to solve
- 공간 크기 n 입력 받음.
- 이동할 계획서 list로 내용 받음.
- 여행가 a의 현재 위치 x=1, y=1로 초기화.
- L인 경우 y-1
- R인 경우 y+1
- U인 경우 x-1
- D인 경우 x+1
- for문으로 list에서 계획서 내용 하나하나 꺼낸 뒤 if 문으로 검사. (파이썬에는 switch문이 없음. )
- 만약 x, y가 1보다 작거나 공간의 크기보다 크면 continue로 계획서 내용 무시.
- L인 경우에는 y가 1보다 작은지만 검사.
- R인 경우에는 y가 n보다 큰지만 검사.
- U인 경우에는 x가 1보다 작은지만 검사.
- D인 경우에는 x가 n보다 큰지만 검사.
# 공간 크기 입력
a= int(input())
# 이동 계획서 입력
move=list(input().split())
# 여행가 위치 초기화
x=1
y=1
## 리스트에서 하나하나 꺼내기
for i in move:
if(i =='L'):
if(y<=1):
continue
y=y-1
elif(i =='R'):
if(y>=a):
continue
y=y+1
elif(i =='U'):
if(x<=1):
continue
x=x-1
elif(i =='D'):
if(x>=a):
continue
x=x+1
print(x, y)
왕실의 나이트 [p.115]
문제
행복 왕국의 왕실 정원은 체스판과 같은 8x8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다...?(ㅋ ㅋ..)
나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.
1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기
이 처럼 8x8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 이때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현한다.
how to solve
- 현재 나이트가 위치한 곳의 좌표를 나타내는 문자열 입력받기.
- 위에서 입력받은 문자열[0]과 ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'] 리스트에서 같은 문자 찾아서 인덱스 +1 => 열을 숫자화하기.
- 행, 열 모두 int로 각각의 변수에 저장.
- 수평 2칸, 수직 1칸 / 수직 2칸, 수평 1칸 => 나올 수 있는 경우의 수 총 8개
- 오른쪽 2칸 위 아래, 왼쪽 2칸 위 아래, 위 2칸 오른쪽 왼쪽, 아래 2칸 오른쪽 왼쪽.
- 각각의 경우를 계산하여 colNum과 rowNum이 1과 8을 넘어가지 않는 경우만 count +=1.
# 현재 나이트가 위치한 곳의 좌표를 나타내는 문자열 입력
location=input()
# 행렬 숫자화
col= ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
colNum=col.index(location[0])+1
rowNum=int(location[1])
count =0
# 수평 2칸 수직 1칸
if(colNum+2<=8 and rowNum+1<=8):
count+=1
if(colNum+2<=8 and 1<=rowNum-1):
count+=1
if(1<=colNum-2 and rowNum+1<=8):
count+=1
if(1<=colNum-2 and 1<=rowNum-1):
count+=1
# 수직 2칸 수평 1칸
if(rowNum+2<=8 and colNum+1<=8):
count+=1
if(rowNum+2<=8 and 1<=colNum-1):
count+=1
if(1<=rowNum-2 and colNum+1<=8):
count+=1
if(1<=rowNum-2 and 1<=colNum-1):
count+=1
print(count)
개선점: 방향 이동 가능한 8가지 방법을 리스트에 넣어주고 for문에서 하나씩 꺼내서 계산하면 훨씬 더 깔끔하게 구현 가능..
게임 개발 [p.118]
문제
캐릭터가 있는 장소는 1x1 크기의 정사각형으로 이뤄진 nxm 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.
맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어있는 공간에는 갈 수 없다.
1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 갈 곳을 정한다.
2. 캐릭터의 바로 왼쪽 방향에 가직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
3. 만약 네 방향 모두 가본 칸이거나 바다로 되어있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.
how to solve
- 궁금한 점: 위치는 0, 0부터 시작해서 n-1, m-1인건가요? (일단 저는 이렇게 두고 풀었습니다. )
- dx, dy를 이용해서 풀 것.
- 맵에서 방문한 곳은 2로 표시. => 마지막에 반복문을 돌려서 맵에서 2인 장소만 세어주어 방문한 칸의 수를 출력할 것.
- 맵은 받아서 2차원 리스트에 저장.
- 현재 위치와 현재 방향은 x, y, d에 저장.
- 캐릭터가 왼쪽으로 회전하므로 dx, dy는 북서남동 순으로으로 저장 - dx=[0 ,-1, 0, +1] dy=[-1, 0 ,+1, 0 ] direction=[0, 3, 2, 1]
- 방향은 direction에 저장.
- d에서 받은 방향으로 direction 배열에서 인덱스 찾기.
- while문 내부에서 현재 위치에서 해당 인덱스의 dx, dy를 더해주어 위치 이동. - maps[nx][ny]==0이면 해당 map 2로 변경
- maps[nx][ny]의 3면이 1(바다)이거나 2(이미 방문)이면 해당 방향의 뒷 방향을 검사.
- 뒷 방향이 1이면 종료.
- 뒷 방향이 1이 아니면 뒤로 한 칸 이동. - direction의 인덱스는 index=(index+1)%4 로 왼쪽 방향으로 회전.
- 뒤 방향은 (index+2)%4
# 맵 입력
n, m=map(int, input().split())
# 캐릭터 위치와 방향
x, y, d= map(int, input().split())
# 방문한 칸 수
count=0
# 맵 받아서 2차원 리스트에 저장.
maps=[]
for i in range(n):
maps.append(list(map(int, input().split())))
# 북서남동으로 저장- 왼쪽으로 회전하므로
dx=[0 ,-1, 0, 1]
dy=[-1, 0 ,1, 0]
direction=[0, 3, 2, 1]
# 받아온 방향 인덱스에 저장.
index=direction.index(d)
while 1:
nx=x+dx[index]
ny=y+dy[index]
bx=x+dx[(index+2)%4]
by=y+dy[(index+2)%4]
dx=x+dx[(index+1)%4]
dy=y+dy[(index+1)%4]
ux=x+dx[(index+3)%4]
uy=y+dy[(index+3)%4]
if(maps[nx][ny]==0):
x, y=nx, ny
maps[x][y]=2
if((maps[dx][dy]==1 or maps[dx][dy]==2) and (maps[ux][uy]==1 or maps[ux][uy]==2) and (maps[nx][ny]==1 or maps[nx][ny])==2):
if(maps[bx][by]==1):
break
else:
nx=x-dx[index]
ny=y-dy[index]
# 왼쪽으로 회전
index=(index+1)%4
# 방문한 칸 수 세기
for i in range(n):
for j in range(m):
print(maps[i][j])
if maps[i][j]==2:
count+=1
print(count)-> 대충 생각한 대로 구현은 했지만.. 에러 발생.
책에서 파이썬 코드는 그대로 보기 싫어서 알고리즘 고수 어진님에게 sos..
if(maps[nx][ny]==0):
x, y=nx, ny
maps[x][y]=2여기서 x, y 변경해주고 아래서 탈출 조건 검색할 때에는 이전 x, y로 검사하고 있었음요.
# 맵 입력
n, m=map(int, input().split())
# 캐릭터 위치와 방향
x, y, d= map(int, input().split())
# 방문한 칸 수
count=0
# 맵 받아서 2차원 리스트에 저장.
maps=[]
for i in range(n):
maps.append(list(map(int, input().split())))
# 북서남동으로 저장- 왼쪽으로 회전하므로
dx=[0 ,-1, 0, 1]
dy=[-1, 0 ,1, 0]
direction=[0, 3, 2, 1]
# 받아온 방향 인덱스에 저장.
index=direction.index(d)
while 1:
nx=x+dx[index]
ny=y+dy[index]
for i in range(4):
# 왼쪽으로 회전
index=(index+1)%4
if(maps[nx][ny]==0):
x, y=nx, ny
maps[x][y]=2
break
else:
break
bx=x+dx[(index+2)%4]
by=y+dy[(index+2)%4]
ddx=x+dx[(index+1)%4]
ddy=y+dy[(index+1)%4]
ux=x+dx[(index+3)%4]
uy=y+dy[(index+3)%4]
if((maps[ddx][ddy]==1 or maps[ddx][ddy]==2) and (maps[ux][uy]==1 or maps[ux][uy]==2) and (maps[nx][ny]==1 or maps[nx][ny])==2):
if(maps[bx][by]==1):
break
else:
nx=x-dx[index]
ny=y-dy[index]
# 방문한 칸 수 세기
for i in range(n):
for j in range(m):
print(maps[i][j])
if maps[i][j]==2:
count+=1
# 처음 캐릭터가 방문한 칸은 항상 육지이므로 count +1
count+=1
print(count)- 왼쪽으로 회전하면서 육지가 있으면 이동, 아니면 회전만
- 회전한 인덱스를 탈출문 조건에 반영
- 마지막에 맨 처음에 방문한 count +1 해주기
결과가 나오긴 하는데 최적의 방법은 아닌 것 같아요.. 다들 어떻게 푸셨는지 공유 해주세요
+그리고 한 문제 푸는데 타임리밋은 얼마나 걸어두시는지, 안풀리는 문제는 어떻게 해결하시는지도.... 궁금합니당.ㅇ.ㅇ..ㅇ.....
