알고리즘65 행렬 곱셈 문제 https://www.acmicpc.net/problem/2740 풀이 #include #include #include #include using namespace std; int arr1[101][101]; int arr2[101][101]; int result[101][101]; int n = 0, m = 0, k = 0; int func(int a, int b){ // result[a][b]에 해당하는 값을 반환 for (int k = 0; k > n >> m; for (int i = 0; i < n; i++) { for (int .. 2022. 6. 11. 백준 소형기관차, (c++) 2616 문제 https://www.acmicpc.net/problem/2616 해결법 3개의 소형객차를 사용해서 최대로 많은 손님을 이끌고 가야한다. 여기서 dp식은 dp[i][j]이다 -> 현재 i까지 바라보고 있는데 소모한 소형기관차는 j이다 dp[i][j] = max(dp[i-1][j], dp[i - k][j -1] + s[i] - s[i -k]); 주의 dp[i][j]에서 1 ~ k번객차까지 봤다는 dp[k]가 있어야하므로 idx - k == 0인 부분도 보아야한다 . 소스 #include using namespace std; int n; int Sequential; int a[51000]; // 각 객차에서 손님의 수 int _sum_a[51000]; //a의 누적합 int dp[51000][4]; /.. 2022. 1. 13. 백준 이분그래프 (c++) 문제 https://www.acmicpc.net/problem/1707 해결 이분 그래프는 하나의 집단에서는 서로 연결이 안되어있는 것이다. 이분 그래프를 만들려면 자신의 집단(자신과 연결된 노드와는 다른 것으로 구분이 되어있어야한다) 구분을 지어서 이분 그래프를 만들어야하는데 그것은 예를 들어서 A노드가 레드이면 A노드와 연관되어있는 B노드는 레드가 아닌 다른색으로 색칠 되어있어야한다. 그렇게 하면 이분그래프가 완성된다. 주의 여기서 처음에 bfs(1)로만 돌렸다가 로직을 for문으로 모두다 보는 것으로 변경했다, 그래프가 하나가 아니라 여러개도 나올 수 있는건가?.. 소스 #include using namespace std; #define RED 1 #define BLACK 0 /* 같은 집합에 속한.. 2022. 1. 13. 프로그래머스 호텔 방 배정 문제 https://programmers.co.kr/learn/courses/30/lessons/64063 풀이방법 1 유니온 파인드 느낌으로 가는 것이다. 맵의 키 값에 해당 키번호에는 비어있는 바로 다음 방번호를 넣어주는 것이다 m[position] = position + 1; findset에서는 맵의 해당 키가 비어있다면 return을 해준다. 문제는 해당 방이 들어갈 다음 비어있는 방을 찾을 때 재귀를 많이 해야해서 효율성이 탈락한다. 소스 #include using namespace std; #define ll long long map m; int findset(int x) { if(m[x] == 0) return x; return m[x] = findset(m[x]); } vector solu.. 2022. 1. 10. 이전 1 2 3 4 ··· 17 다음