Machineboy空
분할정복(Divide and Conquer)Divide : 큰 문제를 작은 문제로 분할한다.기저사례(base case)를 잘 설정하여 일정 기준 이상 분할되지 않도록 해야한다.Conquer: 작은 문제의 답을 모아 큰 문제의 답을 구한다.일반적으로 재귀로 구현한다. 백트래킹(backtracking)답이 될 수 없는 경우는 탐색 대상에서 제외하여 효율적으로 답을 구하는 알고리즘가지치기(pruning)를 통해 연산량의 유의미하게 줄여줌가지치기를 사용하기 위해서는 현재 상태에서 도달할 수 있는 상태가 모두 답이 될 수 없음을 보여야함.정확한 시간 복잡도를 구하기 어려움 분할 정복백트래킹주로 재귀적인 방식으로 해결하위 문제를 해결하고 결과를 결합하여 문제를 해결문제 해결을 위해 모든 가능한 선택을 시도한 후,..
1. 회문(Palindrome)ex) "소주만병만주소", "수박이박수", "Madam, I'm Adam", "1234321" 회문을 판단하는 방법? 2. 올바른 괄호 문자열(VPS = Valid Parenthesis String)ex) (()), (())()보통은 스택(Stack)을 사용해서 해결')'가 입력될 때마다, 스택에 있는 '('를 하나씩 지운다. 이때 스택(top)이 비어있거나 '('이 없으면 올바른 괄호 문자열이 아님모든 문자열을 순회한 뒤, 스택이 비어있으면 올바른 괄호 문자열이고 비어있지 않으면 올바르지 않은 괄호 문자열임
내일 풀 수학 문제의 개수는 오늘 푼 문제 개수의 수와 숫자의 구성이 같으면서, 오늘 푼 문제 개수의 수보다 큰 수 중 가장 작은 수입니다.예를 들어, 오늘 67문제를 풀었으면 다음 날 76문제를 풉니다. 오늘 푼 문제의 개수를 줬을 때 다음날 풀 문제의 개수를 출력하는 프로그램을 작성하세요.입력오늘 푼 문제의 개수 자연수 N1 출력다음날 풀 문제의 개수 출력문제요약입력값과 같은 구성의 수 중 가장 작은 큰 수풀이 포인트Next-permutation정렬REVIEW경우의 수가 다양해지면 자꾸 생각하길 포기한다.작은 단계로 나누어 생각하는 법을 또 명심!999999까지가 아닌 1000까지만 해서 생각해보고 넓히고 하면 됌!CODE#include #include #include using namespace s..