[알고리즘] Implementation

Implementation

구현(Implementation)이란?
머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
모든 범위의 코딩 테스트 문제 유형을 포함하는 개념

프로그래밍 언어의 문법을 정확히 알고있어야 한다.
문제의 요구사항에 어긋나지 않은 답안 코드를 작성해야 한다.

즉, 프로그래밍 언어의 문법의 능숙도와 코드 작성 속도를 요구한다.

비교적 단순한 알고리즘을 요구하지만 코드의 길이가 길어지거나, 사소한 요구 조건이 많은 경우가 존재한다.
모든 경우의 수를 계산하여 해결하는 완전 탐색, 문제의 알고리즘을 한 단계식 해결하는 시뮬레이션, API 개발 문제가 대표적인 경우로 필요한 라이브러리를 활용하는 것이 중요

시간 및 메모리 제한

코딩 테스트의 시간 제한과 메모리 제한을 벗어나지 않게 코딩을 해야한다.

파이썬 3.7의 경우 1초에 약 2,000만 번의 연산을 수행한다.
따라서 시간 제한이 1초이고, 데이터의 개수가 100만 개라면 일반적으로 시간 복잡도가 O(NlogN)이내인 알고리즘을 사용해야 한다.

메모리의 경우 파이썬 리스트의 크기가 1,000만 이상이 된다면 메모리 제한이 걸리는 경우가 많다.

문제의 제한 사항(시간 및 메모리 제한)과 입출력 조건(데이터의 범위)를 확인하고 알고리즘을 사용하자

문제 : 게임 개발

n, m = map(int, input().split())
#방문 여부
visit = [[0]*m for _ in range(n)] #방문한 경우 1, 아직 가보지 않은 경우 0
#2차원 리스트의 초기화 방법, 리스트 컴프리헨션 문법

row, col, d = map(int, input().split())

visit[row][col] = 1 #시작위치는 방문체크

#게임 맵 정보 (0,0)부터 시작
game_map = []
for i in range(n):
  map_row = list(map(int, input().split()))
  game_map.append(map_row)
  #0은 육지, 1은 바다

count = 1 #방문한 칸 수
direction = [0, 1, 2, 3] #북, 동, 남, 서
drow = [-1, 0, 1, 0]
dcol = [0, 1, 0, -1] #북, 동, 남, 서로 이동 시 죄표 변화
first_direction = d #이동 이전의 최초의 방향

while True:
  d = (d + 3) % 4 #왼쪽으로 회전
  next_row = row + drow[d]
  next_col = col + dcol[d]

  if game_map[next_row][next_col] == 0 and visit[next_row][next_col] == 0: #이동이 가능한 경우
    visit[next_row][next_col] = 1
    row = next_row
    col = next_col
    first_direction = d #이동 후 기준 방향
    count += 1
    continue
  
  if first_direction == d: #최초 방향으로 회전할 때 까지 이동하지 못한 경우
    next_row = row - drow[d]
    next_col = col - dcol[d]
    if game_map[next_row][next_col] == 0:
      row = next_row
      col = next_col
    else:
      break

print(count)

참고

나동빈(2020).이것이 취업을 위한 코딩 테스트다 with 파이썬.한빛미디어