본문 바로가기

분류 전체보기67

[백준/C++] #11049 행렬 곱셈 순서 (DP) 문제https://www.acmicpc.net/problem/11049  구상행렬 곱셈 연산의 수의 최솟값을 구하는 문제였다. 해당 문제가 11066번(https://persi0815.tistory.com/47)과 같이 작은 부분을 통해 큰 부분의 값을 알아낼 수 있었다. 처음에 착각했던게, a b c d라는 배열이 있으면, abc * d와 a* bcd의 연산만 가능하다고 생각했었다. 사실 ab*cd도 되는데.. 그래서 해당 부분 수정해서 로직을 짰더니 성공 !!알고리즘이전에 구한 값으로 다음 값을 구하니 dp 유형이다.  풀이 + 코드dp[i][j]는 행렬 i부터 행렬 j까지의 최소 행렬 곱셈 연산 수이다. 최악의 연산수도 범위가 2^31-1보다 작다고 해서 int를 사용했다. #include#incl.. 2024. 7. 23.
[백준/C++] #11066 파일 합치기 (DP) 문제https://www.acmicpc.net/problem/11066 구상문제 풀이가 생각이 안나면 나는 일단 DP로 접근을 해본다. 이 문제도 그러했는데, DP로 접근해보니 풀이가 보였다. 이전 합치는 비용을 이용해서 다음 합치는 비용을 구했다. DP를 사용할 때는 획일화된 기준이 중요해서 첫 기준을 파일 길이로 잡고 다음 기준을 파일 시작 위치로 정했다. 그랬더니 파일 끝 위치는 저절로 설정할 수 있었고, 다음 기준을 분할 위치로 잡았다. 그렇게 마지막 식을 보면 알 수 있듯이 이전 값들을 이용해서 보다 큰 다음 비용을 구할 수 있었다. 알고리즘이전 합치는 비용 이용해서 다음 합치는 비용을 구하니까 DP를 이용했다.  풀이 + 코드dp[i][j]: 파일 i부터 j까지 합치는 데 필요한 최소 비용. .. 2024. 7. 23.
[백준/C++] #2293 동전1 (DP) 문제https://www.acmicpc.net/problem/2293구상나는 보통 문제를 보고 '어떻게 접근해야 할지 모르겠다...! 혹은 재귀인가..?'라는 생각이 들면 dp로 접근해본다. 이 문제도 그러했다. 오랫만에 dp를 풀어서 그런지 좀 머리를 싸맸는데, 동전의 구성이 같은데, 순서만 다른 것은 같은 경우라는 조건을 보고 동전의 가치를 큰 기준으로 잡고 가야겠다는 생각이 들었다. 글로 쓰기가 어려워서 그림으로 대체한다.  알고리즘이전에 구한 값을 이용하여 다음 값을 구하기에 dp(dynamic programming)를 이용했다. 풀이 + 코드#include #include #include #define endl "\n"using namespace std;int N, K;vector coins;v.. 2024. 7. 22.
[백준/C++] #20366 같이 눈사람 만들래? (Two Pointer) 문제https://www.acmicpc.net/problem/20366구상N개의 눈덩이를 가지고, 4개의 눈덩이를 골라, 2개의 눈사람을 만드는데, 두 눈사람의 높이의 차가 최소가 되도록 하여 최소인 높이 차를 출력하는 문제였다. 지금보면 진짜 바보같지만, 처음에는 진짜 내가 이걸 1초만에 생각해낸게 신기할 정도로 쉬워보이는 풀이 (결과적으로 틀린 풀이) 를 생각해냈다.  무엇이었냐 하면, 눈사람의 지름이 a, b, c, d라 하면, (a+b) - (c+d)의 값이 가장 작으면 되니까, (a-c)-(d-b)의 최소값을 구하면 되겠다 생각해서 눈사람의 지름 오름차순으로 정렬하고, 인접한 배열의 값끼리의 차를 구한 배열을 만들어서, 그걸 또 정렬해서(인덱스 값과 함께 pair로. 인접한것 고르면 안되니까),.. 2024. 7. 22.

티스토리툴바