구현_Python

아 역시 파이썬이 최고.. Java에서 방황 후 돌아왔습니다.

 

1. 구현?

 

풀이를 떠올리는 것은 쉽지만, 코드 작성이 어려운 문제

 ex) 특정 소숫점으로 출력, 문자열 -> 리스트 변환 처럼 사소한 조건이 많은 경우

 

유형1. 완전 탐색 -> 모든 경우의 수 다 계산

유형2. 시뮬레이션 -> 문제에서 제시한 알고리즘을 한 단계씩 차례대로 수행

 

2. 메모리 제약사항

1) 리스트

대체로 코테에서는 128 ~ 512MB로 메모리 제한

리스트의 길이가 1,000,000 일 경우 : 약 4KB

10,000,000일 경우 : 약 40KB 이다.

따라서 리스트를 여러개 선언한다면 용량 제한으로 실패할 수 있음.

 

예제 1) 상하 좌우

 

- 시뮬레이션 유형

- 연산 횟수가 이동 횟수에 비례한다.

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

#방향 설정
dx = [0,0,-1,1]
dy = [-1,1,0,0]
moves = ['L','R','U','D']

x , y = 1,1

for plan in plans:
    for i in range(4):
        if plan == moves[i]:
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 1 or nx > N or ny < 1 or ny > N:
                continue
            else:
                x = nx
                y = ny
print(x, y)

 

예제2) 시각

- 완전 탐색 유형 : 모든 경우를 세는 문제이다. 

- ㄴ> 비효율적 시간 복잡도를 가지고 있으므로 전체 데이터 개수 확인 필수!

- 하루가 86400초이기 때문에 제한 시간 안에 문제 해결 가능

N = int(input())
cnt = 0
for h in range(N+1):
    for m in range(60):
        for s in range(60):
            time = str(h) + str(m) + str(s)
            if '3' in time:
                cnt += 1

print(cnt)

 

문제1) 왕실의 나이트

start = input()

# 알파벳을 1~8로 치환
x = int(ord(start[0])) - int(ord('a')) + 1
y = int(start[1])

directs = [(1,2), (1,-2), (-1,2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1)]
result = 0
for direct in directs:
    n_x = x + direct[0]
    n_y = y + direct[1]

    if(n_x < 1 or n_x > 8 or n_y < 1 or n_y > 8):
        continue
    else:
        result += 1

print(result)