구현

* < 이것이 코딩테스트다 > 책 내용을 정리한 글입니다.


구현 Implementation : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
구현 유형의 문제 : 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
피지컬이 좋다 : 프로그래밍 언어의 문법에 능숙하고도 코드 작성 속도가 빠르다
구현 유형의 문제 -> 피지컬을 요구하는 문제 구현하기 어려운 문제
- 알고리즘은 간단한데 코드가 지나칠만큼 길어지는 문제
- 특정 소수점자리까지 출력해야하는 문제
- 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야하는( 파싱을 해야하는 ) 문제
( 사소한 조건 설정이 많은 문제 ) - 프로그래밍 문법 정확하게 숙지 및 라이브러리 사용 경험 풍부해야 유리함

구현 ( 완전 탐색, 시뮬레이션 유형 ) 유형
- 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
- 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제 유형
둘 다 구현이 핵심이 되는 경우가 많아 구현 장에서 다루고 있음. # 구현 시 고려해야 할 메모리 제약 사항 1.  C/C++에서 변수의 표현범위
int -> long long -> BigInteger
파이썬에서 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있다는 점 유의 2. 파이썬에서 리스트 크기
- 대체로 코딩 테스트에서는 128 - 512 MB로 메모리 제한
- 파이썬은 다른 언어에 비해 구현상의 복잡함은 적은 편이지만, 데이터 처리량이 많을 때는 꼭 메모리 제한 고려해야함

- 보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편, 고차원적인 사고력을 요구하는 문제는 나오지 않는 편이라 문법에 익숙하다면 오히려 쉽게 풀 수 있음. - 구현 유형의 문제는 C/C++/Java로 풀 때 더 어려움
문자열 처리하거나 큰 정수 처리하는 문제 출제 경우가 많은데, 문자열 처리가 까다롭고, 큰 정수 처리 라이브러리 별도 사용 필요
파이썬은 기본 문법만 알아도 상대적으로 구현 유형의 문제를 쉽게 해결할 수 있음
PyPy가 구현 난이도가 쉽고 프로그램 실행시간이 다소 짧은 편

구현 문제의 대표적 예시 : 상하좌우 문제, 시각 문제
코딩테스트에서 가장 난이도가 낮은 1,2번 문제는 대부분 그리디 알고리즘이나 구현 문제임
(1) 상하좌우 답안 예시

#	N을 입력받기
n=int(input())
x,y=1,1
plans = input().split()

#L,R,U,D에 따른 이동 방향
dx = [0,0,-1,1]
dy = [ -1,1,0,0 ]
move_types = [ ‘L’, ‘R’, ‘U’, ‘D’ ]

# 이동 계획 하나씩 확인
for plan in plans :
  # 이동 후 좌표 구하기
  for i in range(len(move_types)):
    if plan == move_types[i]:
      nx = x + dx[i]
    # 공간 벗어나는 경우 무시
    if nx<1 or ny<1 or nx>n or ny>n : 
      continue
    # 이동 수행
    x, y = nx, ny
  
  print(x,y)

(2) 시각 ( 완전 탐색 문제로 분류되기도 함 )
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램
- 완전 탐색은 데이터가 100만 개 이하일 때

< 왕실의 나이트 > 실전문제
나이트는 말을 타고 있기 때문에 L자로 형태로만 이동할 수 있으며, 정원밖으로는 나갈 수 있음 ( 수평으로 두 칸, 수직 한 칸 / 수직 두 칸, 수평 한 칸 ) < 게임 개발 > 실전문제
전형적인 시뮬레이션 문제. 삼성전자 코딩 테스트에서 자주 출제되는 대표적인 유형으로, 별도‎의 알고리즘 보다는 문제에서 요구하는 내용을 오류 없이 성실하게 구현만 할 수 있다면 풀 수 있다는 특징이 있음.
- 다만 문제가 길고 바르게 이해하여 소스코드로 옮기는 과정이 간단하지 않음. 따라서 이러한 문제를 잘 풀 수 있도록 반복적인 숙달이 필요 * 일반적으로 방향을 설정해서 이동하는 문제 유형에서는 dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적
* 파이썬 2차원 리스트 선언시 : 컴프리헨션을 이용하는 것이 효율적

- global 키워드 : 정수형 변수인 direction 변수가 함수 바깥에서 선언된 전역변수이기 때문

- 보통 실무의 코딩은 예외 고려해 코드 짜지만, 코딩 테스트는 입력값이 주어지는 경우가 대부분이므로, 이런 예외처리를 고려하지 않고 빠르게 코드 작성하는 데 목표를 둠

# N, M을 공백으로 구분하여 입력받기
n, m = map ( int, input().split()) 

# 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
d = [[0]*m for _ in range(n)]
#	현재 캐릭터의 X좌표, Y좌표, 방향을 입력받기
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 trun_left():
  global direction
  direction -=1
  if direction == -1:
    direction = 3
    
# 시뮬레이션 시작
count = 1
turn_time = 0
while True:
  #왼쪽으로 회전
  turn_left()
  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
   count+=1
   turn_time=0
   continue
   
  
#	회전한 이후 정면에 가보지 않은 칸이 없거나 바다인 경우
  else:
    turn_time+=1
    #네 방향 모두 갈 수 없는 경우
  if turn_time == 4:
    nx=x-dx[direction]
    ny=y-dy[direction]
    #	뒤로 갈 수 있다면 이동하기
    if array[nx][ny]==0:
      x=nx
      y=ny
    #뒤가 바다로 막혀있는 경우
    else:
      break
    turn_time=0
    
# 정답 출력
print(count)