재원블로그 재원블로그

이 문제 역시 완전 탐색을 이용해서 풀 수 있다. 이 문제의 핵심은 왼쪽, 위 모두 꽉 차있는 상태에서 재귀가 이뤄진다고 고정하고 문제를 푸는 것이다. 구현이 약간 복잡하지만 로직 자체는 단순한 문제였다. #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

이 문제는 프로그래머스 Level 2 문제이다. 이 문제는 구현이 어려운 편에 속하고, 백트래킹을 이용해 연산자 우선순위를 정하고, long long 자료형을 사용해야 한다는 사실을 캐치하면 풀 수 있다. 수식이 정해져 있고, 연산자 우선순위가 같은 경우가 없기 때문에 다이나믹 프로그래밍을 생각해내기 어려웠다. 연산자가 최대 3개이므로 우선순위 경우의 수는 최대 6이다. 따라서 O(N) 시간의 알고리즘으로도 1초 안에 풀 수 있다. 연산하는 것까지 구현을 잘 했지만, long long 자료형을 사용해야 한다는 점을 파악하지 못해 처음에 오답이 나왔다. 그러나 문제를 다시 읽고 바로 수정한 뒤 정답을 받을 수 있었다. #include #include #include #include using namespa..