Implementation 개념

아이디어를 코드로 바꾸는 구현

Implementation이란 머리속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 알고리즘 문제를 해결함에 있어서 고민 끝에 얻은 풀이과정을 소스코드로 옮기는 것을 말한다. 아마 알고리즘에 대한 피지컬을 의미한다고 볼 수 있을 것이다. 또한 파이썬에서 제공하는 표준 라이브러리를 숙지하고 있어야 조금 더 쉽게 해결할 수도 있다.

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

이 두가지 방법으로 Implemetation에 접근할 수 있다.

파이썬에서 리스트 크기

문제를 풀기 앞서서 리스트의 크기 제약에 대해서 알고 있어야한다. 일반적으로 코딩 문제를 풀 때에넌 128~512MB로 메모리를 제한하는데, 이러한 메모리 제한을 염두해 둬야한다. 시간제한 1초와 메모리 제한 128MB로 학습하면 안정적으로 이는 1초에 2000만 번의 연산을 수행한다고 가정할 수 있다.

상하좌우

여행가 A는 N X N크기의 정사각형 공간 위에 서 있다. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N,N)이다. 시작 좌표는 (1,1)이며 L,R,U,D로 한칸 씩 움직인다. 또한 해당 좌표에서 움직일 수 없는 입력이면 무시된다. 이를 바탕으로 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X,Y)를 공백으로 구분하여 출력한다.

문제

• 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 =< N =< 100)
• 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1 =< 이동 횟수 =< 100)

코드

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

#L,R,U,D 에 따른 이동방향
#여기서 이동방향은 X,Y축에 대한 것이 아니라. 행렬 상에서 움직이는 것
#(1,1)에서 (1,2)로 가는게 R이고 이는 (0,1)을 더해준 것이다.

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]
            ny = y + dy[i]
    
    if nx <1 or ny<1 or nx>n or ny>n:
        continue
    #if, Continue는 해당 조건이 맞다면 아래의 코드를 실행하지 않음.
    x,y = nx,ny
    
print(x,y)

시각

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성한다. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.

• 00시 00분 03초
• 00시 13분 30초
  반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다.
• 00시 02분 55초
• 01시 27분 45초

문제

• 첫째 줄에 정수 N이 입력된다. (0 =< N =< 23)
• 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.

접근방법

24 x 60 x 60 3중 반복문을 사용해서 3이 들어가면 카운트를 하면된다. 이러한 유형은 완전 탐색, Brute Focing유형으로 분류된다. 비효율적인 시간 복잡도를 가지고 있어서 데이터 개수가 큰 경우에 정상적으로 동작하지 않아 100만 개 이하일 때 사용하면 적절하다.

코드

h = int(input())

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

print(count)