====== 애드혹 ====== * 애드혹은 알고리즘이나 풀이 기법의 이름이 아니라. 애드혹이라는 태그는, 어떤 정형화된 풀이기법을 적용할수 없는 문제에 붙여지는 태그이다. * 그냥 문제마다 그때그때 필요한 풀이방법을 떠올려서 푼다는 면에서는, 가장 원초적이고 근본적인 풀이 방법이기도 하다 * 하지만, 너무 사소하거나 단순하다는 이유로 따로 분류되지 않았을 뿐이지, 여러 문제에서 공통적으로 사용되는 테크닉이 아예 없는것은 아니다. 근데 진짜로 보통때는 이게 너무 당연해서 딱히 정리할 필요도 못느끼고 지나가는데, 가끔 뭔가 꼬이면 그 당연한게 안떠올라서 말리는 경우가 있다.. * 그래서 여기에서는 그런, 사소하고 당연하지만 종종 활용되는 내용들을 생각날때마다 모아보려고 한다. 모아놓고 보면 그 뒤에 다시 체계적으로 분류를 한다던가 하는 식으로 발전될 여지도 있을거 같고.. ===== 잡다 ===== * 1차원 직선위를 이동하면서 주어진 점들을 모두 방문해야 하는 문제. * 이동 거리를 최소화하는 것은, 당연히 한쪽 끝에서 다른 쪽 끝으로 한번 이동하면서 모든 점을 순서대로 방문하는 것이다. * 이 두 경로만 답이 될 가능성이 있는. 그래서 이 두 경로에 대해서만 계산해보면 되는 문제도 많다 * 자연수 n을 분할하는 방법 중, 곱이 최대가 되게 하려면, 2와 3만으로 분할하되 3을 최대한 많이 포함하도록 하면 된다. 코드는 [[ps:problems:boj:1437]] 참고 * [[https://oeis.org/A000792]] * 관련문제: [[ps:problems:boj:1437]], [[ps:problems:boj:31443]] ==== 정수론 ==== * x와 x+1은 서로소이다 (최대공약수가 1이다) => [[ps:problems:boj:13018]], [[ps:problems:boj:23074]] ==== 그래프 ==== * 지름이 가장 작은 트리는 성게 그래프 형태. 성게 그래프의 지름은 2이다. => {{myicon>g2}} [[ps:problems:boj:22967]] * RxC 크기의 그리드 그래프는 R>=2, C>=2 이고 노드 개수(=R*C)가 짝수일 때에만 해밀턴 사이클을 갖는다. => {{myicon>s3}} [[ps:problems:boj:11164]] * R과 C가 모두 3이상인 홀수일 경우 해밀턴 사이클을 갖지 않지만, 여기에서 아무 노드나 한개를 지워서 만든 그래프는 해밀턴 사이클을 갖는다 ==== 기타 ==== * 어떤 자연수의 집합이, 부분집합 합으로 1~N까지의 모든 수를 만들수 있게 하기 * 부분합으로 1~N까지를 모두 만들 수 있게 하려면? => 2진법을 이용한다. 1,2,4,8,... * 집합의 각 원소를 최대 d-1번씩 사용해서 만든 합이 1~N까지를 모두 만들 수 있게 하려면? => d진법을 이용한다. 1,d,d^2,d^3 * 수열의 부분배열의 합으로 1~N까지를 모두 만들 수 있게 하려면? => |S|/2 진법을 이용한다. * {{myicon>p5}}[[ps:problems:boj:15311]], {{myicon>p2}}[[ps:problems:boj:19568]] *