재귀함수3 여행하는 외판원 문제 여행하는 외판원 문제 여행하는 외판원 문제는 유명한 최적화 문제 중 하나다. 최적화 문제는 여러 개의 답 중에서 최소값 또는 최대값을 찾는 문제이기에 완전 탐색 방법으로 풀이 할 수 있다. 다만 도시의 개수가 제한적이라는 조건이 붙는다. 도시의 개수가 매우 크다면 다른 방식으로 풀이해야 한다. 이번 문제는 도시의 개수가 2 2019. 11. 1. 게임판 덮기 - 완전 탐색 H x W 크기의 게임판이 있다. 게임판은 검은 칸과 흰 칸으로 구성된 격자다. 이 때, 흰 칸을 L자 모양의 블럭으로 빈 공간 없이 덮으려고 한다. 모두 덮을 수 있는 경우의 수를 구하시오. 문제에서 모든 경우의 수를 구하라고 했기 때문에 완전 탐색 해야한다. 완전 탐색을 구현하기 위해서는 문제를 먼저 조각 낸다. 블럭을 흰 칸에 놓는다. 더 이상 놓을 블럭이 없으면 1을 리턴한다. 최대한 단순하게 문제를 만들어 보았다. 위의 과정을 반복하면 모든 게임판을 덮을 수 있다. 기저사례 더 이상 놓을 블럭이 없으면 1을 리턴한다. 모든 공간을 다 덮었으면 1을 리턴한다. 알고리즘 설명 사용자로부터 게임판의 크기와 정보를 입력 받는다. 3으로 나눠떨어지지 않는다면 빈 공간을 모두 채울 수 없기 때문에 바로 종.. 2019. 10. 31. 보글게임 - 완전 탐색 주어진 5x5 격자 위에 문자들이 있다. 최대 8방향으로 문자들을 연결해서 찾으려는 단어가 존재하는지 검사하라. 찾으려는 단어가 격자위에 존재하는지 검사하기 위해서는 완전 탐색 해야한다. 처음 시작 좌표 값과 단어를 입력으로 할 시에 격자 위에 존재하는지 검사하는 알고리즘을 구현. 각 문자마다 최대 8방향을 검사하기 때문에 격자가 커지면 커질수록 시간 복잡도는 기하급수적으로 상승하게 된다. (지수 복잡도) 완전 탐색을 재귀를 이용해서 구현했다. char board[5][5] = { {'U', 'R', 'L', 'P', 'M'}, {'X', 'P', 'R', 'E', 'T.. 2019. 10. 24. 이전 1 다음