wonseok.log wonseok.log

이 글은 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

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 BFS로 x/3, x/2, x-1 방향으로 모든 탐색하여 풀이를 작성할 수 있지만 메모리 초과로 다른 풀이 방법을 떠올려야 합니다. 이 문제는 DP를 이용하면 쉽게 풀 수 있습니다. #include using namespace std; int main(){ int vec[1000001]; int num; cin>>num; vec[1] = 0; for(int i=2;i

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 sort 함수를 구현하는 되는 문제로 원하는 조건에 맞게 구현합니다. sort 함수에서 strict weak ordering에 맞게 하지 않으면 런타임 에러가 발생할 수도 있습니다. #include #include #include #include #include using namespace std; bool cmp(string& s1, string &s2){ if(s1.size()

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 배열 같은 경우는 추가, 삭제의 시간복잡도는 O(N)이 걸리는 반면, 링크드 리스트 경우 O(1)입니다. 이 문제는 추가, 삭제가 용이해야 더 편한 문제이기 때문에 링크드 리스트를 사용해야 합니다. #include #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); string s; cin>>s; list mylist; for(int i=0;i>num; for(int i=0;i>op; if(op == 'L' && it != mylist.begin()){ it--; } else if(op == 'D' && it != mylist.end()){ i..