[코테] 구현 공부하기

Day5

구현 → 완전 탐색(모든 경우의 수를 다 계산하는 방법), 시뮬레이션(문제에서 제시한 알고리즘을 차례대로 직접 수행)

 

파이썬 < int 자료형 데이터의 개수에 따른 메모리 사용량 >

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

1,000,000 → 약 4MB

10,000,000 → 약 40MB

주의) 리스트를 여러 개 선언하고, 그중에서 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 못 풀 수도 있음.

 

1초에 2,000만 번의 연산 수행 가능하다고 가정.

시간 제한이 1초, 데이터의 개수 100만 개인 문제는 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용하여 풀어야 함.

 

예제1) 상하좌우

Q. N X N 크기의 정사각형 공간을 L(왼쪽), R(오른쪽), U(위쪽), D(아래쪽) 방향으로 한 칸 씩 이동할 수 있고, 가장 왼쪽 위 좌표는 (1,1) 이다. 그러나 공간을 벗어나는 이동은 무시된다. N 값, 이동 방향이 주어졌을 때 최종적으로 도착할 지점의 좌표를 출력하자.

A. 공간과 좌표를 구현해야 한다.

n = int(input()) #N입력
guide = input().split() #이동 방향 입력
x, y = 1, 1 #기준 좌표

#방향에 따른 이동 좌표
direction = ['L','R','U','D']
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

#이동 방향에 따라 좌표 이동
for i in guide:
  for j in range(0, len(direction)):
    if i == direction[j]:
      nx = x + dx[j]
      ny = y + dy[j]
  
  #공간을 벗어나는 경우에는 무시하고 넘어가기
  if nx < 1 or ny < 1 or nx > n or ny > n:
    continue
  
  #좌표에 이동한 좌표 대입
  x, y = nx, ny

print(x, y)

 

예제2) 시각

Q. 00시 00분 00초부터 N(0≤N≤23)시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 경우의 수를 구하자.

A. 00시 00분 00초 ~ 23시 59분 59초까지의 모든 경우는 86,400가지로 100,000개보다 작아서 하나씩 세서 풀어도 된다. → 완전 탐색(Brute Forcing) 유형. 탐색할 전체 데이터가 100만 개 이하일 때 완전 탐색 사용.

n = int(input())
cnt = 0

#시
for i in range(0, n+1):
  #분
  for j in range(0, 60):
    #초
    for k in range(0, 60):
      #시간을 str타입으로 변환
      clock = str(i) + str(j) + str(k)
      #시간에 3이 들어가 있다면 1을 카운트
      if '3' in clock:
        cnt += 1
      else:
        continue

print(cnt)