그냥 하는 노트와 메모장

* BOJ 2549 - 루빅의 사각형 [ 분류 - BFS(Bidirectional search)/ Backtracking ] 푸는 방법이 다소 다양해서 포스팅하고자 한다. 주어진 문제에서 보면 최대 7번까지만 움직여도 충분히 해결가능한 입력만 주어진다고 한다. 그렇다면 주어진 입력과 목표 4x4배열을 E와 S라고 하자. 그러면 E가 최대 3~4번, S가 최대 3~4번을 움직이면 그 안에 겹치는 교차지점이 반드시 생긴다. 특정 지점 4x4 배열 k에 대해 움직일 수 있는 가지수는 (4+4)*3이 된다. 즉 24 가지수가 나올 수 있는데, S또는 E에서 최대 7번을 움직이기 때문에 24^7의 경우의 수가 나오는데 이 값은 너무나 크다. 시간초과가 자명하다. 따라서 S,E가 교차지점까지 3~4번 이동하는 최대..

조금 짜증나는 백트랙킹 문제였다. unsigned long long 범위를 벗어나지 않기 위해서는 곱셈과정을 직접 구현해야 한다. 그렇지 않으면 10자리 수에 대한 세제곱 수를 구할 때, 무조건 overflow가 발생한다. 기본 아이디어는 다음과 같다. 일의 자리에 대해서 생각을 해보자. 어떤 한자리 수 세제곱을 하면 숫자 k(0

A에서 B로 갈 수 있는 모든 경로의 차의 수 최대값은 최대 유량으로 충분히 가능하다. 하지만 또 하나가 있는게 이 중에서도 한 경로만 사용했을 때, 최대값을 구해서 앞서 구한 모든 경로의 차의 최대값과 한 경로의 차의 수 최대값의 비율을 계산하라고 한다. 단순 최대유량 문제만 내기엔 부족했나보다. 편의상 A에서 B로 가는 모든 경로의 차의 수 최대값을 X라고 하고, 한 경로의 차의 수 최대값을 Y라고하면 구하고자 하는 값은 Y/X가 된다. X는 단순 최대 유량으로 구해서 계산하며 Y는 backtracking으로 정의하여 계산한다. Y를 구할 때, 기저 사례는 B를 만날 때까지고, 재귀를 돌며 방문했던 정점은 다시 방문하지 않도록 한다. 재귀의 반환값은 현재 정점에서 방문 가능한 정점 중에서 차를 최대한..

완전 그래프에 관한 문제다. 크기가 K인 그래프 내의 clique(클릭) 중에서 구성된 정점의 번호가 제일 작은 것을 찾으려고 한다. 입력 데이터의 규모가 작으니 하나하나 접근해나가며 완전 그래프를 만들 수 있는지 없는지 판단하는 백트래킹 재귀 함수를 만들었다. 재귀 호출하기 전에, for문으로 번호가 작은 친구부터 탐색하도록 한다. 마찬가지로 재귀 내에서도 번호가 작은 친구를 찾도록 유도하여 구성된 정점의 번호가 작은 클릭을 찾을 수 있다. 재귀 함수의 기저 사례는 현재 구성된 완전 그래프의 크기 p와 찾아야 하는 완전 그래프의 크기 k와 같으면 true를 반환..