뚝딱뚝딱

https://www.acmicpc.net/problem/12865

💡 평범한 배낭

[문제]
이 문제는 아주 평범한 배낭에 관한 문제이다.한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

[입력]
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.입력으로 주어지는 모든 수는 정수이다.

[출력]
한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

✅ 문제 풀이

• 배낭 문제는 전형적인 DP 문제
• 배낭 문제 중에는 물건의 무게를 쪼갤 수 있는 fraction knapsack 문제와 쪼갤 수 없는 0-1 knapsack 문제로 구분할 수 있다.
• 이 문제는 0-1 knapsack에 해당한다.
• 1번 물건부터 n번 물건까지 각각의 물건을 넣을지 말지에 따라서 무게k 안에 담을 수 있는 최대 가치는 달라진다.
• 이를 계산하기 위해 2차원 배열을 사용한다.
• dp[i][j]에서 i는 i번째 물건까지 고려하면서 최대로 담을 수 있는 배낭의 무게가 j일때의 최대 가치를 갖는다.
• 따라서 dp[i][j]를 구할 때는 i번 째 물건을 넣지 않은 경우와 넣은 경우 중 더 큰 가치를 반영하도록 한다.
  이는 i번째 물건의 무게가 j 이하여야 넣을 수 있기 때문에, 이를 꼭 확인한다.
  i번째 물건을 넣지 않는다면, i-1번째 물건까지 고려했을 때의 가치와 같다.
  i번째 물건을 넣는다면, i번째 물건의 가치+dp[i-1][j-i번째 물건의 무게]와 같다. (i번째 물건의 무게만큼 빼줘야 i를 넣음으로써 배낭의 무게가 j이하로 유지할 수 있기 때문이다)
  이 두 값 중 더 큰 값이 dp[i][j]가 된다.
• 그런데 만약 i번째 물건의 무게가 j보다 크다면, 배낭에 넣을 수 없기 때문에, 이때의 dp[i][j]는 i-1번째 물건까지 고려했을 때의 가치와 동일하게 된다. 어차피 못넣기 때문이다.
• 그렇다면 다음 두가지 경우에 대해서 각각의 점화식을 나타낼 수 있다.
  
  

🅰 j < i번째 물건의 무게

dp[i][j] = dp[i-1][j]

🅱 j >= i번째 물건의 무게

dp[i][j] = max(dp[i-1][j], v[i]+dp[i-1][j-w[i]])

• 입력으로 받은 물건의 개수 n, 배낭에 담을 수 있는 최대 무게 k
• 2중 for문을 통해 i는 1부터 n까지, j는 1부터 k까지 순회하며 dp[i][j]를 계산할 수 있다.
• 이때 점화식에 의해서, 아직 2중 for문을 통해 계산되지 않은 범위의 dp값을 사용하게 되는 경우가 있는데, 이는 결국 조건을 충족하지 못해 0으로 계산되어야 한다. 따라서 처음에 2차원 배열 dp를 생성할 때, 크기가 (n+1) * (k+1)인 배열로 선언하고, 값은 모두 0으로 초기화 하여 시작하였다. 이렇게 하면 0 값을 가져다 쓸 수 있다. 
• 2중 for문으로 dp를 모두 계산하고 나면, dp[n][k]에는 n번 물건까지 고려하여 배낭에 담을 수 있는 최대 무게가 k일때의 최대 가치가 담기게 된다.
• 따라서 dp[n][k]를 출력해준다. 

✏ 코드 전문

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k;
	cin >> n >> k;

	vector<int> w(n+1,0);
	vector<int> v(n+1,0);
	
	for (int i = 1; i <= n; i++) {
		cin >> w[i] >> v[i];
	}

	vector<vector<int>> dp(n + 1, vector<int>(k + 1,0));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (j < w[i]) {
				dp[i][j] = dp[i-1][j];
			}
			else {
				dp[i][j] = max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]]);
			}
		}
	}

	cout << dp[n][k];

	return 0;
}

첫 sql문 문제 풀이이다.

