알고리즘/종만북19 06 - 보글 게임 (BOGGLE) 1. 주어진 칸에서 시작해서 특정 단어를 찾을 수 있는지 확인하는 문제. 시작점(y,x), 단어(word)를 주겠다는 것 예상 2. (y,x) 에서 8방향 탐색(갔던 곳을 다시 갈 수도 있으니 dfs라고 보긴 힘들듯) 3. 기저사례 -(y,x)에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 실패 -원하는 단어가 한 글자인 경우 성공 포인트 -매 탐색마다 글자의 맨 앞글자에만 의미 부여 4. 시간복잡도는 word의 길이 n에 대해 O(8^n) 5. bool hasWord(y,x,word) 형태의 재귀적 탐색 if board[y][x] != word[0] -> return false; if word.size() == 1 -> return true; for(int dir=0; dir5 || nx>5 || ny 2019. 6. 23. 06 - n개의 원소 중 m개를 고르는 모든 조합을 출력 본격적인 내용에 들어가기 전에 소개한 알고리즘이다. n개의 원소 중 3개를 고르는 것을 for문으로 작성한다면 3중 for문 형태가 될 것이다. for(int i=0; i 2019. 6. 23. 02 - 문제풀이 알고리즘 1. 읽고 이해 2. 익숙한 용어로 재정의(추상화) 3. 계획 (알고리즘과 자료구조 구상) 4. 계획 검증 5. 구현 6. 개선(회고) boj 문제 풀듯 답을 구해내는 것이 아니라서 어떤 방식으로 이 책을 공부해야 할 지 모르겠다. 일단 이 알고리즘에 따라서 문제 하나 하나 이해해 나갈 생각이다. 2019. 6. 23. 이전 1 2 3 4 5 다음