재원블로그 재원블로그

이 문제는 완전 탐색으로 푸는 문제이다. 버튼의 횟수에 초점을 맞추어 재귀를 수행하면 훨씬 수행시간을 줄일 수 있다. 한 버튼을 4번 누르게 되면 처음과 동일하므로 4번 미만까지를 제한을 둘 수 있다. 시간 복잡도의 경우 4^10 ~= 1,000,000 정도가 된다. 따라서 완전 탐색으로 풀 수 있다. #include #include #include using namespace std; #define NUMBER_OF_CLOCKS 16 #define NUMBER_OF_BUTTONS 10 int answer; int clocks[NUMBER_OF_CLOCKS]; const vector buttons[NUMBER_OF_BUTTONS] = { {0, 1, 2}, {3, 7, 9, 11}, {4, 10, 14,..

이 문제 역시 완전 탐색을 이용해서 풀 수 있다. 이 문제의 핵심은 왼쪽, 위 모두 꽉 차있는 상태에서 재귀가 이뤄진다고 고정하고 문제를 푸는 것이다. 구현이 약간 복잡하지만 로직 자체는 단순한 문제였다. #include #include using namespace std; #define MAX 20 int H, W; pair block[4][3] = { {{0, 0}, {1, 0}, {1, -1}}, {{0, 0}, {1, 0}, {1, 1}}, {{0, 0}, {0, 1}, {1, 1}}, {{0, 0}, {0, 1}, {1, 0}} }; char matrix[MAX][MAX]; bool assigned[MAX][MAX]; bool inRange(int y, int x) { if (0 C; for (..

이 문제는 완전 탐색으로 해결할 수 있다. 아주 간단하게 계산하면 10! ~= 3,000,000 정도밖에 안된다. 그러나 이 문제의 경우 쌍을 골라야 하고, 순서만 바뀐 경우는 제외해야 하므로 경우의 수가 훨씬 줄게 된다. 그래서 완전 탐색으로도 가능한 문제였다. #include using namespace std; #define MAX 10 int n, m; bool isFriend[MAX][MAX]; bool matched[MAX]; int solve(int matchCount, int prev) { if (matchCount == n) { return 1; } if (prev == -1) { int result = 0; for (int i = 0; i < n; i++) { if (matched[i]..

이 문제는 전위 순회 결과와 중위 순회 결과를 입력으로 받아 후위 순회 결과를 리턴하는 문제이다. 전위 순회의 경우 루왼오, 중위 순회의 경우 왼루오, 후위 순회의 경우 왼오루 순서로 노드를 방문하게 된다. 즉, 전위 순회에서는 무조건 루트부터 방문하므로 맨 앞이 루트가 된다. 전위 순회 결과로 루트를 알아낸 다음, 중위 순회 결과에서 이 루트로 왼쪽 서브트리와 오른쪽 서브트리를 알아낸다. 그 다음 후위 순회와 같이 호출해주면 쉽게 풀 수 있다. #include #include using namespace std; vector preorder; vector inorder; int rootIndex; void postorder(vector tree) { if (tree.empty()) { return; }..

이 문제는 KMP 알고리즘의 PI 배열을 이용하여 풀 수 있는 문제이다. 제한 시간이 500ms로 매우 짧고, 문자열 최대 길이가 40만이므로 반드시 O(N) 이하로 연산이 이루어져야 한다. 이 문제의 핵심 아이디어는 k 다음으로 긴 접미사를 찾을 때 pi[k - 1]을 이용하면 된다는 것이다. 이 점만 알면 쉽게 풀리는 문제였다. #include #include #include #include using namespace std; vector getPi(const string &input) { int m = input.size(); vector pi(m, 0); int begin = 1, matched = 0; while (begin + matched < m) { if (input[begin + mat..

이 문제는 덱을 이용해서 풀었다. 최대 수행 시간이 15000ms 이므로 15초이다. 즉, 15억번의 연산 안에 알고리즘을 짜면 된다. 부분 수열이 연속적인 부분 수열이고, 범위의 중복이 가능하다고 했으므로 덱을 이용해서 풀어야겠다고 생각했다. 유의할 점은 ll A[MAX + 1] 배열을 만들면 메모리 초과가 뜨는데, 이를 해결하기 위해서는 매 루프마다 A[i] 의 값을 직접 계산하면 된다. #include #include using namespace std; typedef long long ll; typedef unsigned int ui; #define MAX 50000000 #define INIT_MOD 4294967296ll ll solve(int K, int N) { ll acc = 0; ll ..

이 문제는 스택을 이용해서 간단하게 풀 수 있다. 문자열의 길이가 최대 10,000 이므로 테스트케이스까지 고려했을 때 O(n^2) 알고리즘은 사용할 수 없다. 스택을 이용하면 한번의 순회만으로 가능하므로 O(n) 시간이 소요되어 1초를 넘기지 않는다. #include #include #include using namespace std; bool correct(char left, char right) { if (left == '(' && right == ')') { return true; } if (left == '{' && right == '}') { return true; } if (left == '[' && right == ']') { return true; } return false; } bool..

동적 배열이나 리스트를 사용하는 문제지만, Queue로도 가능할 것 같아서 풀었다. N C; for (int test = 0; test > N >> K; vector answer = solve(N, K); cout