[알고리즘] 이코테 - 구현

• 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
• 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제, 피지컬을 요구하는 문제(문법에 능숙한 경우에 해당)
• 사소한 조건 설정이 많은 문제일수록 코드로 구현하기가 까다롭다.

 

• 구현이 핵심이 되는 경우
  • 완전탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
  • 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

 

• 파이썬은 매우 큰 수의 연산 또한 기본 지원
• 파이썬에서 리스트 크기 제약
  • 리스트를 여러개 선언하고 그 중에서 크기가 1000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 됨.

 

• 파이썬은 C++에 비해 동작 속도가 느리다. 그래서 파이썬 선택 시 2배의 수행 시간 제한을 적용하는 경우도 있다.
• 일반적으로 1초에 2000만 번의 연산 수행 e.g., 시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제가 있다면 일반적으로 시간 복잡도가 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야 한다.
• 따라서 알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 먼저 확인한 뒤에 이 문제를 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측.

 

• 구현 문제에 접근하는 방법
  • 실무에서는 파이썬으로 프로그램 개발할 때 GPU 연동 및 C언어로 된 코어 SW 사용.
  • Pypy3는 파이썬3의 문법 그대로 지원, 대부분 파이썬3보다 실행 속도 더 빠름.

 

e.g., 왕실의 나이트: 나이트가 이동할 수 있는 경우는 2가지이다. (수평으로 두칸 이동한 뒤에 수직으로 한 칸 이동하기, 수직으로 두 칸 이동한 뒤에 수평으로 한칸 이동하기) 나이트의 위치가 주어졌을 때, 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오.

-> 나이트가 이동할 수 있는 경로를 리스트에 담고, 8가지 경우의 수를 반복문을 통해 하나씩 검사한다.

# 왕실의 나이트
check=[[2,1],[-2,-1],[-2,1],[2,-1],[1,2],[-1,-2],[-1,2],[1,-2]]

n=input("n: ") //c2
now=[]
now.append(ord(n[0])-96)
now.append(int(n[1]))
answerNot=0

for i in range(len(check)):
  if now[0]+check[i][0]>8 or now[0]+check[i][0]<1:
    answerNot+=1
    continue
  if now[1]+check[i][1]>8 or now[1]+check[i][1]<1:
    answerNot+=1

print(8-answerNot) //6

 

e.g., 게임 개발: 캐릭터의 움직임에 이상이 있는지 테스트하려는 상황이다. 메뉴얼에 따라 캐릭터를 이동시킨 뒤에, 캐릭터가 방문한 칸의 수를 출력하는 프로그램 만들기.

1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 갈 곳을 정한다.

2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.

3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한칸 뒤로 가고 1단계로 돌아간다. 단 이때 뒤족 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

 

n, m=map(int,input().split())
d=[[0]*m for _ in range(n)] # 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
x,y,direction=map(int,input().split())
d[x][y]=1

#맵 정보 입력받기
array=[]
for i in range(n):
  array.append(list(map(int, input().split())))
#북, 동, 남, 서
dx=[-1,0,1,0]
dy=[0,1,0,-1]

#왼쪽 회전 메서드
def turn():
  global direction
  direction-=1
  if direction==-1:
    direction=3


#시물레이션 시작
cnt=0# answer
time=0 #돌아간 횟수
while True:
  turn()
  nx=x+dx[direction]
  ny=y+dy[direction]

  if d[nx][ny]==0 and array[nx][ny]==0:
    d[nx][ny]=1
    x=nx
    y=ny
    cnt+=1
    time=0
    continue
  else:
    time+=1

  if time==4:
    nx=x-dx[direction]
    ny=y-dy[direction]
    if array[nx][ny]==0:
      x=nx
      y=ny
    else:
      break
    time=0

print(cnt)