주요 알고리즘-구현

• 상하좌우

A는  1X1정사각형이 N개 있는 형태의 정사각형 공간위에 서있다. A는 상하좌우로 이동할 수 있으며 시작좌표는 (1,1)이다

6개의 명령에 따라 L:왼쪽 이동,R:오른쪽 이동,U:위로 이동,D:아래로 이동

A가 NXN을 벗어나는 움직임을 하면 무시된다. 도착좌표가 출력되도록 프로그램 작성하시오

 

-내 풀이                                                                                             -예제 코드                          

n = int(input())
move = list(input().split())

x, y = 1, 1

for i in move:
  if i == "R" and y < n:
    y += 1
  elif i == "L" and y>1:
    y -=1
  elif i == "U" and x>1:
      x -= 1
  elif i == "D" and x<n:
      x += 1

print(x,y)

 

 

 

---

• 시각

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각중 3이 포함된 시각을 세는 프로그램이다.

 

시간을 1씩 올리면서 완전 탐색 알고리즘으로 모든 경우를 탐색하는 방법이다.

전체 데이터 수가 100만개 이하일때 적절하다.

 

n = int(input())
cnt = 0

for h in range(n+1):
    for m in range(60):
      for s in range(60):
        if '3' in str(h) +str(m) +str(s):
          cnt +=1
print(cnt) 

 

---

• 왕실의 나이트

8X8로 행은 a,b,c,d,e,f,g,h 열은 1,2,3,4,5,6,7,8 로 입력받아(a1)

나이트가 이동할 수 있는 경우의 수 구하기(말은 정원밖으로 나갈 수 없다)  

1.수평으로 두칸 이동 후 수직으로 한칸 이동

2.수직으로 두칸 이동 후 수평으로 한칸 이동

 

상하좌우 문제와 비슷하다! 나이트의 이동경로를 dx,dy에 넣을 수도 있지만

steps=[(-2,1),(-1,2),(1,-2)...] 같이 정의하고 아래 ㅓ럼 풀이 가능

for step in steps:

    next_row = row + step[0]

    next_col = col +step[1]

또한 시작위치를 입력받을때 row와 col 리스트를 굳이 정의 할 필요 없이 아래 처럼 풀이 가능

row= int(start[1])

col=int(ord(start[0])-int(ord('a'))+1

 

#현재 나이트 위치 입력받기

start=input()
col=['a','b','c','d','e','f','g','h']
row=[1,2,3,4,5,6,7,8]

dx=[2,-2,2,-2,1,-1,1,-1]
dy=[1,1,-1,-1,2,2,-2,-2]
x, y=1, 1

for j in range(len(col)):
  if start[0] in col[j]:
    x=j
    break
for k in range(len(row)):
  if int(start[1]) == row[k]:
    y=k
    break
count=0

for i in range(len(dx)):
  next_x=x+dx[i]
  next_y=x+dx[i]
  count+=1
  if next_x<0 or next_y<0 or next_x>=8 or next_y>=8: #풀고보니 해당위치로 이동가능할때 count up하는 방식이 좋아보
    count-=1
    continue

print(count)