2020. 12. 28. 17:50ㆍ알고리즘/알고리즘 문제 [medium]
brute-force 핵심함수
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
const int dx[8] = { -1, -1, -1, 1, 1, 1, 0, 0};
const int dy[8] = { -1, 0, 1, -1, 0, 1, -1, 1};
bool hasWord(int y, int x, const string& word)
{
if(!inRange(y,x)) return false;
if(board[y][x] != word[0]) return false;
if(word.size() == 1) return true;
for(int direction = 0; direction < 8; ++direction)
{
int nextY = y + dy[direction], nextX = x + dx[direction];
if(hasWord(nextY, nextX, word.substr(1)))
return true;
}
return false;
}
//알고리즘 문제해결전략 152p |
cs |
1. 어떤 방식으로 풀어야 하는지
8장의 동적계획법과 관련된 문제임을 알고 메모이제이션을 이용하여 풀어야겠다고 생각하였다.
2. 함수를 어떻게 구현할 것 인지
brute-force 와 마찬가지로 핵심 함수는 위처럼 단어를 게임판에서
순서대로 나열 할 수 있는지 판단할때
단어를 부분으로 나누어 첫 알파벳의 일치여부만 검사해야한다.
게임판 좌표 y, x 에서 단어의 i 번째 인덱스에서 한번 함수가 실행되었는지를 알려주는 배열을 따로 생성하면
다음부턴 따로 함수를 수행하지 않아도 true 인지 false인지 바로 판단 할 수 있다.
"게임판에서의 현재위치 그리고 단어 word가 주어질 때 해당 단어를 이 칸에서부터 시작해서 찾을 수 있는가?"
3. 메모이제이션을 어떻게 표현할 것 인지 <- 틀린이유
|
1
2
|
std::vector<std::vector<int>> alphabet(26);
|
cs |
alphabet[ word[i] - 65 ][j]
이렇게 표현하려고 했던이유
1. 해당 문제의 최악의 경우는 단어의 알파벳이 게임판에 포함되지 않을 경우라고 생각하여
size()이 0일때 바로 false라는 답을 내 시간을 최소한으로 하려고했다. (for문 최대 10번이면끝)
2. 좌표 + 메모이제이션 을 한꺼번에 표현하려고 했다.
alphabet[ 'A' - 65 ][1] = (y*10 + x) + bit *100;
alphabet[][]을 100으로 나누면 bit만 남게된다.
bit를 xor 연산하면 단어가 해당 좌표에서 i번째 알파벳에서의 함수 실행 여부를 알 수있다.
(A^B == A - B )
(0 0 0 0 0 0 0 1 1 0 => 1번째 와 2번째는 이미 실행되었으므로 스킵)
이런 메모이제이션을 통해 brute-force에 현재 좌표에서 이미 이 연산을 수행했으므로 스킵한다는
기저 조건을 추가하고 함수를 실행할때 함수를 실행했음을 기록하면 문제를 풀 수 있을 것 이다.
4. 더 빨리 풀수 있는지
- 단어를 분할하여 풀기 -> 3으로 표현하여 size()가 가장 작은 알파벳으로 분할하면 더 빨리 풀 수 있을 것이다.
- 3으로 표현하여 첫 알파벳으로부터 단어의 다음 알파벳 배열을 이진 탐색
하여 주변에 존재하는지 따지면 더 빨리 풀 수 있을 것이라 생각 했지만
이진 탐색시 최소 구간을 정하는데 최대 5번, 첫 알파벳 주위에 있는지를 알아보는데 최대 3줄 즉 15번 총 20번의 연산이 필요하여
더욱 느릴 수 있다.
bool memo[y][x][10];
처럼 표현을 간결하게 했었으면 구현하기 더 쉬웠을 것이다.
간결하게 표현하고 복잡한 표현일지라도 구현할 수 있도록 연습하자
algospot.com :: BOGGLE
보글 게임 문제 정보 문제 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어
algospot.com
-알고리즘 문제해결전략 150p
'알고리즘 > 알고리즘 문제 [medium]' 카테고리의 다른 글
| [동적 계획법] ASYMTILING 비대칭 타일링 (0) | 2021.01.10 |
|---|---|
| [동적 계획법] Longest Increasing Sequence, JLIS 합친 LIS (0) | 2021.01.08 |
| [동적 계획법, 그래프] JUMPGAME 외발 뛰기 (0) | 2021.01.06 |
| [분할 정복] FANMEETING 팬미팅 (0) | 2021.01.05 |
| [분할 정복, 스위핑, 스택, 상호 배타적 집합] FENCE 울타리 잘라내기 (0) | 2021.01.04 |