✅ Coding Test
🎈 구현 1051 숫자 정사각형
NXM 크기의 직사각형이 주어지고 각 칸에는 한 자리 숫자가 적혀있다. 이 직사각형에서 꼭짓점에 쓰여있는 수가 모두 같은 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하는 문제. 이때 정사각형은 열, 행에 모두 평행해야 한다.
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(n)]
size = min(n, m)
answer = 0
for i in range(m):
for j in range(n):
for k in range(size):
if i + k < m and j + k < n:
if graph[j][i] == graph[j+k][i] == graph[j][i+k] == graph[j+k][i+k]:
answer = max(answer, (k+1)**2)
print(answer)< 코드 해설 >
1. n,m과 직사각형을 리스트 형태로 입력을 받는다.
2. 만들 수 있는 정사각형의 최대 크기는 n, m 중 더 작은 값이므로 size 변수로 저장을 해두고 for문으로 0 ~ size-1까지 정사각형 범위를 찾는다.
3. i+k는 가로보다 작아야 하고, j+k는 세로보다 작아야 하며 정사각형 범위내 꼭짓점에 위치한 숫자가 같다면 answer를 (k+1)**2으로 갱신해준다.
🎈 그리디 1105 팔
L과 R이 주어지고 L보다 크거나 같고, R보다 작거나 같은 자연수 중 8이 가장 적게 들어있는 8의 개수를 구하는 문제.
예시로 L, R이 각각 1, 10이면 내부는 1~10 이고 8이 없는 1,2,3,4 등이 존재하므로 답은 0이다.
import sys
input = sys.stdin.readline
L,R = input().split()
answer = 0
if len(L) != len(R):
print(answer)
else:
for i in range(len(L)):
if L[i] == R[i]:
if L[i] == '8':
answer += 1
else:
break
print(answer)< 코드 해설 >
숫자로 접근해보니 빈 리스트를 2개 생성해 리스트 내 원소 마다 count('8')을 수행했지만 메모리 초과가 발생했다. 메모리 제한이 512MB여도 리스트가 최대 20억까지 생성할 수 있어서 메모리 부분을 신경써주어야 한다.
따라서 숫자가 아닌 문자로 각 자리 수를 확인하는 방법을 선택했다.
1. L과 R의 숫자 개수가 다르다면 8이 아닌 숫자가 무조건 포함되어 있는 것이므로 0을 출력한다.
2. 숫자 개수가 같다면 L의 숫자와 R의 숫자를 각각 비교하며 8인 경우에만 +1을 진행하고 숫자가 다르다면 다음 자리 수로 넘어간다.
3. 구해야 하는 값이 최소 8의 개수이므로 해당 방식이 가능하지만 최대 8의 개수를 구하는데 있어선 해당 조건보다는 해당 자리 수 내 8을 채울 수 있는 방법을 선택하는 것이 더 빠르다.
🎈 DP 11048 이동하기
NXM 크기의 미로에 가장 왼쪽 윗 방 (1,1)부터 시작해 가장 오른쪽 아랫 방인 (N, M)까지 이동하며 각 칸에 놓여진 사탕을 모두 챙겨갈 때 가져올 수 있는 사탕의 최댓값을 구하는 문제.
이동 시 현재 r,c에 있다면 (r+1,c), (r+1,c+1), (r,c+1)로 이동할 수 있다.
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
graph = []
for _ in range(n):
graph.append([0] + list(map(int, input().split())))
dp = [[0] * (m+1)] + graph
for i in range(1, n+1):
for j in range(1, m+1):
dp[i][j] = max(dp[i][j], dp[i][j]+dp[i-1][j], dp[i][j]+dp[i][j-1], dp[i][j]+dp[i-1][j-1])
print(dp[n][m])< 코드 해설 >
1. dp테이블만 제대로 구축한다면 금방 해결하는 문제.
2. 주어진 범위를 생각해 DP테이블은 미로크기인 (NXM)보다 가로 세로가 1씩 더 크게 생성해준다.
3. 이후 2중 for문으로 i,j의 위치를 지정해주고 주어진 3가지 이동 방향마다 값을 max로 갱신해주면 되는 문제.
