[이것이 코딩테스트다 with 파이썬] 3_구현(완전 탐색, 시뮬레이션)

구현

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정, 모든 범위의 코딩테스트 문제 유형을 포함하는 개념

1. Problem
2. Thinking
3. Solution

완전 탐색

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

시뮬레이션

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

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

• 파이썬에서의 리스트 크기에 따른 메모리 사용량

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

파이썬은 다른 언어에 비해서 구현상의 복잡함은 적은 편이지만 데이터 처리량이 많을 때는 메모리 제한을 고려해야한다.
리스트를 여러 개 선언하고, 그 중에서 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 풀 수 없게 되는 경우도 있다.

• 팁 : 파이썬 3.7 기준 1초에 2,000만번의 연산을 수행한다고 가정하고 문제를 풀자.
  • 시간 제한 1초, 데이터 개수가 100만 개인 문제의 경우
  • 일반적으로 시간복잡도가 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야한다.

다만 실무에서는 파이썬으로 프로그램 개발시, GPU를 연동하며, 반복적인 행렬 계산을 요구하는 복잡한 수학 문제를 풀 때는 C언어로 자가성된 파이썬 코어 소프트웨어가 동작한다. 따라서 항상 프로그램 동작 속도가 느리지 않다. 다만 알고리즘 코딩테스트 환경에서는 GPU 연산을 쓰는 경우가 거의 없기에 그러한 사항을 고려하지 않는다.

• 팁 : Pypy3를 지원하는 곳이 늘고 있다. 파이썬3의 문법을 그대로 지원하며, 대부분 파이썬3보다 실행속도가 빠르다.
  • Pypy3의 실행속도는 반복문이 많을 수록 파이썬3에 비해 빠른데, 이는 c/c++에 견줄만큼 빠르다.
  • 만약 Pypy3도 지원한다면 이를 이용하도록 하자

예제1. 시각(113 페이지) - 완전탐색

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오.

import sys
sys.stdin = open('input.txt', 'r')
num = int(sys.stdin.readline())

cnt = 0
for h in range(num + 1):
    for m in range(60):
        for s in range(60):
            if '3' in str(h)+str(m)+str(s):
                # print(str(h)+str(m)+str(s))
                cnt +=1
print(cnt)

• 시간복잡도 : 최대 O(24 * 60 * 60) : 반복문으로 완전탐색해도 상관 없음

예제2. 왕실의 나이트(115페이지) - 시뮬레이션

특정 시작점이 제시된 나이트의 위치 이동이 가능한 경우의 수를 구하시오. 체스판은 8 x 8 배열, 나이트의 이동 방법은 두가지.

1. 수평으로 두칸 이동한 뒤에 수직으로 한 칸 이동하기
2. 수직으로 두칸 이동한 뒤에 수평으로 한 칸 이동하기

import sys
sys.stdin = open('input.txt', 'r')
x, y = sys.stdin.readline()
x_base = {'a' : 1, 'b' : 2, 'c' : 3, 'd' : 4, 'e': 5, 'f': 6, 'g' : 7, 'h' : 8}
move_list = [(2,1), (2,-1), (-2,1), (-2,-1), (1,2), (1, -2), (-1, 2), (-1, -2)]
cnt = 0
for mx, my in move_list:
    if (1 <= x_base[x] + mx <= 8) and (1 <= int(y) + my <= 8):
        cnt +=1
print(cnt)