승형님의 블로그

https://www.acmicpc.net/problem/16565 16565번: N포커 첫째 줄에 N장의 카드를 뽑았을 때, 플레이어가 이기는 경우의 수를 10,007로 나눈 나머지를 출력하라. www.acmicpc.net 요약 트럼프 카드를 이용하여 새로운 규칙의 게임을 만든다. 52장의 카드 중 N장을 선택했을 때, 이 중 포카드 (four of a kind)를 만들 수 있다면 플레이어의 승리이다. 포카드는 "같은 숫자를 가진, 다른 문양의 4장의 카드" 이다. 주어진 N에 대하여 플레이어가 승리하는 경우의 수를 출력한다. 1. 하나의 포카드 쌍은 4개의 카드를 포함한다. 따라서, $N$개의 카드를 선택하였을 때는 최대 $N/4$개의 포카드 쌍을 형성할 수 있다. N개의 카드 중 하나 이상의 포카드..

https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 요약 짝수 N개의 점이 속해있는 집합 P가 주어진다. 이때, 벡터 매칭은 집합 P 속의 한 점에서 다른 점을 잇는 벡터의 집합이다. 모든 점은 한 번만 사용된다. 벡터 매칭에 있는 모든 벡터의 합의 길이의 최솟값을 구한다. 1. 벡터의 길이는 다음과 같다. $\sqrt{( x_2 - x_1)^2 + ( y_2 - y_1)^2}$ 또한, 벡터 합의 길이는 위 식에서 $x_2, y_2$ 자리..

정렬(Sorting)은 항목들을 특정한 순서(예: 오름차순, 내림차순)에 따라 배열하는 것을 말한다. 데이터를 정렬하여 보관하면, 데이터의 검색(Searching)이 용이해 문제의 복잡도를 크게 감소시킬 수 있다. 데이터를 정렬하는 방법에는 여러 가지가 있는데, 병합 정렬(Merge Sort)는 분할 정복(Divide-and_Conquer)의 방식으로 데이터를 정렬하며 O(N log N)의 시간 복잡도로 수행된다. 우선 배열의 처음 인덱스와 끝 인덱스의 절반을 기준으로 배열의 왼쪽 영역과 오른쪽 영역을 나누어준다. 이렇게 배열의 크기를 계속해서 분할하여 각각의 크기가 1이 되었을 때, 합치는 작업을 수행하며 정렬을 진행한다. 데이터를 분할하는 과정은 다음과 같이 재귀적으로 이루어진다. // C/C++로 ..

C++ STL에서는 O(NlogN)의 시간 복잡도로 데이터를 우선순위에 따라 삽입, 삭제할 수 있는 우선순위 큐(Priority Queue)에 대한 Container를 제공한다. 제공하는 Containter를 사용하기 위해서는 헤더 파일 선언이 필요하다. Priority_queue의 선언은 다음과 같이 이루어진다. #include // TypeName Type, PQ를 구성할 기본 container, PQ 내부의 우선순위를 결정하는 구조체 Compare std::priority_queue PQ; 첫 번째 인자에는 우선순위 큐를 구성할 데이터의 형(Type)을 넣어준다. 이때, 사용자가 정의한 구조체 또한 넣어줄 수 있다. 두 번째 인자에는 우선순위 큐를 구현하기 위한 Container의 종류를 넣어준다...

C++ STL에서는 O(NlogN)의 시간 복잡도를 보장하며 원소를 정렬하는 std::sort 함수, std::stable_sort 함수를 제공한다. 제공하는 함수를 사용하기 위해서는 헤더 파일 선언이 필요하다. sort 함수는 3개의 인자를 가진다. #include // typename TYPE void std::sort(TYPE start, TYPE end, Bool compare_func); 첫 번째 인자로는 정렬을 시작할 주소값 (start 부터 시작), 두 번째 인자로는 정렬을 마칠 주소값 (end 전 까지 정렬), 세 번째 인자로는 정렬의 기준이 되는 함수가 들어간다. [start, end)의 범위를 정렬. 세 번째 인자를 비우고 함수를 호출할 경우 기본값으로 오름차순 정렬 함수가 들어간다. ..