20210210_코테공부

# 1915 가장 큰 정사각형 (골드5)

• n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.
• Point. DP로 풀기... .. 노이해... 다시 풀어보기

N, M = map(int, input().split())
A = [[0 for _ in range(M+1)] for i in range(N+1)]
# DP[i][j] = i,j까지 왔을 때, 가장 큰 정사각형의 한 변의 길이
DP = [[0 for _ in range(M+1)] for i in range(N+1)]

for i in range(N):
    for idx, j in enumerate(list(map(int, list(input())))):
        A[i+1][idx+1] = j
mx =0
for i in range(1, N+1):
    for j in range(1, M+1):
        if A[i][j]:
            DP[i][j] = min(DP[i-1][j], DP[i-1][j-1], DP[i][j-1])+1

print(max([max(i) for i in DP]) ** 2)

 

단계별풀기 - 정렬

# 2108 통계학 (실버4)

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

• input()으로 하면 시간초과 남 import sys sys.stdin.readline() 사용
• 데이터 개수 세기 collections 모듈의 Counter 클래스 사용 ( 참고 )

from collections import Counter
import sys
N = int(sys.stdin.readline())
N_list = [int(sys.stdin.readline()) for _ in range(N)]
N_sort = sorted(N_list)

print(round(sum(N_list)/N)) # 반올림함수 round
print(N_sort[int(N/2)])
N_count = Counter(N_sort).most_common(2) #데이터 개수가 많은 순으로 정렬된 배열 리턴
if N > 1: # 데이터가 하나일 경우에는 out of range 뜨니까
    if N_count[0][1] == N_count[1][1]:
        print(N_count[1][0])
    else:
        print(N_count[0][0])
else:
    print(N_list[0])
print(N_sort[-1]-N_sort[0])

 

# 1427 소트인사이드 (실버5)

• 첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.

n = input()
n_list = []
for i in n:
    n_list.append(i)

n_sort = sorted(n_list, reverse=True)
for i in n_sort:
    print(i,end="")