devbelly

문제 www.acmicpc.net/problem/1744 알고리즘 Greedy 풀이 수들이 주어졌을 때, 각 수들을 적절히 묶어 모든 수들의 합이 최대가 되도록 하는 문제입니다. 직관적인 그리디한 문제입니다. 두 수의 묶었을 때 가장 크기 위해서는 각 수가 첫번째로 큰 수, 두번째로 큰 수가 되어야합니다. 단 놓치기 쉬운 포인트 중 두 수를 묶는 조건입니다. 두 수가 음수면 무조건 양수로 만들 수 있으니 곱해나가는 것이 맞으나 두 수가 양수여도 두 수의 곱보다 합이 작을 경우 묶어서는 안됩니다. 예를 들어 수가 1, 1이라면 곱하는 것 대신 두 수를 더하는 것이 더 이득이기 때문입니다. 아래 코드는 양수와 음수를 구분하여 벡터에 넣은 후, 음수벡터의 크기가 홀수라면 1을 추가합니다. 양수 벡터는 수를 따..

문제 www.acmicpc.net/problem/18878 알고리즘 정렬 풀이 $i$번째 소부터 자신의 기호식품의 순위에 따라 가져 갈 때, 각 $i$번째 소마다 몇 개의 시리얼을 나누어 줄 수 있는지 묻는 문제입니다. 문제를 나이브하게 접근하면 처음부터 기호식품을 확인하며 나누어 주면 됩니다. 즉 1번째 소 뒤에 있는 $N-1$마리의 소들에 대해서 나누어주고, 2번째 소 뒤에 있는 $N-2$마리의 소들에 대해 나누어주는 식입니다. 이와 같이 시뮬레이션하면 요구하는 시간 복잡도는 $O(N^2)$ 이므로 시간 초과를 받게 됩니다. 뒤에 서있는 소부터 계산해보도록 합시다. 만약 $k$번째 소 이후에 몇마리가 가져갈 수 있는지를 다 계산을 하였다면 $k-1$번째 소는 이전의 상황과는 관계없이 무조건 자신이 가..

문제 www.acmicpc.net/problem/3392 알고리즘 Sweeping 문제 사각형을 구성하는 좌표들이 주어질 때, 모든 사각형의 면적을 구하는 문제입니다. 단 겹치는 좌표는 한 번만 계산해야 합니다. 각 직사각형을 두 개의 선분으로 분리한 후, x좌표를 기준으로 정렬합니다. 두개의 선분이란 직사각형을 놓았을 때 가장 왼쪽에 있는 선분, 가장 오른쪽에 있는 선분을 의미합니다. 예를 들어 직사각형을 이루는 좌표 (10,10), (20,20)을 받았다면 두 직선은 (10,10,20), (20,10,20)입니다. 앞에서부터 x좌표와 y좌표들입니다. 그리고 순차적으로 각 간선들을 살펴나가며 만약 왼쪽에 있는 선분이라면 그 선분이 가리키는 y좌표들을 업데이트해주고, 오른쪽에 있는 선분이라면 그 선분이 ..

함수사용의 조건 함수를 사용하기 위해선 함수정의와 원형을 제공하고 호출코드를 작성해야합니다. 라이브러리 함수를 사용한다면 이미 해당함수는 정의되어 컴파일이 되어있습니다. 그 원형을 제공하기 위해 우리는 헤더파일을 사용합니다. 함수원형의 필요성 함수의 정의안에 이미 원형이 포함되어 있는데 왜 우리는 굳이 정의와 원형을 나누어 제공을 해야할까요? 첫번째 이유를 이해하기 위해선 함수의 작동방식에 대해 이해할 필요가 있습니다. 호출된 함수는 자신의 리턴값을 CPU의 레지스터나 메모리에 복사하는 방식으로 값을 리턴합니다. 호출된 함수는 함수의 정의를 확인하여 해당 위치에 어떤 값을 리턴해야하는지 알게 됩니다. 그리고 호출한 함수는 함수의 원형을 확인하여 해당위치에서 어떤 값을 가져와야 하는지를 확인합니다. 해당 ..

문제 www.acmicpc.net/problem/18877 알고리즘 binary search 풀이 COWVID-19의 영향으로 사회적 거리두기를 실천하는 소들의 수가 주어집니다. 목초지의 범위가 주어지고 해당 범위안에 소를 배치하되, 가장 가까운 소의 거리가 최대가 되도록 하는 문제입니다. 소들을 임의의 거리 $d$로 배치할 수 있다면, $d$이하의 거리로 소를 배치할 수 있음이 자명합니다. 이분탐색으로 범위를 좁혀나갈 수 있다는 뜻과 동치입니다. $solve$함수는 거리$d$로 $N$마리의 소를 배치할 수 있는가를 리턴하는 함수입니다. $cur$은 가장 최근에 소를 배치한 지역을 의미합니다. 맨 처음에는 당연히 소를 배치하지 않았으므로 가장 작은 수로 초기화를 합니다. 다음의 $cur$이 될 수 있는 ..

포인터 포인터는 변수가 저장될 주소 값을 저장합니다. 선언할 때 에스터리스크(*) 을 사용하여 선언합니다. 변수가 저장될 주소 값만 저장하므로 어떤 데이터 타입을 가리키는지 또한 나타내야 합니다. #include using namespace std; int main() { int a = 10; double b = 10.0; int* ptr = &a; //주소값을 알려주는 &연산자 double* ptr2 = &b; cout

문제 www.acmicpc.net/problem/1517 알고리즘 펜윅트리 풀이 $N$제한이 50만이고 배열의 inversion들을 카운트 하는 문제입니다. 버블소트에서의 교환횟수는 inversion의 수와 동일합니다. inversion이란 $i$$A[j]$ 인 상황을 의미합니다. inversion을 찾으면 swap을 진행하고 inversion의 수가 하나 줄어들고 inversion이 0이 되면 소트가 종료됩니다. 이중포문을 통해 $O(N^2)$에 inversion의 수를 구할 수 있지만 $N$제한이 50만이므로 더 빠른 알고리즘이 필요합니다. 이 문제와 비슷하다고 생각되어 좌표압축 + 세그먼트 트리로 해결하여 풀었지만 좀더 간단하게 푸는 방법을 설명해드리겠습니다. inversion을 카운트 하기 위해선..

문제 www.acmicpc.net/problem/3584 알고리즘 DFS, LCA 풀이 그래프가 주어지고 두개의 정점이 주어졌을 때, LCA를 구하는 문제입니다. LCA를 나이브하게 처리하는 방법은 루트 정점을 구한 후 그 정점으로부터 다른정점들의 깊이를 구합니다. 그리고 처리해야할 두 정점 $u$,$v$를 입력받으면 두 정점이 같아질 때까지 깊이를 기준으로 하나씩 정점을 위로 보내면 됩니다. 깊이를 처리해야하는 시간복잡도는 $O(N)$이고 worst case 또한 모든 간선을 다 탐색하는 것이므로 $O(N)$입니다. 이 문제는 Testcase의 수가 적어 $O(T*N)$에 처리됩니다. 코드 #include #define rep(i,n) for(int i=0;i tc; while (tc--) { cin ..