본문 바로가기
반응형

Problem Solving242

백준 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.
백준 1938번 통나무 옮기기 - C++ 풀이 1. 통나무의 위치와 방향 값으로 평지의 상태를 나타낼 수 있다. 2. 평지의 상태를 그래프의 노드로 생각하고, 한 번의 연산으로 도달 가능한 상태들을 모두 간선으로 잇는다. 3. 초기 상태 노드에서 도착 상태 노드로 가는 최단거리를 BFS를 사용하여 구한다. 1. 통나무의 위치와 방향 값으로 평지의 상태를 나타낼 수 있다. 평지에서 움직이는 것은 통나무뿐이다. 따라서 평지의 상태를 나타내기 위해 필요한 값은 통나무의 위치와 놓인 방향뿐이다. 2. 평지의 상태를 그래프의 노드로 생각하고, 한번의 연산으로 도달 가능한 상태들을 모두 간선으로 잇는다. 통나무의 위치와 방향을 가지고 평지의 상태를 나타낸다. 그리고 하나의 상태를 그래프 상의 하나의 노드로 생각해준다. 그리고 한 번의 연산으로 도달 가능한 상태.. 2022. 7. 6.
반응형

티스토리툴바