[백트래킹] 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.
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.
