1. 문제 2261번: 가장 가까운 두 점 (acmicpc.net) 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 아래 문제 풀이를 보고 작성하였다. *[C/C++] 백준 2261번 - 가장 가까운 두 점 (라인 스위핑) :: 코딩 공부 일지 (tistory.com) 2. 풀이 set과 mindist의 정의가 다음과 같을때 큰 틀은 다음과 같다. set: 고려될 수 있는 점집합 mindist: 현재까지 가장 짧은 두점 거리 1) x축 기준으로 정렬 2) 첫 두점을 기준으로 m..

1. 문제 11444번: 피보나치 수 6 (acmicpc.net) 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 풀이 이 문제는 엄청나게 큰 n번째 피보나치 수를 구하는 문제이며 피보나치 수의 성질을 잘 알고 있어야 풀 수 있는 문제이다. 피보나치 수의 점화식은 다음과 같다 f_n = f_n-1 + f_n-2, (f0 = 0, f1 = 1) 이 식을 다음과 같이 열벡터로나타낼 수 있다. C_n은 원소의 합이 f_n이 되는 열벡터이다. C_n = { {f_n-2}, {f_n-1}} 그리고 이 식을 풀어쓰면 다음과 같은 식이 나오게 된다. C_n = { {f_n-2}, {f_n-2 +..

1. 문제 6549번: 히스토그램에서 가장 큰 직사각형 (acmicpc.net) 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 2. 분할정복 직사각형이 있는 경우의 수는 한 부분문제에서 총 3가지의 경우 로 나눌 수 있다. 1. 왼쪽~ 중간 쪽에 최대인 직사각형이 있는 경우 2. 중간~오른쪽 쪽에 최대인 직사각형이 있는 경우 3. 중간을 포함하여 위의 두 영역에 걸쳐 있는 경우 직관적으로 한 문제당 왼쪽, 오른쪽 두개의 부분문제로 나뉘어지고, 중간을 ..

1. 11050 11050번: 이항 계수 1 (acmicpc.net) 파스칼 삼각형을 사용해 문제를 해결 하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include using namespace std; int cache[11][12]; void initial() { for(int i = 0; i N>>K; initial(); coutK; initial(); cout 임의의 원소a와 임의의 연산?에 대해 a?x = a 이 되게하는 x ) (역원 => 임의의 원소 a와 임의의 연산 ?에 대해 a?x = 0 이 되게하는 x ) 어떤 수를 a로 나눈다 == 어떤 수를 a의 곱셈에 대한 역원과 곱한다 => 만약 a의 곱셈에 대한 역원이 존재하지 않으면..

1. 문제 11054번: 가장 긴 바이토닉 부분 수열 (acmicpc.net) 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 2. 풀이 한 지점에서 왼쪽에선 증가하고 오른쪽에선 감소하는 가장 긴 수열의 길이를 찾는 문제이다. 각 지점에서 시작하는 수열중 가장 긴 증가(감소) 수열의 길이를 찾아서 두 수열의 길이를 더한 뒤 -1 을 해주면 답이된다(중심이되는 지점은 중복되므로 -1해줘야한다.) 즉 이문제는 lis를 두번 구하면 된다는 것이다. 한지점에서의 오른쪽 감소 수열은 다음과 같이 두가지 부분 문제로 이루어져있다. 1. 만약..

1. 문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 2. 최적 부분 구조(optimal substructure) 최장 공통 부분 수열에서는 시작점이 중요하다 다음과 같은 함수를 만들어보자 solve(aidx, bidx) = a 문자열은 aidx 에서 , b문자열은 bidx에서 시작해서 각각 문자열 끝까지 만들어질 수 잇는 최장 공통 부분 수열의 최대 길이 임의의 문자열 a와 b가 있고 이들의 ..