애드혹
- 애드혹은 알고리즘이나 풀이 기법의 이름이 아니라. 애드혹이라는 태그는, 어떤 정형화된 풀이기법을 적용할수 없는 문제에 붙여지는 태그이다.
- 그냥 문제마다 그때그때 필요한 풀이방법을 떠올려서 푼다는 면에서는, 가장 원초적이고 근본적인 풀이 방법이기도 하다
- 하지만, 너무 사소하거나 단순하다는 이유로 따로 분류되지 않았을 뿐이지, 여러 문제에서 공통적으로 사용되는 테크닉이 아예 없는것은 아니다. 근데 진짜로 보통때는 이게 너무 당연해서 딱히 정리할 필요도 못느끼고 지나가는데, 가끔 뭔가 꼬이면 그 당연한게 안떠올라서 말리는 경우가 있다..
- 그래서 여기에서는 그런, 사소하고 당연하지만 종종 활용되는 내용들을 생각날때마다 모아보려고 한다. 모아놓고 보면 그 뒤에 다시 체계적으로 분류를 한다던가 하는 식으로 발전될 여지도 있을거 같고..
잡다
- 1차원 직선위를 이동하면서 주어진 점들을 모두 방문해야 하는 문제.
- 이동 거리를 최소화하는 것은, 당연히 한쪽 끝에서 다른 쪽 끝으로 한번 이동하면서 모든 점을 순서대로 방문하는 것이다.
- 이 두 경로만 답이 될 가능성이 있는. 그래서 이 두 경로에 대해서만 계산해보면 되는 문제도 많다
- 자연수 n을 분할하는 방법 중, 곱이 최대가 되게 하려면, 2와 3만으로 분할하되 3을 최대한 많이 포함하도록 하면 된다. 코드는 1437 참고
정수론
그래프
- 지름이 가장 작은 트리는 성게 그래프 형태. 성게 그래프의 지름은 2이다. ⇒
구름다리 - RxC 크기의 그리드 그래프는 R>=2, C>=2 이고 노드 개수(=R*C)가 짝수일 때에만 해밀턴 사이클을 갖는다. ⇒
Traveling Cellsperson- R과 C가 모두 3이상인 홀수일 경우 해밀턴 사이클을 갖지 않지만, 여기에서 아무 노드나 한개를 지워서 만든 그래프는 해밀턴 사이클을 갖는다
