무식하게 풀기
무식하게 풀기(Brute force) - 4. 시계 맞추기
문제 : Synchronizing Clocks (난이도 中) 문제 분석 위 문제는 앞서 푼 문제같이 무작정 재귀 호출을 할 수 있는 케이스가 아니다. 최적화 과정이 필요하다. 스위치를 누르는 데 있어 순서가 필요없다는 것을 주목하자. 또한 스위치를 4번 누르면 제자리로 돌아온다. 따라서 4^10 = 1,048,576 번 검사를 하면 된다. 구현 using namespace std; const int INF = 9999, SWITHCHES = 10, CLOCKS = 16; //스위치가 연결된 경우 'x', 아닌 경우 '.' const char linked[SWITHCHES][CLOCKS + 1] = { "xxx.............", "...x...x.x.x....", "....x.....x...xx"..
무식하게 풀기(Brute force) - 3. 게임판 덮기
문제 : 게임판 덮기 (난이도 下) 위 문제를 '무식하게' 풀어보자. 문제 분석 L자 모형을 회전해서 나오는 모양들은 다음과 같다. 게임판 중 맨 좌측 상단 빈칸부터 재귀 호출을 시작한다. A, B, C, D 네타입의 도형을 넣으면서 재귀를 수행하면 된다. 이 문제는 답이 항상 0인 사례가 존재한다. 1. 높이가 1인 경우 2. 빈칸 (흰색 칸)이 3의 배수가 아닌 경우 기저사례는 모든 칸을 다 채웠을 때이다. 구현 using namespace std; //주어진 칸을 덮을 수 있는 네가지 방법. //상대적인 위치 (dy, dx) //별표시를 시작 위치로 잡았다. const int cover_type[4][3][2] = { {{0,0},{1,0},{1,1}}, //A {{0,0},{0,1},{1,0}},..
무식하게 풀기(Brute force) - 2. 소풍
문제 : 소풍 (난이도 下) 위 문제를 '무식하게' 풀어보자. 문제 분석 예제 입력을 보면 친구 관계가 순서쌍으로 주어진다. 2번째 케이스를 예로 들면 다음과 같이 표현할 수 있다. (0, 1), (1, 2), (2, 3), (3, 0), (0, 2), (1, 3) 이를 4x4 Matrix로 친구 관계를 나타내면 다음과 같다. 0 1 2 3 0 Friend Friend Friend 1 Friend Friend Friend 2 Friend Friend Friend 3 Friend Friend Friend 이 문제는 '중복'을 방지하는 것이 핵심이다. 1. (0, 1)과 (1, 0)는 이 문제에서 같은 순서쌍이다. 2. 와 은 같은 경우이다. 위 중복을 한 번에 해결하는 법은 항상 번호가 가장 빠른 학생부터..
무식하게 풀기(Brute force) - 1. 보글 게임
리뷰 중인 책 ( 알고리즘 문제 해결전략 1권 )에선 무식하게 푸는 것은 '완전 탐색'이라 한다. 완전 탐색을 하는데 있어 책에서 소개하는 전략은 재귀 호출의 활용이다. 재귀 호출 or 재귀 함수란? 자신이 수행할 작업을 유사한 형태로 여러 조각으로 쪼갠 뒤 그 중 한 조각을 실행하고, 나머지를 자기 자신을 호출해 실행하는 함수이다. 이 때 '더이상 쪼개지지 않는' 최소한 작업에 도달했을 때 사례를 기저 사례(base case)라고 한다. 필자는 재귀 호출을 이용한 문제 풀이는 기저 사례를 세우는 것이 핵심이라 생각한다. 예제 : 보글 문제 (난이도 下) 위 문제를 '무식하게' 재귀 호출을 이용해 풀어보고자 한다. 문제의 분할 첫번째 조각을 찾는 것은 간단하다. 전체 칸에서 단어의 시작 위치만 반환하면 ..