이것 저것 &

문제링크: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;
}

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

제목 그대로 평범한 배낭문제 (knapsack) 입니다. 

배낭 문제는 

• 물건을 쪼갤 수 있는 배낭문제(Fraction Knapsack Problem)
• 물건을 쪼갤 수 없는 배낭문제(0/1 Knapsack Problem)

두가지로 분류됩니다.

 물건을 쪼갤 수 있는 배낭문제의 경우는 가치가 큰 물건부터 담고, 남은 무게 만큼 물건을 쪼개는 방식으로

그리디 알고리즘을 사용합니다.

물건을 쪼갤 수 없는 배낭문제의 경우는 동적계획법을 사용합니다.

해당문제는 dp를 사용하는 방식입니다.

전제조건

n은 물건개수, k는 가져갈 수 있는 무게값

w[]는 물건에 대한 무게값들

v[]는 해당 물건에 대한 가치값

i는 i번째 물건 j는 무게를 나타냅니다. 

즉, dp[i][j]는 i번째 물건까지 최대 j무게까지 가능할때 최고의 가치값입니다. 

점화식은

if(w[i]<=j) 일때는

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

else

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

이 됩니다.

이해가 가지 않으신다면 직접 표로 작성해보세요.

정답코드입니다.

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


int n, k;
int w[100001] = { 0, };
int v[1001] = { 0, };
int dp[101][100001] = { 0, };

int main() {

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

	cin >> n >> k;

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


	return 0;
}

심화문제는 7579번 앱!

좌측 검색누르셔서 제가 푼 코드 확인하실수 있습니다.

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

근우와 명우가 돌아가면서 최선의 선택을 한다.

처음에 규칙성을 찾아보려고 했지만, 규칙성을 찾지를 못했습니다.

1 8 100 2 10 이나 1 8 10 200 10 와 같은 다양한 경우에 따라서 예외가 발생하기 때문에 규칙성이 아닌

모든 경우를 생각해보는 것으로 생각을 바꿨습니다.

근데 모든 경우를 항상 계산해주는것이 아니라 이미 계산한 내용이라면 비트마스킹을 통해 저장해두었다가 다시 전달하는 형태로 구현하는 것이 핵심입니다. 

dp[1001][1001][2] ->   앞에 두 1001은 1~1000까지 시작점, 끝점을 나타냅니다. 그리고 마지막 2는 0일때는 근우 1일때는 명우의 턴을 가르킵니다. 

재귀함수 호출 코드입니다. DP up-down 방식 

int solved(int startt, int endd, int turnn) {

	if (dp[startt][endd][turnn] != -1)
		return dp[startt][endd][turnn];

	if (startt == endd) {
		if (turnn == 1)
			return 0;
		else {
			return arr[startt];
		}
	}

	if (turnn == 0) {
		dp[startt][endd][turnn] = max((solved(startt + 1, endd, !turnn) + arr[startt]), (solved(startt, endd - 1, !turnn) + arr[endd]));
	}
	else {
		dp[startt][endd][turnn] = min((solved(startt + 1, endd, !turnn)), (solved(startt, endd - 1, !turnn) ));
	}

	return dp[startt][endd][turnn];
}

turn이 0일때는 근우 1일때는 명우의 차례입니다. 이 과정을 통해서 최종 결과값을 도출합니다. 

아래는 정답코드입니다.

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


int dp[1001][1001][2];
int t,n;
int arr[1001];

int solved(int startt, int endd, int turnn) {

	if (dp[startt][endd][turnn] != -1)
		return dp[startt][endd][turnn];

	if (startt == endd) {
		if (turnn == 1)
			return 0;
		else {
			return arr[startt];
		}
	}

	if (turnn == 0) {
		dp[startt][endd][turnn] = max((solved(startt + 1, endd, !turnn) + arr[startt]), (solved(startt, endd - 1, !turnn) + arr[endd]));
	}
	else {
		dp[startt][endd][turnn] = min((solved(startt + 1, endd, !turnn)), (solved(startt, endd - 1, !turnn) ));
	}

	return dp[startt][endd][turnn];
}


int main() {
	cin >> t;



	while (t--) {
		cin >> n;

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

		memset(dp, -1, sizeof(dp));

		
		cout << solved(1, n, 0)<<endl;// 0 is 근우 , 1 is 명우
		
	}


}