구현
- 머릿속의 알고리즘을 소스코드로 바꾸는 과정
- 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
- 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행
- int 자료형 데이터 리스트 길이 10,000,000 == 메모리 사용량 약 40MB
- 일반적으로 2000만번의 연산 == 실행시간 1초
- 데이터 개수가 100만개 -> O(NlogN) == 2000만번 연산
문제1. 상하좌우
#상하좌우 2020-12-16 16:42 시작 16:53 종료
N = int(input())
lis = input().split()
pos = [1,1]
for i in lis:
if i == "L":
if pos[1] != 1:
pos[1] -= 1
elif i == "R":
if pos[1] != N:
pos[1] += 1
elif i == "U":
if pos[0] != 1:
pos[0] -= 1
elif i == "D":
if pos[0] != N:
pos[0] += 1
print(pos[0], pos[1])
이 방식보다 각 이동방향에 해당하는 정보를 리스트에 넣고 사용하는게 더 나음
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
nx = x + dx[i]
ny = y + dy[i]
문제2. 시각
#시각 2020-12-16 17:04 시작 16:53 종료 17:23
N = int(input())
cnt = 0
min,sec = 0,0
hour_cnt = 0
while min != 60:
if str(min).count("3") >= 1 or str(sec).count("3") >= 1:
hour_cnt += 1
sec += 1
if sec == 60:
min += 1
sec = 0
if N>= 3 and N<13:
cnt += 60*60
cnt -= hour_cnt
if N>= 13 and N<23:
cnt += 60*60*2
cnt -= hour_cnt * 2
if N == 23:
cnt += 60 * 60 * 3
cnt -= hour_cnt * 3
print(hour_cnt*(N+1) + cnt)
그냥 3중 반복문으로 완전탐색하는게 훨 편했을 것
시단위에서 계산량을 좀 줄이려 했으나 어차피 하루는 86400초이므로 86400번만 검사 수행해도 되기 때문에 완전탐색 ㄱ
문제3. 왕실의 나이트 (20분정도)
#왕실의 나이트 2020-12-16 17:04 시작
inp = input()
pos = []
pos.append(int(inp[1]))
pos.append(ord(inp[0])-96)
dx = [1,2,2,1,-1,-2,-2,-1]
dy = [-2,-1,1,2,2,1,-1,-2]
cnt = 0
for i in range(0,8):
nx = pos[0] + dx[i]
ny = pos[1] + dy[i]
if nx <= 0 or ny <= 0 or nx >= 9 or ny >= 9:
continue
cnt += 1
print(cnt)
방향이 많을 때는 그냥 튜플로 방향 정보를 넣는게 더 편하다
96 빼지말고 걍 int(ord(“a”)) 빼고 1 더하자
문제4. 개임 개발 (40분 정도 대략적인 기능 완성, 나머지 50분은 에러 수정)
#게임 개발 2020-12-16 시작 종료
#보고있는 왼쪽에 갈 곳이 있는지
#있다면 한칸 전진
#없다면 왼쪽으로만 돌고 다시 왼쪽에 갈 곳이 있는지
#만약 4 방향 모두 가본 곳이나 바다면
#방향 유지한채로 뒤로 간다음 왼쪽에 갈 곳이 있는지
#뒤가 바다라면 종료
N,M = list(map(int,input().split()))
pos = [0,0]
pos[1],pos[0],dir = list(map(int,input().split()))
world = []
for i in range(0,N):
world.append(list(map(int,input().split())))
visited = []
visited = world
res = 0
move = [(0,-1),(1,0),(0,1),(-1,0)] #위 오 밑 왼
way = [0,1,2,3] #북 동 남 서
visited[pos[0]][pos[1]] = 2
while True:
for i in visited:
print(i)
print("-----")
cnt = 0
for i in range(0,4):
if dir == 0:
next_way = 3
else:
next_way = dir-1
nx = pos[0] + move[next_way][0]
ny = pos[1] + move[next_way][1]
if nx <= -1 or ny <= -1 or nx >= N or ny >= M:
dir = next_way
cnt += 1
continue
elif visited[nx][ny] == 0:
pos[0] = nx
pos[1] = ny
visited[nx][ny] = 2 # 방문
res += 1
break
else:
dir = next_way
cnt += 1
if cnt == 4:
print("no way")
print(pos)
print(dir)
nx = pos[0] - move[dir][0]
ny = pos[1] - move[dir][1]
print(nx, ny)
if nx <= -1 or ny <= -1 or nx >= N or ny >= M:
print(res)
break
elif visited[nx][ny] == 2:
pos[0] = nx
pos[1] = ny
res += 1
print("go back")
else:
print("done")
print(res)
break
for i in visited:
print(i)
print("-----")
#결과에 x,y축 바꿔서 제출 생각할것
왜 갈 곳이 없고 뒤에 지나온 길일 때 뒤로 안 가는지 고민중
문제점1. 생각했던 x y축이랑 이중리스트의 인덱스를 틀리게 맞춤
문제점2. 갈 곳이 없을 때 다시 방향이 원상태로 돌아와야 하는데 시작 방향부터 4번 체크하면 원상태로 안오고 마지막에 한번 더 틀어줘야 원상태, 다음부턴 그냥 처음 상태 변수에 저장하고 불러오는게 나을 듯
문제 해결
#게임 개발 2020-12-16 17:04 시작 17:57 종료
#보고있는 왼쪽에 갈 곳이 있는지
#있다면 한칸 전진
#없다면 왼쪽으로만 돌고 다시 왼쪽에 갈 곳이 있는지
#만약 4 방향 모두 가본 곳이나 바다면
#방향 유지한채로 뒤로 간다음 왼쪽에 갈 곳이 있는지
#뒤가 바다라면 종료
N,M = list(map(int,input().split()))
pos = [0,0]
pos[1],pos[0],dir = list(map(int,input().split()))
world = []
for i in range(0,N):
world.append(list(map(int,input().split())))
visited = []
visited = world
res = 0
move = [(0,-1),(1,0),(0,1),(-1,0)] #위 오 밑 왼
way = [0,1,2,3] #북 동 남 서
visited[pos[1]][pos[0]] = 2
while True:
#for i in visited:
#print(i)
#print("-----")
cnt = 0
for i in range(0,4):
if dir == 0:
next_way = 3
else:
next_way = dir-1
nx = pos[0] + move[next_way][0]
ny = pos[1] + move[next_way][1]
if nx <= -1 or ny <= -1 or nx >= M or ny >= N:
dir = next_way
cnt += 1
continue
elif visited[ny][nx] == 0:
pos[0] = nx
pos[1] = ny
visited[ny][nx] = 2 # 방문
res += 1
break
else:
dir = next_way
cnt += 1
if cnt == 4:
if dir == 0:
next_way = 3
else:
next_way = dir-1
#print("no way")
#print(pos)
#print(dir)
nx = pos[0] - move[next_way][0]
ny = pos[1] - move[next_way][1]
#print(nx, ny)
if nx <= -1 or ny <= -1 or nx >= N or ny >= M:
print(res)
break
elif visited[ny][nx] == 2:
pos[0] = nx
pos[1] = ny
res += 1
#print("go back")
else:
#print("done")
print(res)
break
#for i in visited:
# print(i)
#print("-----")
#결과에 x,y축 바꿔서 제출 생각할것
이런 경로탐색류 문제는 어디서 막히는지 확인 위해 행렬지도 전체를 루프마다 확인해보자
해설 보고나서
- 방향전환 작업을 위치정보를 global 선언하고 별도 함수로 구현해서 모듈화하는게 더 쉬웠을 거임