문제 해결 알고리즘 기초/완전 탐색 (10) 썸네일형 리스트형 [프로그래머스] 수식 최대화 - 완전 탐색 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 수식 최대화(링크) 풀이 연산자는 *, +, - 세 개이므로 가능한 우선 순위는 총 6가지이다. 주어지는 문자열은 길이 100 이하로 모두 검사하기 쉬운 분량이므로 가능한 우선 순위를 모두 확인한다. 나는 "*+-" 문자열 변수를 선언한 뒤 next_permutation() 으로 가능한 순서를 모두 나열하게 했다. 처음엔 주어진 문자열 그대로 우선순위에 따라 계산하고 결과를 다시 문자열에 붙여 넣는 방식으로 하나하나 계산하려 했다. 과정이 명시적이고 문자열 출력을 통해 진행 상황을 확인하기 쉽지만 문자열을 고쳐 넣는 과정이 포함되어서 불필요하게 코드가 길어진다. 또한, 중간에 음의 부호를 가지는 숫자를 삽입할 때 부호가 아닌 연산자와 구분하기.. [프로그래머스] 카펫 - 완전 탐색 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 카펫(링크) 풀이 (갈색 격자 + 노랑 격자 = 총 격자 개수) 이므로 가능한 가로 격자, 세로 격자의 개수들을 알 수 있다. 여기에 ((가로 격자 - 2) * (세로 격자 - 2) = 노랑 격자) 라는 사실을 추가하면 정답이 되는 가로, 세로 격자의 개수를 알 수 있다. C++ 코드 #include #include using namespace std; vector solution(int brown, int yellow) { int check, total = brown + yellow; vector ans(2); for (int h = 3; h [프로그래머스] 소수 찾기 - 완전 탐색, 재귀, 소수 판별법 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 소수 찾기(링크) 풀이 주어지는 숫자 문자열의 숫자들 각각에 대해 사용하거나 사용하지 않은 경우로 정답 후보를 만들어 소수 판별을 진행한다. 재귀 함수의 입력으로 숫자 문자열을 받으면 앞에서 숫자를 하나 떼어내 소수 후보 문자열에 이어 붙여 소수인지 판별하고, 정답 후보에 추가된 숫자를 제외한 나머지 숫자 문자열로 함수를 재귀 호출한다. 디버깅 "011" 과 "11" 은 다른 문자열이므로 별개의 경우로 판단하지만 사실 같은 소수인 11이다. 다음과 같이 정수 변환 후 비교해 같은 경우로 판단했다. if (stoi(candidate) == stoi(answers[i])) 개선한 코드 소수 판별을 아무 생각없이 목표 숫자의 절반까지의 자연수로 모.. [알고스팟] 시계 맞추기 - 완전 탐색, 재귀 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 시계 맞추기(링크) 접근 방법 TSP 문제처럼 스위치 10개를 순차적으로 누르며 각 스위치를 3번 누를 때까지 (4번 누르는 것은 안 누르는 것과 같다.) 재귀 호출했다. 실패 원인 이 문제는 TSP처럼 도시의 (스위치의) 방문 순서 (누르는 순서)가 중요하지 않다. (1번 누르고 4번 누르는 것과 4번 누르고 1번 누르는 것은 완전히 동일하므로.) 핵심은 각 스위치당 얼마나 누르는지를 중점으로 재귀호출해야 한다. C++ 코드 #include using namespace std; const int INF = 9999, SWITCHES =10, CLOCKS = 16; const char linked[SWITCHES][CLOCKS+1] = { ".. [알고스팟] 여행하는 외판원 문제 - 완전 탐색, 재귀 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 여행하는 외판원 문제(링크) 도시들과 도시들 사이의 거리가 주어지면 모든 도시를 한 번씩 방문한 뒤 출발지로 돌아오는 가장 짧은 순환을 구한다. 문제에 따라 출발한 도시로 돌아오지 않고 모든 도시를 한 번씩 방문하기만 하도록 요구할 수도 있다. 이 경우는 최소 가중치 합의 해밀턴 경로를 구하는 것이라 할 수 있다. 최적화 문제 이전의 문제들은 하나의 답을 찾지만 외판원 문제와 같은 경우 여러 개의 답 중 어떤 기준에 따라 가장 좋은 답을 찾아내는 최적화 문제이다. 이런 특성에 따라 이전 재귀 함수의 형태와 다른 점들에 유의하자. 반환해야 하는 값이 문제에서 정한 기준에 따라 다르므로 단순히 대입이나 합산으로 반환값을 결정하지 않는다. 재귀적으.. [알고스팟] 게임판 덮기 - 완전 탐색, 재귀 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 게임판 덮기(링크) 빈 곳이 있는 게임판이 주어질 때 L 모양의 블럭을 한 개씩 덮어 모든 칸을 채우는 방법의 가짓수를 계산한다. 재귀적으로 생각하기 게임판에 L 모양의 블럭을 한 개 덮는 것을 하나의 작업 조각으로 생각한다. 재귀 함수는 빈 곳이 있는 게임판이 주어질 때 4 가지 모양의 L 블럭을 각각 덮을 수 있는지 검사해보는 작업을 반복한다. 중복으로 세는 문제 블록을 놓는 순서에 상관없이 같은 블록들로 덮었다면 한 가지 경우이다. 블록을 놓는 순서를 강제하면 놓는 순서에 따라 별개의 경우로 세는 문제를 막을 수 있다. 가장 왼쪽 위의 빈 칸부터 덮어 나가는 것으로 순서를 강제하자. 무식하게 풀 수 있을까? 빈 칸의 수는 50개를 넘지 .. [알고스팟] 소풍 - 완전 탐색, 재귀 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 소풍(링크) 재귀적으로 생각하기 학생의 명단이 주어지면 둘 씩 짝 짓는 경우의 수를 계산한다. 두 학생을 짝 짓는 작업을 하나의 작업 조각으로 보면 재귀 함수는 아직 짝을 찾지 못한 학생의 명단이 주어질 때 두 학생을 짝 지어주는 작업을 반복한다. 중복으로 세는 문제 1번 3번을 짝 짓는 것과 3번 1번을 짝 짓는 것은 별개의 경우로 세면 안 된다. 이처럼 중복으로 세는 문제를 다루는 한가지 방법은 항상 특정 형태의 답만을 세는 것이다. (조합을 구할 때 동일한 원소들이 순서가 다르게 선택되어 별개의 경우가 되지 않도록 고르는 순서를 강제하는 것과 같다.) 무식하게 풀 수 있을까? 이 문제가 가장 많은 답을 가지는 입력은 열 명의 학생이 모두.. [알고스팟] 보글 게임 - 완전 탐색, 재귀 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 보글 게임(링크) 재귀적으로 생각하기 주어지는 단어를 게임판의 알파벳으로 만들 수 있는지 판별하므로 단어의 알파벳 하나와 게임판의 알파벳이 일치하는지 검사하는 작업 조각을 단어의 알파벳 개수만큼 반복해 문제를 해결한다. 단어의 맨 앞 알파벳과 현재 게임판 위치의 알파벳을 비교해 일치하면 나머지 글자로 이루어진 단어를 넘기며 재귀 호출한다. 즉, 재귀 함수는 인자로 받는 단어의 첫 알파벳과 게임판의 알파벳이 일치하는지 확인하는 동일한 작업을 반복한다. 재귀 호출에 필요한 입력 찾아야 할 단어와 현재 검사해야 할 게임판의 좌표를 인자로 받는다. 시간 복잡도 시간 안에 동작하는지 확인하기 위해 최악의 경우를 고려해보자. 길이가 n 인 단어가 주어질.. 이전 1 2 다음