C / C++ / Java : int, long long 등 종류에 따라 표현 범위가 달라짐
Python : 프로그래머가 직접 자료형을 지정할 필요가 없고 큰 수의 연산을 기본으로 지원
정수형 종류에 따른 범위
파이썬 리스트 크기
대체로 코딩 테스트에서는 128 ~ 512MB로 메모리를 제한
파이썬은 시스템 내부적으로 아래와 유사한 크기의 메모리 차지
크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 틀릴 수 있음
리스트 메모리 사용량
채점 환경
파이썬은 C / C++ 보다 동작 속도가 느리기에 C / C++ 보다 긴 수행 시간제한을 적용
시간제한과 데이터의 개수로 어느 정도의 시간 복잡도의 알고리즘으로 풀지 예측할 수 있어야 함
2020년 기준으로 Python 3.7 코드를 작성
1초에 2,000만 번의 연산을 수행한다고 가정하고 문제를 풀면 실행 시간제한에 안정적
예) 시간제한 : 1초, 데이터의 개수 : 100만 개 : O(NlogN) 이내의 알고리즘으로 문제를 풀어야 함
예제 : 상하좌우
문제
여행가 A는 N * N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 * 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위의 좌표는 (1, 1)이며, 가장 오른쪽 아래의 좌표는 (N, N)이다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있다. 이때, 여행가 A가 N * N 크기의 정사각형을 벗어나는 움직임은 무시된다. L : 왼쪽으로 한 칸 이동, R : 오른쪽으로 한 칸 이동, U : 위로 한 칸 이동, D : 아래로 한 칸 이동
입력 조건
첫째 줄에 공간의 크기를 나타내는 N이 주어짐 (1 <= N <= 100)
둘째 줄에 여행가 A가 이동할 계획서 내용이 주어짐 ( 1 <= 이동 횟수 <= 100)
출력 조건
첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력
해설
연산 횟수는 이동 횟수에 비례 : 시간 복잡도는 O(N)
일련의 명령에 따라 개체를 이동시킨다는 점에서 시뮬레이션 유형
n = int(input())
move = list(input().split())
pos = [1, 1]
for m in move:
if m == 'L' and pos[1] != 1:
pos[1] -= 1
elif m == 'R' and pos[1] != n:
pos[1] += 1
elif m == 'U' and pos[0] != 1:
pos[0] -= 1
elif m == 'D' and pos[0] != n:
pos[0] += 1
print(pos[0], pos[1])
예제 : 시각
문제
정수 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이 하나라도 포함되는 모든 경우의 수 출력
해설
모든 시각의 경우를 하나씩 모두 세서 쉽게 풀 수 있음
이런 유형은 완전 탐색 유형으로 분류
비효율적인 시간 복잡도 때문에 데이터 개수가 큰 경우 정상 작동하지 않을 수 있음
일반적으로 데이터 개수가 100만 개 이하일 때 완전 탐색을 사용하면 적절
n = int(input())
count = 0
for h in range(n + 1):
for m in range(60):
for s in range(60):
if '3' in str(h) + str(m) + str(s):
count += 1
print(count)
실전 문제 : 왕실의 나이트
문제
행복 왕국의 왕실 정원은 체스판과 같은 8 * 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있다. 나이트는 말을 타고 있기 때문에 이동할 때는 L자 형태로만 이동할 수 있고, 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다. 1. 수평으로 두 칸 이동한 뒤 수직으로 한 칸 이동하기 2. 수직으로 두 칸 이동한 뒤 수평으로 한 칸 이동하기 나이트의 위치가 주어졌을 때, 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램으로 작성하시오. 이때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현한다.
입력 조건
첫째 줄에 8 * 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 두 문자로 구성된 문자열 입력
출력 조건
첫째 줄에 나이트가 이동할 수 있는 경우의 수 출력
해설
책에서는ord를 사용하여 col을 int로 변경
pos = input()
move = [(-2, 1), (-2, -1), (2, 1), (2, -1), (1, 2), (-1, 2), (1, -2), (-1, -2)]
row = int(pos[1])
# col = int(ord(pos[0])) - int(ord('a')) + 1
for i, col in enumerate(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], start=1):
if col == pos[0]:
col = i
break
count = 0
for m in move:
if (1 <= col + m[0] <= 8) and (1 <= row + m[1] <= 8):
count += 1
print(count)
실전 문제 : 게임 개발
문제
현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 * 1 크기의 정사각형으로 이뤄진 N * M 크기의 직사각형으로, 각 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다. 맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간은 갈 수 없다. 캐릭터의 움직임을 나타내는 매뉴얼은 다음과 같다. 1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향 (반시계 방향으로 90도 회전)부터 차례대로 갈 곳을 정한다. 2. 캐릭터의 바로 왼쪽 방향에 아직 가보진 않은 칸이 존재한다면, 왼쪽방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다. 3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.
현민이는 위 과정을 반복적으로 수행하며 캐릭터의 움직임에 이상이 있는지 테스트하려고 한다. 매뉴얼에 따라 캐릭터를 이동시킨 뒤에 캐릭터가 방문한 수를 출력하는 프로그램을 만드시오.
입력 조건
첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력 (3 <= N, M <= 50)
둘째 줄에 게임 캐릭터가 있는 칸의 좌표 (A, B)와 바라보는 방향 d가 서로 공백으로 구분하여 주어짐
셋째 줄부터 맵이 육지인지 바다인지에 대한 정보가 주어짐, 맵의 외곽은 항상 바다
(처음 게임 캐릭터가 위치한 칸의 상태는 항상 육지)
방향 d : 북쪽(0), 동쪽(1), 남쪽(2), 서쪽(3) / 맵 상태 : 육지(0), 바다(1)
출력 조건
첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수를 출력
해설
맵의 외곽은 항상 바다로 구성되어 있음
풀이 방식은 다르지 않지만, 책과는 다르게 작성
n, m = map(int, input().split())
a, b, d = map(int, input().split())
game_map = [list(map(int, input().split())) for _ in range(m)]
move = [(-1, 0), (0, 1), (1, 0), (0, -1)]
count = 1
game_map[a][b] = 1
turn_time = 0
while True:
turn_time += 1
d = (d - 1) % 4
if game_map[a + move[d][0]][b + move[d][1]] == 0:
game_map[a + move[d][0]][b + move[d][1]] = 2
a += move[d][0]
b += move[d][1]
count += 1
turn_time = 0
if turn_time == 4 and game_map[a - move[d][0]][b - move[d][1]] != 1:
a -= move[d][0]
b -= move[d][1]
turn_time = 0
elif turn_time == 4 and game_map[a - move[d][0]][b - move[d][1]] == 1:
break
print(count)
