본문 바로가기

알고리즘225

06 - 게임판 덮기 BOARDCOVER 1. 흰 칸에 4가지 타입의 ㄴ모양 블럭을 둬서 꽉 채우는 경우의 수를 출력. 2. 현재 위치 기준으로 fx[4][3] = { {0,0,1}, {0,0,1}, {0,1,1}, {0,1,1} }; fy[4][3] = { {0,1,1}, {0,1,0}, {0,0,1}, {1,0,1} }; 에 블럭을 두도록 설계하자. 3.map[][]에 문자 입력받고, mark[][]에 블럭을 둔 곳을 표시하도록 함. (입력받을 때 검정색 부분도 마크하도록 함) map의 제일 좌상단을 기준으로 x가 1증가하는 방향(x범위 초과 시 y 1증가, x = 0)으로 탐색 int go(int cy, int cx) //게임판을 덮는 경우의 수를 출력하는 재귀함수 기저: - 모든 블럭이 마크됐으면 게임판이 덮어 진 것으로 return 1.. 2019. 6. 25.
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.

티스토리툴바