데이터베이스설계를 들으면서 sql문은 어느 정도 익숙해져 있고, 정처기를 준비하면서도 복잡한 sql문을 공부해 왔어서 어렵지 않게 문제를 풀 수 있었으나...! 역시 디테일한 부분은 좀 더 공부할 필요가 있음을 느낀 첫 문제였다.

DATE 형식의 컬럼의 출력 형태 변환하는 방법!

이 문제에서 내가 걸렸던 부분은 주의사항에 있는 DATE 형식을 주어진 예제의 출력결과처럼 변경하여 출력할 수 있도록 하는 것이었다.

문제에서 PUBLISHED_DATE의 형식을 'YYYY-MM-DD' 형태로 출력하도록 요구하고 있다.

처음에는 이 부분을 확인하지 못하고 그냥 출력해 보았는데, 뒤에 상세한 시간까지 출력되는 것을 확인하였다.

이렇게 시간까지 표시되는 것을, 날짜만 표시되도록 변경해주어야 한다.

이때 사용할 수 있는 것이 DATE_FORMAT() 함수이다!!

mysql : DATE를 원하는 형식으로 변경하기

각 sql마다 다른데, 내가 사용하는 mysql을 기준으로는 다음과 같은 방식을 사용할 수 있다.

1. 날짜→문자열로 변환

DATE FORMAT(날짜, 출력 형식)

문제 예시 ) DATE_FORMAT(A.PUBLISHED_DATE, '%Y-%m-%d')

위의 형태의 날짜를 '2020-01-02'의 형태로 리턴해준다.

2. 문자열→날짜로 변환
 
STR_TO_DATE(문자, 출력 형식)
 
예시) 
STR_TO_DATE('20080101', '%Y-%m-%d')

20080101이라는 문자를 2008-01-01의 형태의 날짜로 리턴해준다.

---

여기에서 주의할 점은 '%Y-%m-%d' 이 부분인데, 여기에서 Y이면 '2020'과 같은 형태를, m이면 '03'과 같은 형태를, d이면 '23'과 같은 형태로, 보통 'yyyy-mm-dd'형식의 출력을 얻을 수 있다.
이 부분이 왜 헷갈리냐면, 저 문자를 대문자로 쓰느냐, 소문자로 쓰느냐에 따라 다른 출력이 되기 때문이다.
나도 처음에는 모두 대문자로 써서, 월은 'march', 일은 'secondary_three' 이런식으로 나왔다.
따라서 형식에 따라 잘 구분지어 주어야 한다. 
자세한 내용은 아래의 표를 참고하자.

**FORMAT설명

위의 방법을 사용하고 출력한 결과이다.

원하는 출력 형태를 얻을 수 있었다!

전체 코드는 아래와 같다.

SELECT A.BOOK_ID, B.AUTHOR_NAME, DATE_FORMAT(A.PUBLISHED_DATE, '%Y-%m-%d') AS PUBLISHED_DATE
FROM BOOK A JOIN AUTHOR B ON A.AUTHOR_ID=B.AUTHOR_ID 
WHERE A.CATEGORY='경제' 
ORDER BY A.PUBLISHED_DATE;

join할 때 조인할 테이블을 A, B이런식으로 지정해주는 건 정처기 때 버릇.. 아주 좋은 버릇인거 같다.

가끔 안해도 돌아갈 때가 있는데, 정확하게 쓰는 거는 위가 맞기 때문에, 최대한 쓰려고 한다.

select ~ from~join~on~where~order by~ 순으로 알아보기 쉽게 줄바꿈 해 두었다.

* DATE_FORMAT(A.PUBLISHED_DATE, '%Y-%m-%d') AS PUBLISHED_DATE 

이런 부분의 경우, 예시 출력 형태를 보고 컬럼 이름을 잘 지정해주는 것이 중요한 포인트이다.

아깝게 틀릴 수 있는 사소한 문제이기 때문이다!

이상 백준허브 연동 겸 가볍게 풀어본 sql문제였다.