[백준] 2839번 설탕 배달 (C++) - 간단한 dp
2023. 3. 22. 16:13
solving/C, C++
1. 발상 우선 아이디어는 다음과 같다. 설탕 5kg, 3kg이 있으므로 -> 이번 회차의 최소 설탕봉지 개수는 (이번회차-3) / (이번회차-5) 둘 중 최솟값을 구해 거기에 +1봉지를 더한 값이다. base case : dp[3] = 1, dp[5] =1, 모든 dp 배열의 값은 0으로 초기 설정한다. 예외 존재) dp[i-3], dp[i-5] 둘 중 하나만 가능한 경우: 둘 중 존재하는 값 + 1 로 설정해야 한다. 예외처리를 위해 IF, ELSE IF, ELSE문 이용하였다. 2. 소스코드 #include #include #include using namespace std; int dp[5001] = {0, }; int main(){ cin.tie(NULL); ios::sync_with_stdio..
[백준] 11660번 구간 합 구하기 5 (C++) - 간단한 dp
2023. 3. 21. 21:47
solving/C, C++
2. 소스코드 1. 전체 소스코드 #include #include #include using namespace std; int N, M; int arr[1025][1025] = {0, }; int dp[1025][1025] = {0, }; int main(){ cin.tie(NULL); ios::sync_with_stdio(false); cin >> N >> M; for(int i=1; i arr[i][j]; } } for(int i=1; i> y1 >> x2 >> y2; cout
[백준] 1912번 연속합 (C++) - 간단한 dp
2023. 3. 21. 16:19
solving/C, C++
1. 발상 dp[] 배열을 이용해 문제를 해결한다. dp[i] = dp[i-1]+arr[i] 의 합과 arr[i] 중 큰 것 정답은 dp[i]에 저장된 값 중 최댓값 배열 정렬하기 귀찮아서 그냥 벡터 사용해서 값을 모두 insert한 뒤 sort 이용해 정렬했다. 2. 소스코드 #include #include #include using namespace std; int main(){ cin.tie(NULL); ios::sync_with_stdio(false); int n; cin >> n; int arr[n]; int dp[n]; for(int i=0; i> arr[i]; } vector ans; dp[0] = arr[0]; ans.push_back(dp[0]); for(int i=1; i
[백준] 5639번 이진 탐색 트리 (C++) - binary search tree
2022. 11. 21. 14:05
solving/C, C++
발상 우선 전위 탐색을 통해 얻은 tree가 주어지므로, 이를 배열에 입력받는다. 그리고 아래 그림과 같은 이분 탐색을 거치면, 후위 탐색으로 배열을 바꿀 수 있다. 전위 탐색 : root -> left -> right 후위 탐색 : left -> right -> root 이므로 순서를 바꾸어준다. 소스코드 #include #include using namespace std; int tree[10001]; void postorder(int start, int end){ if(start == end) { cout
[백준] 1991번 트리 순회 (C++) - preorder, inorder, postorder
2022. 11. 21. 02:29
solving/C, C++
발상 트리 순회에는 전위 순회 (postorder), 중위 순회 (inorder), 후위 순회 (postorder) 이 있다. 전위 순회 : node -> left -> right 중위 순회 : left -> node -> right 후위 순회 : left -> right -> node 모두 node 자신의 방문순서를 기준으로 생각하면 된다. 각각의 수도코드는 다음과 같다. void postorder{ cout char; if(node->left != NULL) postorder(node->left); if(node->right != NULL) postorder(node->right); } void inorder{ if(node->left != NULL) inorder(node->left); cout c..
[백준] 1325번 효율적인 해킹 - C++ (DFS, 그래프)
2022. 11. 10. 18:56
solving/C, C++
발상 1. 우선 그래프를 이용하는 문제인데 - A가 B를 신뢰할 경우 B를 해킹하면 A도 해킹할 수 있다는 것은, B가 부모 노드이고 A가 자식 노드인 것으로 생각하였다. B->A로 간선이 이어져서 B에서 해킹할 수 있는 자식 노드들을 모두 동시에 해킹할 수 있는 것들로 보았다. 2. DFS를 이용해 1~N까지 각 노드에서 출발했을 때 총 몇 개의 노드를 방문할 수 있는지를 계산하면 되는 문제이다. 3. dfs 함수를 int로 설정하였다. for문을 이용해 1~N까지 반복문을 설정하고, 각 node에서 출발하여 새로운 node를 방문할 때 (check값이 false인 자식 노드) ans에 해당 node에서의 dfs 값을 더하도록 했다. (해당 노드+거기에 연결된 자식 노드의 수) 4. 반환된 ans값을 ..
[백준] 11724번 연결 요소의 개수 - C++ (DFS, 그래프)
2022. 11. 10. 18:03
solving/C, C++
풀이에 https://velog.io/@polynomeer/%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8CConnected-Component 포스팅을 참고하였음을 밝힙니다. 발상 1. 그래프 + 주어진 그래프의 정점들을 DFS를 이용해 탐색하여 연결 요소의 개수를 밝히는 문제이다. 2. 그래프는 우선 C언어에 내장된 vector를 이용해 구현하고, 방향이 없는 그래프이므로 하나를 입력받을 때마다 v->u, u->v 두 가지 모두를 입력한다, 3. DFS를 이용하면 한 개의 연결 요소 그래프에 속한 노드를 전부 탐색할 수 있으므로, false값을 가진 node에 대해 DFS를 수행해 해당 연결 요소의 노드를 전부 탐색하고 답에 +=1을 해준다. 그리고 또 false값을 가진 node가 ..
[백준] 14501번 퇴사 - C++ (Bruteforce, 재귀함수)
2022. 10. 8. 18:57
solving/C, C++
발상 1. 우선 알고리즘 중 bruteforce를 이용해야겠다고 생각했다. 1~N까지 날짜 중 되는 상담을 잡았을 때의 최대 값을 구하는 것이고, A일이라면 A+1일의 상담에 걸리는 날짜부터 N까지를 다시 탐색하는 방법으로 문제를 해결하면 될 것이라고 생각했다. 2. 종료하는 분기점은 date가 N보다 클 때이다. 이 때 종료하고, 그 이전의 cost값을 v에 push해준다. 그런데 date=N+1일 때는 실제로는 직전에 시작한 상담이 마지막 날에 정확히 끝나는 것이므로, (예로, N이 7일 때, 5일에 3만큼의 상담을 했다면, date=8이 되어 종료되지만 실제로는 5, 6, 7일 3일간 상담을 하고 8로 넘어가므로 date=8도 유효한 값이다.) 이 때의 cost값도 v에 push해준 뒤 return..