뚝딱뚝딱

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;
}

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

💡 분할과 정복 ** 쿼드트리 문제와 유사

[문제]
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.(1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

[입력]
첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

[출력]
첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

✅ 문제 풀이

• 분할과 정복을 통해 해결할 수 있는 문제이다.
• 문제는 처음 size에서 3등분 해가며 분할한다.
• 입력으로 주어진 size에서 시작하여, size 만큼 배열을 순회한다.
• 순회하다가 첫 값과 달라지는 부분이 발생하면, 9등분으로 나뉘어야 하기 때문에, size를 3등분 한다.
• 그리고 해당 함수를 각 9등분의 첫 값의 좌표에 맞추어 9번의 재귀호출을 한다.
• 첫번째 조각의 첫 좌표는 이전의 첫 좌표와 항상 동일하고, 두번째 조각의 첫 좌표는 y를 size만큼 더한 값이고, 세번째 조각의 첫좌표는 y를 size*2만큼 더한 값이다.
• 네번째 조각의 첫좌표는 x를 size 만큼 더한 값이고, 다섯번째 조각의 첫좌표는 x와 y 모두 size 만큼 더한 값이다...
• 이렇게 9등분을 차례차례 좌표를 부여하고 재귀호출 하면된다.
• 재귀호출 뒤에는 동작이 없기 때문에 바로 return하도록 하고, 만약 해당 size에서 모든 값이 동일했다면, 해당 값을 1 count하도록 한다.
• 이때 카운트는 map을 통해서 -1, 0,1을 key로 하였고, 0으로 자동 초기화 되는 값에 증가 연산자로써 연산되도록 구현하였다.  

✏ 코드 전문

#include<iostream>
#include<vector>
#include<map>

using namespace std;

int n;
vector<vector<int>> arr;
map<int, int> m;

void func(int size, int x, int y) {
	for (int i = x; i < x + size; i++) {
		for (int j = y; j < y + size; j++) {
			if (arr[x][y] != arr[i][j]) {
				int new_size = size / 3;
				func(new_size, x, y);
				func(new_size, x, y + new_size);
				func(new_size, x, y + new_size * 2);
				func(new_size, x + new_size, y);
				func(new_size, x + new_size, y + new_size);
				func(new_size, x + new_size, y + new_size * 2);
				func(new_size, x + new_size * 2, y);
				func(new_size, x + new_size * 2, y + new_size);
				func(new_size, x + new_size * 2, y + new_size * 2);
				return;
			}
		}
	}
	m[arr[x][y]]++; //해당 키가 map에 없으면, 자동으로 키 생성 및 0으로 초기화하고 증가시킴.
}

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

	cin >> n;

	arr.resize(n, vector<int>(n));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}

	func(n, 0, 0);

	cout << m[-1] << "\n" << m[0] << "\n" << m[1];

	return 0;
}

💡 map

• map 자료구조는 <키, 값>의 쌍으로 이루어진 자료형이다.
• map<int, int> m 으로 키와 값이 모두 int 타입인 map 자료구조를 하나 생성하였다고 가정하자.
• map은 키를 마치 인덱스처럼 사용할 수 있다.
• map[-1]은 키가 -1인 요소의 값을 리턴하게 된다.
• 만약 키값이 map에 존재하지 않은 새로운 값이라면, map[1]++ 을 했을 때 map에는 키가 1인 요소가 생성되고, 값은 0으로 자동 초기화 된다. 그리고 ++ 증가 연산자를 사용했기 때문에, map[1]은 1의 값을 갖게 된다.
• 따라서 map의 경우 insert로 값을 직접 넣지 않고도, map[키]=값 으로써 요소를 추가할 수 있다.  

https://school.programmers.co.kr/learn/courses/30/lessons/131117

💡 문제

FOOD_PRODUCT와 FOOD_ORDER 테이블에서 생산일자가 2022년 5월인 식품들의 식품 ID, 식품 이름, 총매출을 조회하는 SQL문을 작성해주세요. 이때 결과는 총매출을 기준으로 내림차순 정렬해주시고 총매출이 같다면 식품 ID를 기준으로 오름차순 정렬해주세요.

✅ 문제 풀이

• FOOD_PRODUCT와 FOOD_ORDER 테이블을 JOIN한다.

FOOD_PRODUCT A JOIN FOOD_ORDER B
ON A.PRODUCT_ID = B.PRODUCT_ID

