'bits/stdc++.h' 모든 표준 라이브러리가 포함된 헤더입니다. 이 헤더는 표준 헤더가 아니기에 GCC가 아닌 컴파일러로 컴파일이 되지 않습니만 백준 온라인 저지, 코드포스, ACM-ICPC 등 GCC를 컴파일러로 사용하는 대회에서 유용하게 사용할 수 있습니다. 맥은 보통 Xcode를 설치하기에 컴파일러로 LLVM을 사용하는데 이는 따로 설정을 통하여 'bits/stdc++.h' 헤더를 사용할 수 있습니다. (2022.08.20 수정) 1. g++ --version 커맨드를 이용하여 InstalledDir의 설치 경로 확인합니다. 2. 1번 결과 경로의 한단계 상위폴더에 있는 include 폴더로 파인더를 열어줍니다. 예를 들어, 1번 결과의 경로가 '/Application/Xcode.app/u..
1787번: 문자열의 주기 예측 - KMP, DP 문자열이 주어질 때 이 문자열의 모든 접두사에 대하여 추정할 수 있는 주기 중 가장 긴 것의 길이의 합을 출력하는 문제이다.KMP에서 다뤘던 광고문제나 Slot Machines문제에서 비슷한 유형을 다뤄본 적이 있다.문자열에서 주기를 구하는 방법은 S - pi[S-1]로 계산하였다.그러나 이 때의 답은 S-pi[S-1]값이 작을 때였고, 우리가 구해야할 답은 S-pi[S-1]의 값이 클 때가 되어야한다.즉 pi는 접미사도 되고 접두사도 되는 최대 길이이기에 최소 길이를 구하여야 한다는 것을 알 수 있다. ababa의 pi[S-1]은 3이다. S[:3], S[2:]이 모두 aba로 같기 때문이라는 것을 알 수 있다.이 때 aba의 pi값은 1이 되는데,S[..
1017번: 소수 쌍 - 이분 매칭 짝수 개의 수 리스트가 주어질 때, 2개씩 짝지었을 때의 합이 모두 소수가 되는 경우의첫 번째 수와 연결 되어 있는 수를 오름차순으로 출력하는 문제이다. 입력에 주어지는 수들은 중복되지 않으므로 1이 두 번 주어질 수는 없다.소수는 2보다 클 경우 모두 홀수이므로 합이 홀수가 될 때의 경우를 생각해보자.홀수는 짝수와 홀수가 더해질 때만이 홀수가 되므로 2개의 그룹으로 나눠지고이들을 짝지어 이어주는, 즉 이분매칭 문제가 되게 된다.짝수 그룹, 홀수 그룹으로 나누고 이들을 잇는 간선들은 합이 소수가 될 경우 이어준다.이 그래프의 최대 매칭이 N/2일 경우에 답으로 가능할 경우인 것을 알 수 있다. 약간의 함정이 숨어있는 문제다. 출력해야할 부분은 첫 번째 수와 연결되어 있..
안녕하세요 hellogaon입니다.한양대학교 에리카 프로그래밍 대회, 2018 HEPC - MAVEN의 출제 및 검수를 진행하였습니다!끝난 지 한참 지난 대회지만 추후 많은 분들이 대회를 준비하실 때 많은 분들에게 도움이 되고자 풀이 및 코드를 작성하였습니다. A - 15725번: 다항함수의 미분첫째 줄에 최대 일차 일변수 다항식이 주어질 때 주어진 다항식을 미분한 결과를 출력하는 문제이다.최대 일차 일변수 다항식이기에 상수항만 있을 수도 있으므로x가 있을 경우 계수가 있다면 그 계수를, 없다면 부호에 따라 1 또는 -1을 출력하며x가 없을 경우 0을 출력하면 되는 문제이다. B - 15726번: 이칙연산세 수가 주어질 때 사이에 곱셈 기호, 나눗셈 기호를 한 번씩 사용하여 만든 식 중 가장 큰 값을 출..
14961번: Untangling Chain 원점에서 시작하여 N번 동안 L의 거리를 이동한 뒤 왼쪽 또는 오른쪽으로 회전을 반복한다.회전하는 방향이 고정되어 있을 때 교차하지 않도록 이동거리를 정해주는 문제이다. 접근 방법은 다음과 같다.현재 이동하고 있는 방향이 오른쪽일 때 다음에는 위쪽, 또는 아래쪽으로 이동하여야한다.위쪽과 아래쪽으로 갈 때 방해 받지 않으려면 지금까지 이전에 진행했던 경로 중 가장 오른쪽에 있는 좌표보다 1 더 간다면 이동하는데에 문제가 없을 것이다.위 또는 아래로 이동한 뒤에도 오른쪽 또는 왼쪽으로 이동하는 것이 방해받지 않으려면위로 간다면 지금까지 이전에 진행했던 경로 중 가장 위에 있는 좌표보다 1 더,아래로 간다면 아래에 있는 좌표보다 1 더 간다면 문제가 없을 것이다.이..
14959번: Slot Machines - KMP N개의 수들이 주어질 때, 이 수열은 처음 K개의 원소를 제외하고 주기 P를 갖는다.이 때, K+P가 최소가 되는, 같다면 P가 최소가 되는 K와 P를 출력하는 문제이다. 주기를 찾는 문제는 KMP에서 광고문제로 설명한 적이 있다.문자열을 이루고 있는 최소의 주기를 구하는 방법은 문자열의 길이가 S일 때, S - pi[S-1]이다.이를 이용하려면 먼저 pi배열을 구하여야 한다.pi[i] = N[...i]의 접미사도 되고 접두사도 되는 문자열의 최대 길이로주기가 시작되는 부분을 알 수 없으므로 모든 N에 대하여 확인해봐야하므로 시간복잡도가 O(N^2)이다.그러나 여기서 N개의 수를 뒤집어서 생각한다면 주기의 시작부분은 처음부터가 되게 되며단 한번의 pi배열..
14955번: How Many to Be Happy? - 최소 컷 N개의 정점과 M개의 간선으로 이루어진 그래프에서 각 간선이 MST가 포함되기 위해제거해야하는 간선의 최소 개수의 합을 구하는 문제이다. 접근 방법은 다음과 같다.u와 v를 잇는 가중치가 c인 간선이 있을 때 이 때 이 간선이 MST가 아니라는 것은가중치가 c미만인 간선들로 u와 v가 이어져 있다는 것이다.이제 이 간선을 MST에 포함되게 하려면 가중치가 c미만인 간선들로 u와 v가 이어져있지 않게 해야한다는 뜻이 되며이는 각각의 간선을 용량이 1인 간선으로 보았을 때가장 작은 유량으로 u와 v가 각각 다른 집합에 속하도록 나누는, 즉 최소 컷을 구하는 문제가 된다. 매 간선을 보며 그 간선의 비용보다 작은 간선으로만 용량이 1인 간선으로..
13560번: 축구게임 - 탐욕법 하나의 팀은 다른 모든 팀과 정확히 한 번씩만 경기를 하고 무승부는 없을 때의 팀별 승수가 주어졌을 때유효한 조합인 지 파악하는 문제이다. O(N)에 푸는 방법은 아래와 같다. Fulkerson Chen Anstee theorem: i는 1부터 N까지 일 때, ΣA[i] ≤ i*(i-1)/2 이며, ΣA[i] = N*(N-1)/2 이여야한다. 위를 만족할 경우 1, 아닐 경우 -1을 출력해주면 되는 문제이다. 또한 탐욕법으로 O(N^2)에 풀 수도 있는데매 단계마다 승수가 가장 높은 팀은 승수가 낮은 팀에 대해 이긴다라는 방법을 선택하여모든 팀에 대하여 진행해주면 풀 수 있는 문제이다.
1222번: 홍준 프로그래밍 대회 - 수학 N개의 수가 주어질 때 이들 중 X로 나누어 떨어지는 수의 개수 * X의 값의 최대값을 출력하는 문제이다.N은 최대 200,000이며 수의 최대값은 2,000,000으로 N^2으로 보는 방법은 당연히 시간 초과이다.풀이는 이러하다. 2,000,000여개를 담을 수 있는 배열 A을 만든 뒤 이 배열에는 수들의 개수를 담는다.그 다음 1 ~ 2,000,000를 보며 지금 보는 수를 X라 할 때 A[X], A[2*X], A[3*X] ... 의 값을 더한다면X로 나누어 떨어지는 수의 개수가 된다.이들 중 2이상인 수에 대해 X와 곱한 값이 가장 큰 값을 출력하면 풀 수 있는 문제이다. 이 때의 시간복잡도를 계산해보면 2,000,000개의 모든 수를 X가 1일 때는 2,..
A - Palindromic Twist 문자열 s가 주어질 때 이 문자열의 모든 글자를 그 글자 알파벳의 다음 알파벳, 또는 이전 알파벳으로 바꾸어펠린드롬을 만들 수 있는 지 없는 지 판단하는 문제이다.간단한 구현 문제인데 실제 대회에선 많은 Hack이 나온 문제 중 하나였다.이는 a와 z같은 양 끝 알파벳은 각각 b, y로만 바뀔 수 있으며 서로 바뀌지는 않는다. (순환 형태가 아니다.)이에 대한 조건만 조심하면 쉽게 풀 수 있는 문제이다. B - Numbers on the Chessboard 정해진 규칙에 따라 n*n 체스보드를 채워나갈 때 x열 y행에 적혀있는 숫자는 무엇인지 출력하는 문제이다.n이 짝수일 때 홀수일 때, x + y가 짝수일 때 홀수일 때로 나누어 수식을 세워 계산하였다.예를 들어 ..