초이의 끄적끄적

# 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="")

# 11055 가장 큰 증가 부분 수열 (실버2)

• 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.
• 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.
• 첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

import copy
N, A = int(input()), list(map(int, input().split()))

# DP[i] : i까지 왔을 때, 합의 최대
# 자기 자신이 제일 클 수도 있음 ex) 1000 100 10 1 -> 1000이 젤커
DP = copy.deepcopy(A) 

for i in range(1, N):
    for j in range(i):
        if A[i] > A[j]:
            DP[i] = max(A[i]+DP[j], DP[i])

#마지막이 최대라는 보장없음
#예시ㅣ -> print(DP) [1, 101, 3, 53, 113, 6, 11, 17, 24, 32]
print(max(DP))

+ (심화) 합이 가장 큰 증가 부분 수열의 합과 리스트 출력하기 

import copy
N, A = int(input()), list(map(int, input().split()))

# DP[i] : i까지 왔을 때, 합의 최대
# 자기 자신이 제일 클 수도 있음 ex) 1000 100 10 1 -> 1000이 젤커
DP = copy.deepcopy(A)
rev = [i for i in range(N)]
idx = 0

for i in range(1, N):
    for j in range(i):
        if A[i] > A[j] and DP[i] < A[i]+DP[j]:
            DP[i] = A[i]+DP[j]
            rev[i] = j
    if DP[idx] < DP[i]:
        idx = i

print(DP[idx])
while rev[idx] != idx:
    print(A[idx], sep=" ")
    idx = rev[idx]
print(A[idx])

// 결과값
10
1 100 2 50 60 3 5 6 7 8
113
60
50
2
1

+ 최장 증가 부분 수열(LIS : Longest Increasing Subsequence)

단계별풀기 - 브루트 포스

# 1436 영화감독 숌 (실버 5)

• Point. 1666 2666 3666 4666 5666 6666 이 아니고 6660 6661 6662 6663... 이다.
• 단순 반복문으로 666이 들어있는지 판별한다

n = int(input())
cnt = 0
six_n = 666
while True:
    if '666' in str(six_n):
        cnt += 1
    if cnt == n:
        print(six_n)
        break
    six_n += 1

# 1932 정수 삼각형 (실버1)

• 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
• Point. 모든 경로를 따지면 2^50 -> 이번생에 못푼다
• DP문제 (다음 상태를 저장하고 사용함)
  1. 상태를 정의한다 
  2. 점화식을 찾는다(구한다) 
  3. 시간복잡도를 계산한다
  4. 코딩한다(재귀 or 반복문 사용)

N = int(input())
# DP[i][j] : i,j 도착했을 때 최대값
# DP[i][j] = max(DP[i-1], DP[i-1][j]) + A[i][j]
A = [[0 for _ in range(N+1)] for i in range(N+1)]
DP = [[0 for _ in range(N+1)] for i in range(N+1)]

for i in range(1, N+1):
    tmp = list(map(int, input().split()))
    for j in range(1, i+1):
        A[i][j] = tmp[j-1]

for i in range(1, N+1):
    for j in range(1, i+1):
        DP[i][j] = max(DP[i-1][j-1], DP[i-1][j]) + A[i][j]

print(max(DP[-1]))

단계별풀기 - 브루트 포스

# 7568 덩치 (실버5)

• 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다.
• 여러분은 입력에 나열된 사람의 덩치 등수를 구해서 그 순서대로 첫 줄에 출력해야 한다. 단, 각 덩치 등수는 공백문자로 분리되어야 한다.
• point. 정렬 ㄴㄴ, 그냥 자기보다 크고 무거운(둘 다 큰) 사람이 몇 명인지 쟤서 자기 등수만 정하면 된다.

tc = int(input())
student_list = []

for _ in range(tc):
    x, y = map(int, input().split())
    student_list.append((x, y))

for i in student_list:
    rank = 1
    for j in student_list:
        if i[0] < j[0] and i[1] < j[1]:
                rank += 1
    print(rank, end = " ")