하기 내용은 '이것이 취업을 위한 코딩 테스트다 with 파이썬(저자: 나동빈님)'의 책을 정리한 내용입니다.

chap04. 구현

피지컬로 승부하기

코딩테스트에서의 구현 : “머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정”
→ 구현 문제 유형 : 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념

• 구현하기 어려운 문제

  • 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
  • 특정 소수점 자리까지 출력해야 하는 문제
  • 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야 하는) 문제

• 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법

• 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

파이썬에서 리스트 크기

대체로 코딩 테스트 : 128 ~ 512MB로 메모리 제한

데이터의 개수(리스트의 길이)	메모리 사용량
1,000	약 4KB
1,000,000	약 4MB
10,000,000	약 40MB

구현 문제에 접근하는 방법

보통의 구현 문제 : 사소한 입력 조건 등을 문제에서 명시, 문제의 길이가 꽤 긴 편
고차원적인 사고력을 요구하는 문제는 나오지 않음 → 문법에 익숙하다면 쉽게 풀 수 있음

• 시각
  • 완전 탐색 : 가능한 경우의 수를 모두 검사해보는 탐색 방법

# 구현 - 게임 개발
import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
# 방문한 위치를 저장하기 위한 맵을 생성해 0으로 초기화
d = [[False]*M for _ in range(N)]

# x, y, direction: (A, B), d: 바라보는 방향
# 0: 북쪽, 1: 동쪽, 2: 남쪽, 3: 서쪽
x, y, direction = map(int, input().rstrip().split())
dx, dy = [-1, 0, 1, 0], [0, -1, 0, 1]
d[x][y] = True # 현재 좌표 방문 처리

# 맵 정보 입력
arr = [list(map(int, input().rstrip().split())) for _ in range(N)]

# 왼쪽으로 회전하는 함수
def turn_left():
  global direction
  direction -= 1 # 왼쪽으로 회전
  if direction == -1:
    direction = 3 # 0: 북쪽, 1: 동쪽, 2: 남쪽, 3: 서쪽

# 시뮬레이션
cnt = 1
turn_time = 0
while True:
  # 왼쪽으로 회전
  turn_left()
  nx, ny = x + dx[direction], y + dy[direction]
  
  # 회전한 후 정면에 방문하지 않은 곳이 존재하는 경우
  if d[nx][ny] == 0 and arr[nx][ny] == 0:
    d[nx][ny] = True
    x, y = nx, ny
    cnt += 1
    turn_time = 0
    continue
  
  # 회전한 이후 정면에 방문하지 않은 곳 없거나 바다인 경우
  else:
    turn_time += 1
  
  # 네 방향 모두 갈 수 없는 경우
  if turn_time == 4:
    nx, ny = x - dx[direction], y - dy[direction]
    # 뒤로 갈 수 있는 경우 이동
    if arr[nx][ny] == 0: # 육지
      x, y = nx, ny
    else: # 바다
      break
    turn_time = 0

print(cnt)

• 전형적인 시뮬레이션 문제
  • 삼성전자 공채 코테에 자주 출제되는 대표적인 유형
  • 별도의 알고리즘 필요 → 문제에서 요구하는 내용 오류없이 성실하게 구현할 수 있다면 가능
• 일반적으로 방향 설정해 이동하는 문제 유형에서는 dx, dy라는 별도의 리스트를 만드는 것이 효과적

→ 코드 작성 시 반복문을 이용해 모든 방향을 차례로 확인 가능