목록재귀 (13)

1일1알

백준 1991번 트리 순회 C++

노드와 트리를 직접 만들어서 풀다가 좀 오래걸렸는데 다른사람들 푼 것을 보니까 map으로 쉽게 풀 수 있었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; struct Node { Node* parent = nullptr; Node* left = nullptr; Node* right = nullptr; char value; }; Node* root = nullptr; Node* FindNode(Node* curr,..
알고리즘 2022. 6. 12. 19:57
백준 2407번 조합 C++

파이썬으로 하면 그냥 계산하면 되지만 C++에서는 int64 범위를 넘어가기 때문에 문자열로 처리해야 한다. 조합 계산은 파스칼의 삼각형을 이용해 메모이제이션과 재귀 방식을 이용하였고 수를 더할때는 문자열을 이용하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; vector cache; string Combination(int n, int m) { if (m == 0 || m == n) return "1"; strin..
알고리즘 2022. 6. 10. 11:21
백준 2448번 별 찍기 - 11 C++

삼각형의 높이, row, col 정보를 이용하여 재귀를 통해 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; void rec(int height, int row, int col, vector &board) { if (height == 3) { board[row][col] = '*'; board[row + 1][col - 1] = '*'; board[row + 1][col + 1] = '*'; for (int i = col - 2; i ..
알고리즘 2022. 3. 27. 12:28
백준 6576번 쿼드 트리 C++

분할 정복으로 n * n 의 픽셀을 구하고 그것을 16진수로 출력하는 문제이다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; string str; int idx = 0; void rec(vector& board, int row, int col, int n) { if (idx >= str.length()) return; if (str[idx] == 'Q') { idx++; rec(board, row, col, n / 2); rec(board, row, ..
알고리즘 2022. 2. 6. 14:49
백준 5904번 Moo 게임 C++

moo 문자열을 간단하게 숫자로 나타내 보겠다. moo는 3, mooo는 4, mooooo는 5 이런 식으로 사용할 것이다. moo 수열은 3 -> 3 4 3 -> 3 4 3 5 3 4 3 이런 식으로 증가하게 된다. n을 입력받아서 n이 수열의 길이보다 크다면 수열의 길이를 규칙에 맞춰서 늘리고, n이 수열의 길이보다 작다면 n의 값을 재조정하고 수열의 길이를 축소해가면서 문제를 해결하였다. 처음에는 직접 수열을 구현해보았는데, 그런 식으로 문제를 풀면 메모리 초과가 난다. 따라서 규칙에 맞춰서 특정 위치의 문자를 구하는 식으로 문제를 해결해야 한다. #include #include #include #include #include #include #include #include #include #inc..
알고리즘 2021. 12. 7. 12:31
백준 16198번 에너지 모으기 C++

어느 인덱스를 고르면 해당 인덱스의 값은 삭제되고, 그 양 옆의 수의 곱들의 합의 최댓값을 구하는 문제이다. vector의 erase와 insert 기능을 이용하여 재귀 함수로 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; vector v; int res = -1; void solve(int ans) { for (int i = 1; i < v.size() - 1; i++) { int mul = v[i - 1] * v[i + 1]; int delete..
알고리즘 2021. 11. 20. 10:14
이전 Prev 1 2 3 Next 다음