알고리즘/baekjoon
20210209_코테공부
jungeun960
2021. 2. 9. 11:55
- 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)
반응형