• 두 테이블의 공통 속성인 PRODUCT_ID를 기준으로 JOIN한다.

• 생산일자가 2022년 5월인 식품을 추린다.

WHERE PRODUCE_DATE>='2022-05-01' AND PRODUCE_DATE<='2022-05-31'

• 제품 당 총매출을 구해야 하기 때문에, 제품 ID를 기준으로 그룹화한다.

GROUP BY A.PRODUCT_ID

• 조회할 정보를 가져온다.

SELECT A.PRODUCT_ID, A.PRODUCT_NAME, SUM(A.PRICE*B.AMOUNT) AS TOTAL_SALES

• 현재 PRODUCT_ID로 그룹화 되어 있기 때문에, SUM을 통해 같은 그룹 내 상품들의 매출을 더하여 총매출을 구할 수 있다.

• 조건에 따라 정렬한다.

ORDER BY TOTAL_SALES DESC, PRODUCT_ID ASC;

• 총매출을 기준으로 내림차순 정렬, 식품 ID를 기준으로 오름차순 정렬 해준다.

✏ 코드 전문

SELECT A.PRODUCT_ID, A.PRODUCT_NAME, SUM(A.PRICE*B.AMOUNT) AS TOTAL_SALES
FROM FOOD_PRODUCT A JOIN FOOD_ORDER B
ON A.PRODUCT_ID = B.PRODUCT_ID
WHERE PRODUCE_DATE>='2022-05-01' AND PRODUCE_DATE<='2022-05-31'
GROUP BY A.PRODUCT_ID
ORDER BY TOTAL_SALES DESC, PRODUCT_ID ASC;

CAST(A.DAILY_FEE*30*(1-B.DISCOUNT_RATE*0.01) AS SIGNED) AS FEE

💡 CAST 연산자
: 계산된 FEE값을 정수로 변환

AS SIGNED : 부호를 유지

AS UNSIGNED : 부호 제거

https://school.programmers.co.kr/learn/courses/30/lessons/157339

💡 문제

CAR_RENTAL_COMPANY_CAR 테이블과 CAR_RENTAL_COMPANY_RENTAL_HISTORY 테이블과 CAR_RENTAL_COMPANY_DISCOUNT_PLAN 테이블에서 자동차 종류가 '세단' 또는 'SUV' 인 자동차 중 2022년 11월 1일부터 2022년 11월 30일까지 대여 가능하고 30일간의 대여 금액이 50만원 이상 200만원 미만인 자동차에 대해서 자동차 ID, 자동차 종류, 대여 금액(컬럼명: FEE) 리스트를 출력하는 SQL문을 작성해주세요. 결과는 대여 금액을 기준으로 내림차순 정렬하고, 대여 금액이 같은 경우 자동차 종류를 기준으로 오름차순 정렬, 자동차 종류까지 같은 경우 자동차 ID를 기준으로 내림차순 정렬해주세요.

문제의 조건

• CAR_TYPE 이 '세단' 또는 'SUV'
• 2022-11-01 부터 2022-11-30 까지 대여가능
• 30일간의 대여금액 >=500000 AND <2000000
• 위를 만족하는 자동차의 CAR_ID, CAR_TYPE, FEE 출력
• 단, 대여금액 기준 내림차순, 자동차 종류 기준 오름차순, 자동차 ID기준 내림차순 정렬

✅ 문제 풀이

• 대여 가능 여부를 판단한다.
  HISTORY 테이블에서 START_DATE와 END_DATE가 있다. 11월 달에 대여한 적이 있는지를 보려면, START_DATE는 11월 30일 이전이어야 하고, END_DATE는 11월 1일 이후여야 한다. SQL문으로 나타내면 다음과 같다.

CAR_RENTAL_COMPANY_RENTAL_HISTORY C 
    WHERE C.START_DATE<='2022-11-30' AND C.END_DATE>='2022-11-01'

• 그럼 이 날짜에 RENTAL한 적이 있는 자동차는 제외하면 된다. 
• 이렇게 생각할 수도 있다. 11월 달에 대여한 적 없는 자동차만 고르면 되는 거 아닌가? 로직을 어떻게 짜냐에 다르긴 하지만, 단순하게 각 레코드 마다 11월달에 대여한 적 없는 경우를 고른다면, 11월에도 대여했었지만 다른 날짜에도 대여했던 동일한 자동차도 포함되어 버릴 수 있기 때문에, 11월에 대여한 자동차의 ID 자체를 제외하는 식으로 접근하였다. 이는 NOT IN 연산자를 통해 제외할 수 있다.

