N번째 피보나치 수를 구한 후 그 수가 짝수이면 YES, 아닐경우 NO를 출력하는 프로그램을 구성하시오.
| JUMPGAME_문제 (0) | 2015.12.28 |
|---|---|
| FIBONACCI_알고리즘 (0) | 2015.12.28 |
| BOGGLEGAME_알고리즘_3 (0) | 2015.12.28 |
| BOGGLEGAME_알고리즘_2 (0) | 2015.12.28 |
| BOGGLEGAME_알고리즘_1 (0) | 2015.12.28 |
3. 중첩으로 저장하는 부분 제외하기
생각
기본적인 원리는 [BOGGLEGAME_알고리즘_1]과 동일하다.
하지만 조금 깊게 생각해보면 8방향을 검사할때 중첩되는 부분이 있다는 것을 알 수 있다.
예를 들면
0 1 2
3 4 5
6 7 8
일때
이런식으로 갈수 있는 방향을 트리로 정리할 수 있다.
이때 트리의 깊이가 단어의 길이라고 생각하면 붉은 원 두개가 서로 같은 정보를 가지고 있는 것을 알 수 있다.
이 알고리즘의 핵심은 이 붉은 부분을 검사한 후 그 결과값을 저장해 놓는다는 것에 있다.
즉, 단어의 4번째 글자를 찾기 위해 재귀적으로 검사할때
0번으로 들어가서 검사할 수 있는 위 3개(1, 3, 4)의 각 요소에 찾는 알파벳이 없다면
더이상 4번째 글자를 찾기 위해 0번으로 들어가 일일이 확인해 볼 필요가 없다는 것이다.
위의 아이디어를 구현하기위해 필요한 코드는 의외로 간단하다.
기존의 코드에 캐시를 저장할 수 있는 배열을 만들어놓고, 위와 같은 상황이 되면 -1로 표시하는 부분만 구현하면 된다.
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 | // BOGGLEGAME_2 #include <iostream> #include <string.h> static const int BOGGLE_MAX = 5; static const int WORD_MAX = 10; int g_ArrX[] = { -1, 0, 1, 1, 1, 0, -1, -1 }; int g_ArrY[] = { -1, -1, -1, 0, 1, 1, 1, 0 }; char* g_Boggle[BOGGLE_MAX]; char* g_WordsArr[WORD_MAX]; // 기록 배열 char g_CacheArr[BOGGLE_MAX][BOGGLE_MAX][WORD_MAX] = {0,}; int g_StringLen = 0; int g_CurCharNum = 0; int g_CurWordNum = 0; // 해당 좌표에 전달되는 문자가 있는지 검사 bool f(int y, int x, char CurChar) { // 기저사례 1 x또는 y가 범위 밖이라면 false if (x < 0 || y < 0) return false; // 기저사례 1 x또는 y가 범위 밖이라면 false if (x >= BOGGLE_MAX || y >= BOGGLE_MAX) return false; // 기저사례 2 찾으려는 문자가 '\0' 이거나 // 문자열의 길이와 같으면 문자열을 찾은것이므로 true if (CurChar == '\0' || g_CurCharNum > g_StringLen) return true; // 찾으려고 하는 좌표가 이미 -1 이라면 여긴 이전에 찾았던 곳이므로 패스 if (g_CacheArr[y][x][g_CurCharNum] == -1) return false; if (g_Boggle[y][x] == CurChar) { if (g_StringLen == 1){ // 기저사례 3 문자를 찾았는데 문자열의 // 길이가 1이면 곧 찾는 문자열이므로 true return true; } // 문자를 찾았으면 문자인덱스를 1증가 ++g_CurCharNum; // 현 인덱스를 중심으로 다음 문자를 8방향 검사 for (int i = 0; i < 8; i++) { // 모두 찾으면 true if (f( (y + g_ArrY[i]), // y좌표 (x + g_ArrX[i]), // x좌표 g_WordsArr[g_CurWordNum][g_CurCharNum]) ) { return true; } } // 문자를 못찾았으면 문자인덱스 1감소 --g_CurCharNum; // 8방향 모두 아니라면 현재 좌표에서 다음문자를 찾을 방법이 없기때문에 -1 g_CacheArr[y][x][g_CurCharNum] = -1; } // 현 인덱스의 문자가 찾는 문자가 아니면 false return false; } int main() { // 테스트 케이스 int testCase = 0; int stringCount = 0; int temp = 0; for (int i = 0; i < BOGGLE_MAX; i++) { g_Boggle[i] = new char[BOGGLE_MAX + 1](); } for (int i = 0; i < WORD_MAX; i++) { g_WordsArr[i] = new char[WORD_MAX + 1](); } scanf("%d", &testCase); while (testCase--){ g_CurWordNum = 0; // 보글게임판 5 x 5 입력 for (int i = 0; i < BOGGLE_MAX; i++) { scanf("%s", g_Boggle[i]); } // 확인하려는 문자열 갯수 입력 scanf("%d", &stringCount); temp = stringCount; // 확인하려는 문자열 입력 ENTER 구분 for (int i = 0; i < stringCount; i++) { scanf("%s", g_WordsArr[i]); } while (stringCount--){ bool isYes = false; // 단어를 찾는 루프를 돌 때마다 캐시를 -1로 초기화해준다. memset(g_CacheArr, 0, sizeof(g_CacheArr)); // 현재 검사하려고 하는 문자열의 길이 저장 g_StringLen = (int)strlen((const char*)g_WordsArr[g_CurWordNum]); // g_CurCharNum = 현재 검사하려고하는 문자 인덱스 예) ABCDE에서 C 면 2 g_CurCharNum = 0; for (int y = 0; y < BOGGLE_MAX; y++) { for (int x = 0; x < BOGGLE_MAX; x++) { // y, x인덱스와 찾으려는 문자열의 문자를 f에 넘김 // 있으면 YES if ( f(y, x, g_WordsArr[g_CurWordNum][g_CurCharNum])) { printf("%s YES\n", g_WordsArr[g_CurWordNum++]); isYes = true; // 루프를 빠져나간다. break; // 루프를 빠져나간다. } } if (isYes) // 루프를 빠져나간다.. break; // 루프를 빠져나간다.. } // 4, 4까지 돌았는데 없으면 NO if (!isYes) { printf("%s NO\n", g_WordsArr[g_CurWordNum++]); } } } // 메모리 해제 for (int i = 0; i < BOGGLE_MAX; i++) { delete []g_Boggle[i]; g_Boggle[i] = NULL; } for (int i = 0; i < WORD_MAX; i++) { delete[]g_WordsArr[i]; g_WordsArr[i] = NULL; } return 0; } | cs |
총 4곳이 수정되었다.(main 1 + 함수 3)
1. 첫번째는 캐시 배열을 선언하는 부분
1 2 | // 캐시 배열 char g_CacheArr[BOGGLE_MAX][BOGGLE_MAX][WORD_MAX] = {0,}; | cs |
2. 둘째는 현재 좌표가 -1(이전에 찾아본 곳)일 경우 false를 반환하는 부분
1 2 3 | // 찾으려고 하는 좌표가 이미 -1 이라면 여긴 이전에 찾았던 곳이므로 패스 if (g_CacheArr[y][x][g_CurCharNum] == -1) return false; | cs |
3. 셋째는 8방향이 모두 아니라면 -1로 마킹하는 부분이다.
1 2 | // 8방향 모두 아니라면 현재 좌표에서 다음문자를 찾을 방법이 없기때문에 -1 g_CacheArr[y][x][g_CurCharNum] = -1; | cs |
4. 넷째는 캐시 배열을 초기화 하는 부분이다.(main)
while(StringCount--) 이후에 추가된다.
1 2 | // 단어를 찾는 루프를 돌 때마다 캐시를 -1로 초기화해준다. memset(g_CacheArr, 0, sizeof(g_CacheArr)); | cs |
결과
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | 1 AAAAA AAAAA AAAAA AAAAA AAAAA 5 AAAAAAAAAAD AAAAAAAAAAD AAAAAAAAAAD AAAAAAAAAAD AAAAAAD AAAAAAAAAAD NO AAAAAAAAAAD NO AAAAAAAAAAD NO AAAAAAAAAAD NO AAAAAAD NO | cs |
| FIBONACCI_알고리즘 (0) | 2015.12.28 |
|---|---|
| FIBONACCI_문제 (0) | 2015.12.28 |
| BOGGLEGAME_알고리즘_2 (0) | 2015.12.28 |
| BOGGLEGAME_알고리즘_1 (0) | 2015.12.28 |
| BOGGLEGAME_문제 (0) | 2015.12.28 |
2. 배열에 표시하기
생각
1단계. 25 x 25의 배열 선언
2단계. 각 원소에 인접함의 유무를 저장함
ex) 4 x 4 일때
A A A S -> 0 1 2 3
A E E A -> 4 5 6 7
A Y E A -> 8 9 10 11
A A A A -> 12 13 14 15
이면
arr[15][15] =
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 1 4 5
1 0 2 4 5 6
2 1 3 5 6 7
3 2 6 7
4 0 1 5 8 9
5 0 1 2 4 6 8 9 10
6 1 2 3 5 7 9 10 11
7 2 3 6 10 11
8 4 5 9 12 13
9 4 5 6 8 10 12 13 14
10 5 6 7 9 11 13 14 15
11 6 7 10 14 15
12 8 9 13
13 8 9 10 12 14
14 9 10 11 13 15
15 10 11 14
3단계. 찾고자하는 문자열을 위의 인덱스로 변환후 저장한다.
ex) YES -> 9 6 3
YEA -> 9 10 11
4단계. 저장한 숫자 배열(편의상 YES배열 )을 순회하며 arr[ i ][ i+1 ]에 YES의 (i+1)번째 요소가 들어있는지 검사한다. 있으면 i++ 후 i가 숫자 배열의 끝일때까지 반복
ex) YES -> ( arr[YES[i] ][ YES[i+1] ] == 6)
문제
처음 위 알고리즘을 생각했을땐 2차원 배열을 가장먼저 만들어 놓기만 하면 모든 답을 처리할수 있기에 시간적인 문제를 해결할 수 있을 것이라 생각했다. 때문에 정답이라고 생각했는데 다음과 같은 경우에 답을 찾지 못하는 문제가 있다.
A A A A -> 0 1 2 3
A E E E -> 4 5 6 7
A Y A A -> 8 9 10 11
A A A A -> 12 13 14 15
일때 E E E Y의 경우 숫자배열에 5 6 5 9 로 저장되어야 함이 맞다. 하지만 위의 알고리즘은 숫자 배열을 만들때
8방향 탐색을 하지 않는다. 때문에 7의 E를 저장하고 다음 요소인 Y를 찾을 수 없어 오답처리된다.
다른 방법을 찾아야겠다.
| FIBONACCI_문제 (0) | 2015.12.28 |
|---|---|
| BOGGLEGAME_알고리즘_3 (0) | 2015.12.28 |
| BOGGLEGAME_알고리즘_1 (0) | 2015.12.28 |
| BOGGLEGAME_문제 (0) | 2015.12.28 |
| ZEROONE_알고리즘 (0) | 2015.12.28 |