구현 개념 정리

📖 구현(implementation)

• 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
• 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념

📖 완전 탐색

• 모든 경우의 수를 주저 없이 다 계산하는 해결 방법

📖 시뮬레이션

• 문제에서 제시한 알고리즘을 한 단계식 차례대로 직접 수행

📖 구현 시 고려해야 할 메모리 제약 사항

• 파이썬에서는 프로그래머가 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본으로 지원
• 다만, 파이썬에서의 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있음

📖 파이썬에서 리스트 크기

• int 자료형 데이터의 개수에 따른 메모리 사용량

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

• 파이썬은 다른 언어에 비해서 구현상의 복잡함이 적은 편이지만 데이터 처리량이 많을 때는 꼭 메모리 제한을 고려해야함
• 일반적인 코딩 테스트 수준에서는 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야 한다는 점 정도만 기억하면 됨

📖 채점 환경

• 자신의 코드가 1초에 2,000만 번의 연산을 수행한다고 가정하고 문제를 풀면 실행 시간 제한에 안정적임

📖 구현 문제에 접근하는 방법

	구현 난이도	프로그램 실행 시간
파이썬	쉬운 편	긴 편
PyPy	쉬운 편	다소 짧은 편
C/C++	어려운 편	짧은 편

• 코딩 테스트에서 Pypy3를 선택한다면 파이썬3와 동일한 코드를 제출해서 실행 시간을 줄일 수 있음

✏️ 예제 4-1. 상하좌우

💻 입력 조건

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

💻 출력 조건

• 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력한다.

💻 입력 예시

5
R R R U D D

💻 출력 예시

3 4

📖 문제 해결

• 이러한 문제는 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션(simulation)유형으로 분류되며 구현이 중요한 대표적인 문제 유형이다.

# 1. 직접 작성한 풀이
n = int(input())
movement = list(map(str,input().split()))

map_ = [[0]*(n+1) for _ in range(n+1)]

now = [1,1]

for move in movement:
    
    if move == 'U' and now[1] != 1:
        now[1] -= 1
    
    elif move == 'D' and now[1] != n:
        now[1] += 1
    
    elif move == 'R' and now[0] != n:
        now[0] += 1
        
    elif move == 'L' and now[0] != 1:
        now[0] -= 1
    
    else:
        continue
        
print(now[1], now[0])

# 2. 책에 제시된 풀이
# N 입력받기
n = int(input())
x, y = 1, 1
plans = input().split()

# L, R, U, D에 따른 이동 방향
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
    # 이동 수행
    x, y = nx, ny

print(x, y)

✏️ 예제 4-2. 시각

💻 입력 조건

• 첫째 줄에 정수 N이 입력된다. (0 <= N <= 23)

💻 출력 조건

• 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.

💻 입력 예시

5

💻 출력 예시

11475

📖 문제 해결

• 모든 시각의 경우의 수를 고려한다고 하여도 경우의 수가 100,000개도 되지 않으므로 파이썬에서 문자열 연산을 이용해 3이 시각에 포함되어 있는지 확인해도 시간 제한 2초 안에 문제를 해결할 수 있다.
• 이러한 유형은 완전 탐색(Brute Forcing) 유형으로 분류되기도 한다. 완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법이다.
• 일반적으로 알고리즘 문제를 풀 때는 확인(탐색)해야 할 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색을 사용하면 적절하다.

# 1. 직접 작성한 풀이
n = int(input())

count = 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 time.count('3') >= 1:
                count += 1

print(count)

# 2. 책에 제시된 풀이
# H를 입력받기
h = int(input())

count = 0
for i in range(h + 1):
    for j in range(60):
        for k in range(60):
            # 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            if '3' in str(i) + str(j) + str(k):
                count += 1

print(count)