완전 탐색8 시계 맞추기 시계 맞추기 4x4개의 격자 형태로 배치된 16개의 시계가 있다. 각 시계들은 3,6,9 혹은 12시를 가리키고 있는데 모든 시계가 12시가 되도록 만들려고 한다. 시계를 조작하는 방법은 10개로 구성된 스위치를 조작하는 방법 뿐이다. 각 스위치들은 최소 3개에서 여러개의 시계와 연결되어 있다. 스위치를 누를 때마다, 해당 스위치와 연결된 시계는 3시간씩 앞으로 움직인다. 모든 시계를 12시로 만드려면 최소한 스위치를 몇 번이나 눌러야 하는지 출력하라. 풀이 방법 문제를 있는 그대로 풀려고 하면 완전 탐색으로 불가능하다. 이유는 ? 완전 탐색을 사용하기 위해서는 스위치를 누르는 횟수의 모든 조합을 다 열거할 수 있어야 하는데, 각 스위치를 몇 번 누르는지는 상관없게 된다면 무한대의 조합이 나오게 된다. .. 2019. 11. 12. 게임판 덮기 - 완전 탐색 H x W 크기의 게임판이 있다. 게임판은 검은 칸과 흰 칸으로 구성된 격자다. 이 때, 흰 칸을 L자 모양의 블럭으로 빈 공간 없이 덮으려고 한다. 모두 덮을 수 있는 경우의 수를 구하시오. 문제에서 모든 경우의 수를 구하라고 했기 때문에 완전 탐색 해야한다. 완전 탐색을 구현하기 위해서는 문제를 먼저 조각 낸다. 블럭을 흰 칸에 놓는다. 더 이상 놓을 블럭이 없으면 1을 리턴한다. 최대한 단순하게 문제를 만들어 보았다. 위의 과정을 반복하면 모든 게임판을 덮을 수 있다. 기저사례 더 이상 놓을 블럭이 없으면 1을 리턴한다. 모든 공간을 다 덮었으면 1을 리턴한다. 알고리즘 설명 사용자로부터 게임판의 크기와 정보를 입력 받는다. 3으로 나눠떨어지지 않는다면 빈 공간을 모두 채울 수 없기 때문에 바로 종.. 2019. 10. 31. 조합 - 완전 탐색 조합: 일부 원소를 선택해 부분집합을 만드는 방법 n명의 학생들이 주어졌을 때, c명의 학생을 선택해서 만들 수 있는 모든 경우의 수를 구하시오. 간단한 완전 탐색 문제이다. 몇명의 학생을 선택하는지 값이 고정되어 있다면, 선택해야 하는 숫자 개수 만큼 반복문을 순회하면 완전 탐색을 할 수 있다. 선택해야 하는 숫자 개수가 늘어나면 늘어날수록 코드를 보기 힘들기 때문에 아래는 재귀 함수형태로 구현한 코드이다. 완전 탐색 문제는 재귀 함수를 이용하면 간단하게 작성 할 수 있다. void printPicked(vector& picked) { for(auto it : picked) { cout 2019. 10. 28. 소풍 - 완전 탐색 문제 n명의 학생들이 소풍 때 두 명씩 짝을 지어 행동하게 하려고 한다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어야 한다. 입력 값으로 학생의 수와 친한 친구 관계가 주어졌을 때, 학생들을 짝 지을 수 있는 방법의 수를 출력하시오. 짝 지을 수 있는 모든 방법의 수를 탐색하여 친한 친구 관계만 체크해서 해결 할 수 있다. 문제를 해결하는 포인트는 재귀적으로 두 학생을 짝 지어주는 경우의 수를 계산하는 동작 bool areFriends[10][10]; bool taken[10]; int countPairings(bool* taken, int n) { int ret = 0; int mark = -1; // 현재 .. 2019. 10. 28. 보글게임 - 완전 탐색 주어진 5x5 격자 위에 문자들이 있다. 최대 8방향으로 문자들을 연결해서 찾으려는 단어가 존재하는지 검사하라. 찾으려는 단어가 격자위에 존재하는지 검사하기 위해서는 완전 탐색 해야한다. 처음 시작 좌표 값과 단어를 입력으로 할 시에 격자 위에 존재하는지 검사하는 알고리즘을 구현. 각 문자마다 최대 8방향을 검사하기 때문에 격자가 커지면 커질수록 시간 복잡도는 기하급수적으로 상승하게 된다. (지수 복잡도) 완전 탐색을 재귀를 이용해서 구현했다. char board[5][5] = { {'U', 'R', 'L', 'P', 'M'}, {'X', 'P', 'R', 'E', 'T.. 2019. 10. 24. 카펫의 크기 구하기 - 완전 탐색 카펫의 전체 크기를 출력 갈색과 빨간색으로 이루어진 격자 모양의 카펫이 있다. 갈색의 개수와 빨간색의 개수가 주어졌을 때 카펫의 전체 크기를 맞추는 문제이다. 빨간색은 갈색으로 둘러 쌓여있는 구조이다. 빨간색을 갈색으로 둘러 쌓으려면 위/아래, 좌/우로 한줄씩 더 나와야 한다는 사실을 알 수 있다. 빨간색의 개수가 주어졌을 때 약수끼리의 곱(a*b)으로 표현 할 수 있다. 이 때 약수끼리의 곱을 행과 열의 길이로 대입해서 풀면 된다. 약수를 구하는 방식은 완전 탐색으로 0으로 나누어 떨어지는 숫자를 구하면 된다. 최적화를 하면 완전 탐색으로 자기 자신의 숫자까지 오는게 아니라 제곱근까지 오면 된다. 위에서 찾은 약수끼리의 곱으로 a행과 b열로 구성 되었을 때 둘러 쌓을 수 있는 최소 숫자를 구한 후 매개.. 2019. 10. 24. 이전 1 2 다음