본문 바로가기

Coding Test15

[Math] 11051: 이항 계수2 https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 1. 풀이 a. dp로 푸는 방법 (파스칼 삼각형) b. factorial 함수를 사용하는 방법 2. 코드 a. from sys import * # 입력 N, K = map(int, stdin.readline().rstrip().split()) """ 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 ... """ # 문제 조건 dp = [[0] for _ in range(1002)] # 시작 dp[1].append(1) # 파스칼 삼각형 for i in rang.. 2021. 7. 8.
[Two Pointer] 2003: 수 들의 합2 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 1. 코드 from sys import * # 입력 N, M = map(int, stdin.readline().rstrip().split()) seq = list(map(int, stdin.readline().rstrip().split())) # Two Pointer start = 0 end = 0 total = 0 answer = 0 # Two Point.. 2021. 7. 7.
[Algorithm] 에라토스테네스의 체 from sys import * # 최대 숫자 MAX = 1000001 # 소수인지 아닌지 판별하는 배열 CHECK = [True] * MAX # 1은 소수가 아니고, 2는 소수이다. CHECK[1] = False CHECK[2] = True # 소수를 저장하는 자료구조 set PRIME = set() for i in range(2, MAX): if CHECK[i]: # 소수 PRIME.add(i) # 소수가 아닌 숫자에 대해서 false 처리 for j in range(i * 2, MAX, i): CHECK[j] = False 2021. 7. 7.
[Math, Eratosthenes' sieve] 9020: 골드바흐의 추측 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 1. 코드 from sys import * # 문제 조건 MAX = 1000001 # 소수인지 아닌지 판별하는 배열 CHECK = [True] * MAX # 1은 소수가 아니고, 2는 소수이다. CHECK[1] = False CHECK[2] = True # 소수를 담는 자료구조 set PRIME = set() # 2 ~ MAX까지 소수 판별 for i in range(2, .. 2021. 7. 7.

티스토리툴바