반응형 알고리즘207 백준 1311번 할 일 정하기 1 - C++ 풀이 1. dp(idx, mask): 사람들의 상태가 mask일 때, idx~마지막 일까지 수행하기 위한 최소 비용 2. dp(idx, mask) = min(i번 사람에게 맡겼을 때의 비용 + dp(idx+1, mask | (1 2022. 7. 12. 백준 4256번 트리 - C++ 풀이 1. root 노드는 preorder[0]이다. 2. inorder 결과에서 root보다 먼저 나온 노드들은 왼쪽 부트리를 이루고, 나중에 나온 노드들은 오른쪽 부트리를 이룬다. 1. root 노드는 preorder[0]이다. 전위 순회 시 가장 먼저 방문하는 노드는 루트 노드이다. 2. inorder 결과에서 root보다 먼저 나온 노드들은 왼쪽 부트리를 이루고, 나중에 나온 노드들은 오른쪽 부트리를 이룬다. 중위 순회 시 왼쪽 부트리 - 루트 - 오른쪽 부트리 순으로 방문한다. 전위 순회 결과에서 찾은 루트를 중위 순회 결과에서 찾는다. 그리고 루트보다 더 먼저 등장한 노드들로 왼쪽 부트리를 만들고, 루트보다 더 나중에 등장한 노드들로 오른쪽 부트리를 만드는 작업을 재귀적으로 반복해주면 원래 트리를 .. 2022. 7. 11. 백준 17299번 오등큰수 - C++ 풀이 1. 오큰수와 동일하게 스택을 이용하여 풀이한다. 1. 오큰수와 동일하게 스택을 이용하여 풀이한다. 오큰수 문제와 같은 풀이를 적용할 수 있다. Ai 대신 F(Ai)값을 가지고 비교한다는 차이만 있다. 백준 17298번 오큰수 - C++(cpp) 풀이 + 그림 설명 1. 오른쪽부터 왼쪽으로 가면서 오큰수를 구할 것이다. 2. 스택에는 앞으로 오큰수가 될 수 있는 수들만 들어있게 유지한다. 3. 어떤 수 x를 고려하는 시점에서의 스택 top이 x의 오큰수이다. 1. 오 please-amend.tistory.com #include #include using namespace std; const int MAX = 1000001; int N; int A[MAX], F[MAX], NFG[MAX]; int main.. 2022. 7. 10. 백준 2933번 미네랄 - C++ 풀이 1. 바닥에서 시작하는 DFS/BFS로 떠있는 미네랄인지 체크할 수 있다. 2. 떠있는 미네랄들에 대해서 아랫부분이 어딘가에 닿을 때까지 떨어뜨린다. 1. 바닥에서 시작하는 DFS/BFS로 떠있는 미네랄인지 체크할 수 있다. 인접한 미네랄은 하나의 클러스터이므로, 바닥에서 DFS/BFS를 시작하여 방문하지 못한 미네랄은 떠있는 미네랄로 판단하면 된다. 2. 떠있는 미네랄들에 대해서 아랫부분이 어딘가에 닿을 때까지 떨어뜨린다. 1에서 검증한 떠있는 미네랄들에 대해서 각각 아랫부분이 어딘가에 닿으려면 몇 칸이나 떨어져야 하는지 구한다. 떠있는 클러스터는 그중 가장 작은 값만큼 떨어지게 될 것이다. #include #include using namespace std; const int LEFT = 0, RIG.. 2022. 7. 8. 백준 1781번 컵라면 - C++ 풀이 + 그림 설명 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. day일에 풀 수 있는 문제는 데드라인이 day 이상인 문제들이다. 따라서 N일에 풀 수 있는 문제는 데드라인이 N인 문제들 밖에 없으므로, 그 중에서 가장 컵라면을 많이 주는 문제를 골라야 한다. (N-1)일에는 데드라인이 (N-1)일이거나 N일인 문제들을 풀 수 있다. 데드라인이 N일인 문제 중 가장 많은 컵라면을 주는 문제는 N일에 풀어야 하기 때문에, 이제 그 문제를 제외한 문제들 중에서 가장 많은 컵라면을 주는 문제를 고르면 된다. 같은 방식으로 N-2, N-3, ..., 1일까지 계속해서 가능한 문제 중 가장 많은 컵.. 2022. 7. 7. 이전 1 ··· 8 9 10 11 12 13 14 ··· 42 다음 반응형