A.CAR_ID NOT IN (
    SELECT DISTINCT C.CAR_ID 
    FROM CAR_RENTAL_COMPANY_RENTAL_HISTORY C 
    WHERE C.START_DATE<='2022-11-30' AND C.END_DATE>='2022-11-01'
)

• 첫 WHERE 조건을 하나 완성하였다.

• 30일간의 대여금액을 계산하기 위해 테이블을 조인한다.
  이를 구하기 위해서는 CAR_RENTAL_COMPANY_CAR 테이블과 CAR_RENTAL_COMPANY_DISCOUNT_PLAN 테이블을 INNER 조인해주어야 한다. 그래서 각 자동차마다 CAR_TYPE에 따라 DISCOUNT 정보를 갖도록 할것이다.

FROM CAR_RENTAL_COMPANY_CAR A JOIN CAR_RENTAL_COMPANY_DISCOUNT_PLAN B
ON A.CAR_TYPE=B.CAR_TYPE

• 두 테이블의 공통 속성인 CAR_TYPE을 기준으로 JOIN한다.

• 조건에 따라 WHERE 절에 조건을 추가로 작성해준다.

AND A.CAR_TYPE IN('SUV', '세단') 
AND B.DURATION_TYPE = '30일 이상' 
AND A.DAILY_FEE*30*(1-B.DISCOUNT_RATE*0.01)>=500000 
AND A.DAILY_FEE*30*(1-B.DISCOUNT_RATE*0.01)<2000000

• CAR_TYPE이 'SUV', '세단' 중에 해당하면 조회한다. IN 연산자를 사용하였다.
• 조인 후에는 각 자동차 마다 CAR_TYPE에 따라 3개의 DISCOUNT_RATE 정보가 엮여있을 것이다. 이 중에서 DURATION_TYPE이 '30일 이상' 인것 만 사용하도록 한다.
• 대여금액은 조건에 해당하는 자동차의 DAILY_FEE*30*할인률 이기 때문에, 이 값이 50만원 이상 200만원 미만인 것만 추리도록 한다.

• 필요한 정보를 출력한다.

SELECT A.CAR_ID, A.CAR_TYPE, CAST(A.DAILY_FEE*30*(1-B.DISCOUNT_RATE*0.01)AS SIGNED) AS FEE

• 위에 조건에 부합하는 자동차의 CAR_ID, CAR_TYPE, FEE를 조회하도록 한다.
• 이때 FEE의 경우 *0.01 때문에 소수점 이하 두자리 형태로 출력되게 되는데, 조건의 주의사항에서 FEE의 경우 정수 형태로 출력하도록 되어있기 때문에, CAST 연산자를 사용하여 정수형태로 출력하도록 한다. AS SIGNED는 소수점을 없애면서 부호는 그대로 유지한다는 것이다.

• 조회결과를 주어진 정렬 조건에 맞도록 설정하기

ORDER BY FEE DESC, CAR_TYPE ASC, CAR_ID DESC;

• 마지막에 ORDER BY 문을 통해서 FEE를 기준으로 내림차순, CAR_TYPE을 기준으로 오름차순, CAR_ID를 기준으로 내림차순 정렬하도록 해준다.

✏ 코드 전문

SELECT A.CAR_ID, A.CAR_TYPE, CAST(A.DAILY_FEE*30*(1-B.DISCOUNT_RATE*0.01)AS SIGNED) AS FEE 
FROM CAR_RENTAL_COMPANY_CAR A JOIN CAR_RENTAL_COMPANY_DISCOUNT_PLAN B
ON A.CAR_TYPE=B.CAR_TYPE
WHERE A.CAR_ID NOT IN (
    SELECT DISTINCT C.CAR_ID 
    FROM CAR_RENTAL_COMPANY_RENTAL_HISTORY C 
    WHERE C.START_DATE<='2022-11-30' AND C.END_DATE>='2022-11-01'
)
AND A.CAR_TYPE IN('SUV', '세단') 
AND B.DURATION_TYPE = '30일 이상' 
AND A.DAILY_FEE*30*(1-B.DISCOUNT_RATE*0.01)>=500000 
AND A.DAILY_FEE*30*(1-B.DISCOUNT_RATE*0.01)<2000000
ORDER BY FEE DESC, CAR_TYPE ASC, CAR_ID DESC;