[코딩테스트 python] 구현; 완전탐색, 시뮬레이션 알고리즘

 

출처 [저서] : 이것이 취업을 위한 코딩테스트다 with 파이썬

 

구현

= 아이디어를 코드로

유형

: 완전탐색, 시뮬레이션

메모리 사용량 with Python

: int 자료형 데이터 개수

리스트 길이	메모리 사용량
~ 1,000,000	약 4KB
10,000,000	약 40MB

>> 사용량 제한보다 적은 크기의 메모리 사용 해야함

시간제한

1초에 2,000만 번 연산 수행 가정

>> 데이터 개수 = 100만 개, 시간복잡도 O(NlogN)이내의 알고리즘 사용해야함

    예시]  n = 1,000,000일 때,  Nlog₂N =약 20,000,000

접근방법

고차원적인 사고력x  >> 문법에 익숙하면 ok, 문제를 잘 읽으면 해결 가능

 

1. 상하좌우 문제

# 이동 횟수에 비례 
# >> 이동횟수:시간복잡도 = N:O(N)
# 시뮬레이션 유형

( x, y )
>> Right = y값 1 증가   /   Left = y값 1 감소
>> Up = x값 1 감소  /  Down = x값 1 증가

(1,1)	(1,2)	(1,3)	(1,4)
(2,1)	(2,2)	(2,3)	(2,4)
(3,1)	(3,2)	(3,3)	(3,4)
(4,1)	(4,2)	(4,3)	(4,4)

n = int(input())
plans = input().split()

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

x, y = 1, 1
for plan in plans:
  for i in range(len(types)):
    if plan == types[i]:
      nx = x + dx[i]
      ny = y + dy[i]
  if nx<1 or ny<1 or nx>n or ny>n:
    continue
  x, y = nx, ny

print(x, y)

 

2. 시각 문제

# N시 59분 59초까지의 시각 중 3이 포함되는 모든 경우의 수 반환
# 완전탐색 유형

my code 

n = int(input())
in_three = [3, 13, 23, 43, 53] + [i for i in range(30, 40)]

answer = 0
for h in range(n+1):
  if h in in_three:
    answer += (60 * 60)
  else:
    answer += ( len(in_three) * 60 #분에 포함
               + (60-len(in_three))*len(in_three) ) #초에 포함
print(answer)

> N시도 세어야 하기에 N+1을 해야하는 것이 point

 

저서의 풀이

n = int(input())

answer = 0
for h in range(n+1):
  for m in range(60):
    for s in range(60):
      if '3' in str(h)+str(m)+str(s):
        answer += 1
print(answer)

# 하나하나 새면서 해도 ok. 모든 경우의 수 = 86, 400가지 밖에 안 됨
# 문자열로 검사하는 것이 point

>> 반복문 적게 돌리고 싶어서 고민하는 것도 좋지만 심플하고 빠르게 구현하고 넘어가는 것도 좋은 방법일 듯