1. 문제 18113번: 그르다 김가놈 (acmicpc.net) 18113번: 그르다 김가놈 첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ 106, 1 ≤ K, M ≤ 109, N, K, M은 정수) 두 번째 줄부터 김밥의 길이 L이 N개 주어진다. www.acmicpc.net 2. 풀이 문제를 보면 김밥의 길이가 k보다 큰 경우, 양쪽을 균일하게 k씩 자른다 하지만 2k보다 짧은 경우, 한쪽 k만 자른다. k보다 작거나 같은 경우 김밥은 그냥 폐기한다 김밥 길이를 받을 때, L > k인 경우, L 2k일때, L-2k를 리스트에 저장한다 L == 2k일때는 문제에서 아무런 언급이 없기..
1. 문제 14609번: 구분구적법 (Large) (acmicpc.net) 14609번: 구분구적법 (Large) 첫 번째 줄에는 다항함수의 차수를 나타내는 양의 정수 K(1 ≤ K ≤ 10) 가 주어진다. 두 번째 줄에는 최고차항부터 내림차순으로 각 항의 계수를 나타내는 정수 ci (0 ≤ ci ≤ 10, 1 ≤ c1 ≤ 10) 가 www.acmicpc.net 2. 풀이 실제 적분값과 근삿값이 일치하게 만드는 epslion을 찾는다 그러면 실제 적분값을 먼저 구해야겠지 최대 10차 다항함수까지로 제한되어있고 다항함수 적분 방법도 힌트로 나와있다 그러면 c0xk+c1xk−1+...+ck를 적분하면 된다 그러면 $$\frac{c_{0}x^{k+1}}{k+1} + \..
1. 문제1 1072번: 게임 (acmicpc.net) 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 2. 풀이1 탐색범위는 x+1부터 충분히 큰 수까지.. x가 제한이 10의 9제곱인데.. 이는 입력으로 주어지는 x가 10의 9제곱이지 가능한 제한이 10의 9제곱이라는 뜻은 아니다. 그래서 대충 10의 18제곱까지 탐색하도록 범위를 잡았다 그리고 절대로 지지 않는다고 했기 때문에... x 기준으로 현재 x+k를 잡았다면... y값은 y+k로 바뀌겠지 그리고 그때 변화된 승률도 (y+k)*100//(..
1. parametric search 이분 탐색을 응용하여, "최적화 문제"를 "결정 문제(decision problem)"로 바꿔서 문제를 푸는 알고리즘 최적화 문제는 예를 들면 다음과 같다. "f(x) = True가 되는 x의 최댓값을 구하세요" 이를 결정 문제로 바꾸면 다음과 같을 것이다. "어떤 x에서 f(x) = True인가?" 가능한 모든 x에 대해 f(x)가 True인지, False인지 검사한다면, 최적화 문제를 결정 문제의 집합으로 바꾸어 해결할 수 있을 것이다. 모든 결정 문제의 값 중에서 True인 최댓값을 구하면 되니까 하지만 모든 결정문제를 다 해결하는 것은 당연히 비효율적 그러나 어떤 조건을 만족한다면, 위 과정을 효율적으로 해결할 수 있다. x1 < x2이고, f(x2) = Tr..
1. 문제 2428번: 표절 (acmicpc.net) 2428번: 표절 첫째 줄에 제출한 솔루션의 개수 N이 주어진다. 둘째 줄에는 각 솔루션 파일의 크기 size(F1), size(F2), ..., size(FN)이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ size(Fi) ≤ 100,000,000) 솔루션 파일의 크기는 정수이 www.acmicpc.net 2. 풀이 F1,F2,...,Fn이 주어질때, Fi=0.9∗Fj인 (Fi,Fj)의 개수를 구하는 문제 조건이 2개가 있는데.. 사실 Fi=0.9∗Fj을 만족하는 최대 인덱스 j를 찾는다 그러면 Fi,Fi+1, ..., Fi,Fj까지가..
내 블로그 - 관리자 홈 전환 |
Q
Q
|
---|---|
새 글 쓰기 |
W
W
|
글 수정 (권한 있는 경우) |
E
E
|
---|---|
댓글 영역으로 이동 |
C
C
|
이 페이지의 URL 복사 |
S
S
|
---|---|
맨 위로 이동 |
T
T
|
티스토리 홈 이동 |
H
H
|
단축키 안내 |
Shift + /
⇧ + /
|
* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.