이것 저것 &

문제링크: programmers.co.kr/learn/courses/30/lessons/59413

보호소에서는 몇 시에 입양이 가장 활발하게 일어나는지 알아보려 합니다. 0시부터 23시까지, 각 시간대별로 입양이 몇 건이나 발생했는지 조회하는 SQL문을 작성해주세요. 이때 결과는 시간대 순으로 정렬해야 합니다.

이전 입양 시각 구하기(1)처럼 하게 되면 count가 0일때 값들이 나오지 않습니다. 즉, 모든 시간대(0시~23시)를 조회해야 합니다.

쿼리문에서 로컬 변수를 활용하는 문제를 사용하는 문제입니다..

이를 위해서 set을 사용했습니다.

아래는 정답코드입니다.

set @hour := -1;
SELECT 
    (@hour := @hour + 1) as HOUR,
    (select count(*) from animal_outs where hour(datetime) = @hour) as COUNT
from 
    animal_outs
where
    @hour < 23;
    

문제링크:programmers.co.kr/learn/courses/30/lessons/59412

보호소에서는 몇 시에 입양이 가장 활발하게 일어나는지 알아보려 합니다. 09:00부터 19:59까지, 각 시간대별로 입양이 몇 건이나 발생했는지 조회하는 SQL문을 작성해주세요. 이때 결과는 시간대 순으로 정렬해야 합니다.

hour를 알아야 풀 수 있는 문제였습니다.

count(datetime) as count를 통해서 시간대별 입양 횟수를 구할 수 있습니다. ( group by hour 로 묶여있기 때문에)

정답코드입니다.

-- 코드를 입력하세요
SELECT hour(datetime) as hour, count(datetime) as count
from ANIMAL_OUTS 
group by hour having hour >= 9 and hour <=19
order by hour

문제링크:programmers.co.kr/learn/courses/30/lessons/59041

동물 보호소에 들어온 동물 이름 중 두 번 이상 쓰인 이름과 해당 이름이 쓰인 횟수를 조회하는 SQL문을 작성해주세요. 이때 결과는 이름이 없는 동물은 집계에서 제외하며, 결과는 이름 순으로 조회해주세요.

주어진 조건을 하나씩 만족하다보면 쉽게 구할 수 있습니다.

• 두 번 이상 쓰인 이름과 -> group by  name having count(name) > 1
• 이름이 없는 동물은 집계에서 제외하며 -> where name is not null 
• 결과는 이름 순 -> order by name 

아래는 정답코드입니다.

-- 코드를 입력하세요
SELECT name, count(name) as count from ANIMAL_INS
where name is not null 
group by  name having count(name) > 1
order by name 

문제링크:programmers.co.kr/learn/courses/30/lessons/59040

동물보호소에 개와 고양이밖에 없기 때문에 group by로 간단하게 풀 수 있습니다.

아래는 정답코드입니다.

SELECT ANIMAL_TYPE, COUNT(ANIMAL_TYPE) AS COUNT
FROM ANIMAL_INS
GROUP BY ANIMAL_TYPE

문제링크:programmers.co.kr/learn/courses/30/lessons/59408

distinct 명령어를 알기만 하면 쉽게 풀 수 있는 문제입니다. 

중복제거를 의미합니다.

아래는 정답 코드입니다.

-- 코드를 입력하세요
SELECT  count( distinct NAME) from ANIMAL_INS  where NAME is not null ;

문제링크:programmers.co.kr/learn/courses/30/lessons/59405

동물 보호소에 가장 먼저 들어온 동물의 이름을 조회하는 SQL을 작성하는 문제입니다. 

1. limit 를 사용하는 방법

select NAME
from ANIMAL_INS 
order by DATETIME
limit 1;

정렬과 limit를 사용해서 가장 먼저 들어온 동물을 조회하는 방법입니다.

문제링크:www.acmicpc.net/problem/17208

냅색알고리즘을 아는냐 모르냐에 따라서 체감 난이도가 큰 문제입니다.

우선 배낭여행 알고리즘을 모른다 하시면 아래링크 문제부터 풀어 보세요.

gusdnr69.tistory.com/153 

평범한 배낭문제와 같은 맥락입니다.

하지만 감튀랑 버거 두가지를 함께 고려해주어야 하는 문제입니다.

저는 삼차원 배열을 만들어서 해결했습니다.

dp[i][j][u]  => n번째 손님까지, j개의 버거, u개의 감튀로 최대 몇명의 손님을 받을 수 있는가?

이를 위해서는 삼중 포문을 사용해야 합니다.

//solve
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for (int u = 1; u <= k; u++) {
				if (j >= b[i] && u >= p[i]) 
					dp[i][j][u] = max(dp[i - 1][j][u], dp[i - 1][j - b[i]][u - p[i]] + 1);	
				else
					dp[i][j][u] = dp[i - 1][j][u];
			}
	

평범한 배낭문제와 굉장히 유사합니다.

아래는 전체 정답 코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;

int n, m, k;

int dp[101][301][301] = { 0, };
int b[301] = { 0, };
int p[301] = { 0, };

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

	cin >> n >> m >> k;

	for (int i = 1; i <= n; i++) 
		cin >> b[i] >> p[i];

	//solve
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for (int u = 1; u <= k; u++) {
				if (j >= b[i] && u >= p[i]) 
					dp[i][j][u] = max(dp[i - 1][j][u], dp[i - 1][j - b[i]][u - p[i]] + 1);	
				else
					dp[i][j][u] = dp[i - 1][j][u];
			}
	
	cout << dp[n][m][k] << endl;
}

손에 안 익으시다면 배낭여행 알고리즘 문제를 3~4개 푸시면서 다른 문제가 나와도 적용할 수 있게 연습해보세요.

문제링크:www.acmicpc.net/problem/7579

배낭문제 알고리즘으로 해결하는 문제입니다.

근데 기존 배낭문제에서는 배낭에 넣을 수 있는 최대값을 구하잖아요?

근데 이문제는 최소 값을 구해야 하고 무게가 아닌 시간값을 구해야하는게 다른 문제입니다. 

그래서 시간과 무게를 반대로 생각해서 점화식을 구현하는 문제입니다.

이 문제가 어려우시다면 아래 문제를 먼저 풀어보세요.

gusdnr69.tistory.com/153 

m[] 메모리 배열

c[]  비용 배열

dp[i][j]  i는 n개의 앱 중에서 몇번째 앱까지인지   j는 시간을 의미합니다.

이때 dp에 저장되는 값은 메모리값이 저장됩니다.

점화식은

if(j >= c[i])  dp[i][j] = max(dp[i-1][j], dp[i -1][j- c[i]] +m[i])

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

입니다.

dp[i][j] >= M 일때  min(result,j)를 통해서 결과값을 도출합니다.

아래는 정답코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;

int N, M;
int m[101] = { 0, };
int c[101] = { 0, };
int dp[101][10001] = { 0, };
int result = 1000000000;


int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M;

	for (int i = 1; i <= N; i++){
		cin >> m[i];
	}
	for (int i = 1; i <= N; i++) {
		cin >> c[i];
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= 10000; j++) {
			if (c[i] <= j)
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + m[i]);
			else
				dp[i][j] = dp[i - 1][j];

			if (dp[i][j] >= M) result = min(result, j);
		}
	}
	

	cout << result << endl;

	return 0;
}