wonseok.log wonseok.log

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 이 문제를 그리디라고 오해하여 중량 대비 가치가 가장 큰 경우를 넣는다고 할 경우 예외가 발생하게 됩니다. 그리디가 아닌 DP로 해결해야 하면 DP로 유명한 0-1 knapsack 알고리즘입니다. D[i][w] : 현재 w 무게가 남은 상태에서 i번째 item선택까지 최대 가치 if w[i] < w, D[i][w] = max(D[i-1][w-w[i]]+v[i], D[i-1][w]) : i번째 Item을 담을 수 있다면, i-1번째까지 Item을 담으면서 현재 담을 수 있는 무게가 w-w[i]만큼 남은 경웅의 최대 가치합에 i번째 Item의 가치를 합한 값과 D[i-1][w] 값 비교 else, D[i][w] = D[i-1][w] #include #..

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 그리디 알고리즘을 사용해야 합니다. 예를 들어 로프 5개 중 3개로만 가지고 최대 중량을 구하는 문제라고 하면 중량이 무거운 순으로 정렬 후 최대로부터 3개의 로프를 사용하게 되고 3개 중 가장 작은 값에 곱하기 3을 해주면 됩니다. 즉, n개의 로프를 사용한다고 하면, n번째로 큰 값에 곱하기 n을 해줘야 합니다. #include #include using namespace std; int main(){ int num; cin>>num; int arr[100000]; for(int i=0;i>arr[i]; } sort(arr, arr+num); int result = 0; for(int i=0;i

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 그리디 알고리즘의 대표적인 문제입니다. 가장 많이 회의를 하기 위해서는 회의가 가장 먼저 끝나는 회의순으로 정렬 후 동일 시 먼저 시작하는 경우를 탐색하면 됩니다. #include #include #include #include using namespace std; bool cmp(pair& p1, pair& p2){ if(p1.second == p2.second){ return p1.firstnum; for(int i=0;i>a>>b; vec.push_back({a,b}); } sort(vec.begin(), vec.end(), cmp); int cnt = 1; int e = vec[0].second; for(int i=1;i=e){ e = ve..

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 BFS를 사용할 수 있지만 DP를 활용하여 공간복잡도를 줄일 수 있습니다. if i%2 != 0 && i%3 != 0, D[i] = D[i-1]+1 if i%2 == 0 && i%3 != 0, D[i] = min(D[i-1], D[i/2]) + 1 if i%2 == 0 && i%3 == 0, D[i] = min(D[i-1], D[i/2], D[i/3]) + 1 방법을 출력하기 위해서는 그 전 숫자를 담는 prev 배열을 만들어야 합니다. 10 => prev[10] = 9, prev[9] = 3, prev[3] = 1 #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie..

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 Prefix sum 구하기 문제입니다. DP를 사용하면 시간복잡도 O(N)에 구할 수 있습니다. D[i] = D[i-1] + D[i-2] +... +D[1] #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int arr[100000]={0}; int n,m; cin>>n>>m; for(int i=1;i>arr[i]; arr[i]+=arr[i-1]; } for(int i=0;i>a>>b; cout

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 DP를 이용하여 풀 수 있는 문제로 규칙을 잘 생각하면 됩니다. 2차원 배열을 만들고 행은 집의 수를 가리키고, 열은 3가지의 색상 크기로 선언합니다. i행 j열은 j색상을 칠한다고 가정했을 때, i 번째 집까지 집을 칠하는 최대 비용을 계산합니다. 첫 번째 행에서는 이전에 색을 칠한 집이 없기 때문에 자신의 색상을 칠하는 값으로 초기화합니다. 두 번째 행부터는 이전 행과 겹치지 않는 열 중에서 최대값을 설정하면 됩니다. ex) 2행 1열에서는 1행 2열과 1행 3열 둘 중 최대값에 2행 1열에 빨간집을 칠하는 값을 더하면 됩니다. #include using namespace std; int main(){ int num; cin>>num; int ..

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 DP를 활용하여 해결해야 하는 문제입니다. 기존의 DP는 1차원 점화식을 사용했다면, 이번 문제는 2차원배열을 이용한 점화식을 구해야 합니다. (연속적으로 3개의 계단을 밟는지에 대한 판단 때문에) D[i][1] : i번째 계단까지 포함하여 연속된 계단 수가 1인 경우, 즉 D[i-1]은 밟지 않고, D[i-2]를 밟은 경우 D[i][2] : i번째 계단까지 포함하여 연속된 계단 수가 2인 경우, 즉 D[i-1]을 밟고 D[i]를 연속적으로 밟은 경우 따라서 D[num][1]과 D[num][2] 중에 최댓값이 답이 됩니다. #include #include using namespace std; int main(){ ios::sync_with_stdi..

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 DP 전형적인 문제 중 하나로, 테이블 정의하고, 점화식만 찾으면 쉽게 해결할 수 있습니다. 문제해결을 위한 점화식은 D[i] = D[i-1] + D[i-2] +D[i-3] 입니다. #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int num; cin>>num; int vec[20]; vec[1] = 1; vec[2] = 2; vec[3] = 4; for(int i=4;in; cout