20210209_코테공부

# 2167 2차원 배열의 합 (브론즈1)

• 2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다.
• 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(i ≤ x, j ≤ y).
• point. 누적합 사용

N,M = map(int,input().split())
A = [list(map(int, input().split())) for _ in range(N)]
# DP[i][j] = (1,1) 부터 (i,j) 까지의 부분합
DP = [[0 for i in range(M+1)] for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, M+1): #대각선 중복되므로 빼줘야됨
        DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + A[i-1][j-1]

for _ in range(int(input())):
    i, j, x, y = map(int, input().split())
    print(DP[x][y] - DP[i-1][y] - DP[x][j-1] + DP[i-1][j-1])

 

 

*  1차원 배열 누적합

A = [i for i in range(10)]
print(A)
for i in range(1, 10):
    A[i] = A[i-1] + A[i]
print(A)

// 결과값
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 3, 6, 10, 15, 21, 28, 36, 45]

• 3까지 합은 -> 6
• 5부터 9까지의 합 -> 9누적합 - (5-1)누적합 = 45 - 10 = 35
• => i부터 j까지의 합은 DP[j] - DP[i-1]

 

단계별풀기 - 정렬

# 2750 수 정렬하기 (브론즈1)

• 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
• 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 

n = int(input())
num = [int(input()) for _ in range(n)]
sort_n = sorted(num)

for i in range(n):
    print(sort_n[i])

 

# 2751 수 정렬하기2 (실버5)

• 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다
• 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 
• point. 수 정렬하기 코드 제출하면 시간 초과남 -> input()으로 입력받아 메모리 초과가 날 경우, import sys sys.stdin.readline() 사용

import sys
n = int(sys.stdin.readline())
num = [int(sys.stdin.readline()) for _ in range(n)]
sort_n = sorted(num)

for i in range(n):
    print(sort_n[i])

 

# 10989 수 정렬하기3 (실버5)

• 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
• 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다.  
• 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
• point. 수 정렬하기2로 코드로 제출하면 메모리 초과 뜸 -> array를 사용한다

import sys
n = int(sys.stdin.readline())
b = [0]*10001 #수가 10,000보다 작거나 같은 자연수이기 때문
for i in range(n):
    b[int(sys.stdin.readline())] += 1  #같은 수 갯수 세기
for i in range(10001):
    if b[i] != 0:
        for j in range(b[i]): #같은 수 갯수만큼 출력하기
            print(i)