[백트래킹] 1987 알파벳
1. 알파벳 보드 b 생성 2. 알파벳 모음 alphabets 생성 - 이미 찾은 알파벳 확인용 3. 방향 설정 상 하 좌 우 dx = {-1, 1, 0, 0} dy = {0, 0, -1, 1} 이 보드의 (0, 0) 부터 시작해서, 상하좌우 매번 탐색하면서 - 보드의 바깥으로 가는 경우는 다시 돌아옴(백트랙). - 새로운 알파벳을 탐색했으면 기록하고, 다음 경로 탐색. - 이미 기록된 알파벳을 탐색했으면 백트랙. ex) 2 4 CAAB ADCB 이와 같은 알파벳 보드에서, 재귀함수가 어떻게 진행되는지 보자. C : 알파벳 체크. 1 상 : 없음, 돌아옴 2 하 : A 체크 2-1 상 : C가 이미 체크 되어있음, 돌아옴 2-2 하 : 없음, 돌아옴 2-3 좌 : 없음, 돌아옴 2-4 우 : D 체크 2..
2019. 6. 27.
GCD algorithm
GCD 알고리즘은 유클리드 호제법(Euclidean algorithm)으로도 불린다. 아래와 같은 원리를 이용하여 알고리즘을 짠다. a lemma: if a, b 가 정수이고 둘다 0이 아니면서 a = b*q + r을 만족하는 q, r 이 정수이면 then gcd(a, b) = gcd(b, r) 이를 코드에 그대로 옮기면, 최대공약수를 쉽게 구할 수 있다. 최소공배수는 A와 B를 곱하고, gcd(A, B)로 나누어 주면 구할 수 있다. 이를 이용하면 백준 문제를 쉽게 풀수있다. #include int main() { int a, b, r; scanf("%d %d", &a, &b); int A = a; int B = b; while (b != 0) { r = a % b; a = b; b = r; } pri..
2019. 6. 11.
9251 LCS
LCS 또한 교재에서 볼 수 있는 DP의 전형적인 문제이다. 길이가 각각 i, j인 문자열 x, y가 있다고 해보자. LCS(i, j) 는 문자열 x, y의 최장 공통 부분 수열(LCS)이라고 할 때, 다음과 같이 점화식을 세울 수 있다. LCS(i, j) = LCS(i-1, j-1) + 1 if x[i] == y[j] max( LCS(i-1, j), LCS(i, j-1) ) otherwise 이렇게 만들어놓고, i와 j에 따른 dynamic programming을 구현하기 위하여 d[i][j]를 만든다. 그리고 이 행렬을 잘 채워나가다가, 맨 마지막 오른쪽 부분 즉, d[i][j]가 우리가 원하는 LSC 값이다. #include #include #include using namespace std; in..
2019. 6. 9.
