이것이 취업을 위한 코딩 테스트다 with 파이썬

구현

머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기

구현 문제 유형은 모든 범위의 코딩테스트 문제 유형을 포함하는 개념

이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 ‘구현' 유형으로 묶어서 다루고 있음

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

• 구현 시 고려해야 할 메모리 제약 사항
  • 파이썬에서 리스트의 크기
    • int 자료형 데이터의 개수에 따른 메모리 사용량

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

  • 채점 환경
• 상하좌우 (p.111)

  # 입력값 
  # 5
  # R R R U D D
  # 출력값
  # 3 4
  def p4_1():
    n = int(input())
    data = list(input().split(" "))
    x=1
    y=1
    for i in data:
      nx=x
      ny=y
      if i == "R":
        ny+=1
      elif i == "L":
        ny-=1
      elif i == "U":
        nx-=1
      else:
        nx+=1
      if nx<1 or nx>n or ny<1 or ny >n:
        continue
      else:
        x=nx
        y=ny
        
    print("{},{}".format(x,y))

  if문 대체

  dx = [0,0,-1,1]
  dy = [-1,1,0,0]
  move_types = ['L','R','U','D']

• 시각 (p.113)

  # 입력값
  # 5
  # 출력값
  # 11475
  def p4_2():
    n = int(input())
    count=0
    t = {"hour":0,"minute":0,"second":0}
    while t["hour"]<=n:
      if t["hour"]%10 ==3:
        count+=1
      elif t["minute"]//10==3:
        count+=1
      elif t["minute"]%10==3:
        count+=1
      elif t["second"]//10==3:
        count+=1
      elif t["second"]%10==3:
        count+=1
      t["second"]+=1
      if t["second"] == 60:
        t["second"]=0
        t["minute"]+=1
      if t["minute"] == 60:
        t["minute"]=0
        t["hour"]+=1
    print(count)

  문자로 생각하기

  for i in range(n+1):
      for j in range(60):
        for k in range(60):
          if '3' in str(i)+str(j)+str(k):
            count+=1
    print(count)

• 왕실의 나이트 (p.115)

  # 입력값
  # a1
  # 출력값
  # 2
  def p4_3():
    data=input()
    x = int(data[1])
    y = int(ord(data[0]))-int(ord('a'))+1
    
    dx=[2,2,-2,-2,1,-1,1,-1]
    dy=[1,-1,1,-1,2,2,-2,-2]
    
    count=0
    for i in range(8):
      if x+dx[i]<1 or x+dx[i]>8 or y+dy[i]<1 or y+dy[i]>8:
        continue
      else:
        count+=1
    print(count)

• 게임 개발 (p.118)

  # 입력값
  # 4 4
  # 1 1 0
  # 1 1 1 1
  # 1 0 0 1
  # 1 1 0 1
  # 1 1 1 1
  # 출력값
  # 3
  def turn_left():
    global direction
    direction -= 1 
    if direction == -1:
      direction=3
      
  def p4_4():
    n,m = map(int,input().split(" "))
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    d = [[0]*m for _ in range(n)]
    global direction
    x,y,direction=map(int,input().split(" "))
  
    d[x][y]=1
    array = []
    for i in range(n):
      array.append(list(map(int,input().split(" "))))
    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_timr = 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)