이것 저것 &

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

간단한 dfs 문제였습니다. 

백트래킹의 요소는 잘 모르겠습니다. 단지 가까운 치킨 가게를 찾을때 bfs 탐색의 개념을 사용하지 말고, 각각의 치킨집과 집의 거리를  |r1-r2| + |c1-c2| 공식을 통해서 찾아주게끔만 구현해주면 맞는 간단한 문제입니다.

저는 치킨집 좌표를 구조체 벡터를 사용해서, 집 좌표는 pair사용해서 구현했습니다. 

아래는 정답 코드입니다. 

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

typedef struct a{
	int y;
	int x;
	bool checked;
}Chk;

vector <pair <int, int>> house;
vector <Chk> chicken;
int n = 0, m = 0;
int result = 2e9;

void dfs(int cnt, int current) {

	if (cnt == m) {
		/*
		for (int i = 0; i < chicken.size(); i++) {
			if (chicken[i].checked == true)
				cout << i << ' ';
		}
		cout << endl;*/

		int sum = 0;

		for (int i = 0; i < house.size(); i++) {
			int mined = 1000000000;
			for (int j = 0; j < chicken.size(); j++) {
				if (chicken[j].checked == false) continue;

				mined = min(mined, abs(house[i].first - chicken[j].y) + abs(house[i].second - chicken[j].x));
			}
			sum += mined;
		}

		if (result > sum)
			result = sum;

		return;
	}
	

	for (int i = current; i < chicken.size(); i++) {
		if (chicken[i].checked == false) {
			chicken[i].checked = true;
			dfs(cnt + 1, i);
			chicken[i].checked = false;
		}
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	// 1.
	cin >> n >> m;
	int num = 0;
	for(int i=1;i<=n;i++)
		for (int j = 1; j <= n; j++) {
			cin >> num;
			if (num == 1)
				house.push_back(make_pair(i, j));
			else if (num == 2)
				chicken.push_back({ i,j,0 });
		}
	//2.
	dfs(0, 0);

	cout << result << endl;
	return 0;
}

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

간단한 시뮬레이션 문제입니다.

이동방향에 따라 이동시켜주면서 max y, x 값과 min y,x값을 찾아주면 되는 문제입니다.

이동할때는 4방향 배열을 사용해서 문제를 해결합니다.

바로 정답코드입니다.

#include <iostream>
#include <string>
#include <cmath>
using namespace std;


int t = 0;
int y_arr[4] = { -1,0,1,0 }; //북 동 남 서 방향
int x_arr[4] = { 0,1,0,-1 };

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

	cin >> t;

	while (t--) {
		int cy = 0, cx = 0, dir = 0;
		int minx = 0, miny = 0, maxx = 0, maxy = 0;

		string arr;
		cin >> arr;

		for (int i = 0; i < arr.size(); i++) {
			int ny, nx;
			if (arr[i] == 'F') {
				cy = y_arr[dir%4] + cy;
				cx = x_arr[dir%4] + cx;
			}
			else if (arr[i] == 'B') {
				cy = y_arr[(dir+2)%4] + cy;
				cx = x_arr[(dir+2)%4] + cx;
			}
			else if (arr[i] == 'R') {
				dir++;
			}
			else if (arr[i] == 'L') {
				dir--;
				if (dir < 0)
					dir += 4;
			}

		//	cout << i + 1<<"x y" << cx << ' ' << cy <<" dir "<<dir<<endl;
			if (maxx < cx)
				maxx = cx;
			if (maxy < cy)
				maxy = cy;
			if (minx > cx)
				minx = cx;
			if (miny > cy)
				miny = cy;
		}
		//cout << maxy << ' ' << maxx << ' ' << miny << ' ' << minx << endl;
		cout << ((maxy - miny)* (maxx - minx)) << "\n";

	}


	return 0;
}

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

dp문제입니다.

우선 벽장문을 이동할 때, 가장 가까운 문을 옮기는 그리디적인 방식이 항상 최선이 아니라는 것을 알아야 합니다.

ex) 1 0 0 0 1 0 이런식으로 문이 있을때 3번으로 가야한다면 1번문을 이동할건가요? 5번문을 이동할건가요?

즉 모든 경우를 다 고려해주어야 합니다. 이때 시간의 효율성을 위해 dp를 사용해야합니다. 

즉, 이전에 방문했던 값을 마킹해두며 진행해야 합니다.

dp를 사용해야하는 것을 인지했으면, 점화식을 도출해야 합니다.

dp[1번 문위치][2번 문위치][현재 인덱스] = min( 1번 문위치 옮겼을때 최소값, 2번 문위치 옮겼을때 최소값)

이를 토대로 top-down 방식을 사용해서 구현했습니다.

재귀식은 이렇게 구현했습니다.

int solved(int o1, int o2,int cnt) {

	if (cnt == k + 1)
		return 0;

	int &ret = dp[o1][o2][cnt];
	if (ret != -1)
		return ret;
	ret = 0;
	ret = min(abs(arr[cnt] - o1) + solved(arr[cnt], o2, cnt + 1), abs(arr[cnt] - o2) + solved(o1, arr[cnt], cnt + 1));
	return ret;
}

아래는 정답코드입니다.

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

int n = 0, k = 0;
int open1, open2;
int arr[21] = { 0, };
int dp[21][21][21];

int solved(int o1, int o2,int cnt) {

	if (cnt == k + 1)
		return 0;

	int &ret = dp[o1][o2][cnt];
	if (ret != -1)
		return ret;
	ret = 0;
	ret = min(abs(arr[cnt] - o1) + solved(arr[cnt], o2, cnt + 1), abs(arr[cnt] - o2) + solved(o1, arr[cnt], cnt + 1));
	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	memset(dp, -1, sizeof(dp));

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

	cout<<solved(open1, open2, 1)<<endl;


	return 0;
}

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

전형적인 dp문제입니다.

결과를 도출할때 2가지로 나누어 생각했습니다.

• 끝이 0일때,
• 끝이 1일때

만약 n=4, k=1일때, 경우의수는 

1100

0110

0011

1101

1011

이렇게 5가지 입니다.

즉, 

i는 n, j는 k 값일때

각각

dp[idp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1]
dp[i][j][1] = dp[i - 1][j][0] + dp[i - 1][j - 1][1]

아래는 정답코드입니다.

#include <iostream>
using namespace std;
int t,n, k;
int dp[101][101][2] = { 0, };
int main() {

	cin >> t;
	
	dp[1][0][0] = 1; //n k 마지막수가 0인지 1인지
	dp[1][0][1] = 1;

	for (int i = 2; i <=100; i++) {
		for (int j = 0; j < i; j++) {
			dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1];
			dp[i][j][1] = dp[i - 1][j][0] + dp[i - 1][j - 1][1];
		}
	}
	while (t--) {
		cin >> n >> k;
		cout << dp[n][k][0] + dp[n][k][1] << "\n";

	}
	
}

문제풀이:www.acmicpc.net/problem/9251

LCS알고리즘에 대한 설명은 아래 링크를 참고해주세요.

gusdnr69.tistory.com/192

아래는 정답코드입니다.

 LCS2, 팰린드롬 문제들도 함께 풀어보시면서 익혀보세요.

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

string a, b;
int dp[1001][1001] = { 0, };
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	string temp1, temp2;
	cin >> temp1 >> temp2;

	a = ' ' + temp1;
	b = ' ' + temp2;

	for (int i = 1; i < b.size(); i++) {
		for (int j = 1; j < a.size(); j++) {
			if (b[i] == a[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}

	cout << dp[b.size() - 1][a.size() - 1] << endl;


	return 0;
}

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

LCS문제입니다.

LCS에 대한 설명은 아래 링크를 참고하세요

gusdnr69.tistory.com/192

해당 문제에서는 부분수열을 출력해야합니다.

이때 역순으로 올라가면서 하나씩 저장해준후에, 

역순으로 출력해주면 됩니다.

아래는 알파벳을 저장하는 코드입니다.

	int col = a.size() - 1;
	int row = b.size() - 1;

	while (dp[row][col]) {

		if (dp[row][col] == dp[row - 1][col]) {
			row--;
		}
		else if (dp[row][col] == dp[row][col - 1]) {
			col--;
		}
		else {
			result += a[col];
			row--, col--;
		}

	}

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

#include<iostream>
#include <string>
#include <algorithm>
using namespace std;
string a, b;
string result;
int dp[1001][1001] = { 0, };

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	string temp1, temp2;
	cin >> temp1;
	cin >> temp2;
	
	a = ' ' + temp1;
	b = ' ' + temp2;
	
	
	for (int i = 1; i < b.size(); i++) {
		for (int j = 1; j < a.size(); j++) {
			if (a[j] == b[i]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}

	
	
	int col = a.size() - 1;
	int row = b.size() - 1;

	while (dp[row][col]) {

		if (dp[row][col] == dp[row - 1][col]) {
			row--;
		}
		else if (dp[row][col] == dp[row][col - 1]) {
			col--;
		}
		else {
			result += a[col];
			row--, col--;
		}

	}

	cout << dp[b.size() - 1][a.size() - 1] << endl;
	if (result.size() > 0) {
		reverse(result.begin(), result.end());
		cout << result << endl;
	}
	return 0;
}

a와 b 앞에 ' '를 추가해주면서 1base로 시작할 수 있도록 만들었습니다.

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

해당 문제는 lcs와 연관이 있다.

LCS의 갯수를 통해서 팰린드롬을 위한 갯수 도출할수 있기 때문입니다.

논리자체는 굉장히 간단하다.

• 1. 입력받은 문자열과 문자열을 뒤집은 것과의 lcs 구하기
• 2. N - LCS 이 정답

우선 lcs는 아래 링크를 통해서 이해하자

gusdnr69.tistory.com/192

아래는 정답코드이다.

팰린드롬이 LCS와 연관이 있다는 것을 이해하는 것이 어려운 문제이고, 

구현 난이도는 매우 낮은 문제이다.

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

int n = 0;
string arr;
string arr_re;
int dp[5001][5001] = { 0, };

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

	cin >> n;
	cin >> arr;
	arr_re = arr;
	reverse(arr_re.begin(), arr_re.end());
	for (int i = 0; i < n; i++) {
		if (arr_re[0] == arr[i]) dp[0][i] = 1;
		else if(dp[0][i - 1] == 1)dp[0][i] = 1;

		if (arr_re[i] == arr[0]) dp[i][0] = 1;
		else if (dp[i - 1][0] == 1)dp[i][0] = 1;
	}

	for (int i = 1; i < n; i++) {
		for (int j = 1; j < n; j++) {
			if (arr_re[i] == arr[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}
	/*
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << dp[i][j] << ' ';
		}
		cout << endl;
	}*/

	cout << n - dp[n - 1][n - 1] << endl;


	return 0;
}

LCS는 longest common subsequence의 약자입니다. 우리나라 말로는 최장 공통 부분 수열을 의미합니다. 

이해하기 쉽도록 longest common substring 과 비교해보겠습니다. 

substring은 연속된 부분 문자열이고 subsequence는 연속적이지는 않은 부분 문자열이다.

예를 들어 iamaboy에서 amab는 연속하는 부분 문자열이므로 substring이 되고 aaby는 순서는 일치하지만 연속적이지는 않는 subsqeunce가 됩니다.

그렇다면 두 문자열에서의 LCS는 어떻게 구할까요?

예시를 들겠습니다. 두 문자열은 ACCGATCG와 GACAT 입니다.

우선 전체는 아래와 같은 구조입니다.  ( 아래에 설명이 나옵니다. 우선은 이해하지 마시고 그렇구나 넘어가세요.)

문자열 ACCG와 G의 부분 수열은 G하나 입니다. 

문자열 ACCGATCG와 G의 최대 부분 수열은 G하나 입니다. 

문자열 ACCGATCG와 GA의 최대 부분 수열은 G,A  총 2개 입니다. 

위와 같은 형태로 진행하다보면 아래와 같은 그림이 만들어 지는 것입니다. 

점화식의 형태로 나타낸다면, 

만약 두 알파벳이 같을때, dp[i][j] = dp[i -1][j - 1] +1

두 알파벳이 다를때는 dp[i][j] = max(dp[i -1][j], dp[i][j -1])

LCS관련 문제 모음입니다.

다 풀어보세요!

 백준 알고리즘

• https://www.acmicpc.net/problem/9251

• https://www.acmicpc.net/problem/9252

• https://www.acmicpc.net/problem/5582

•  www.acmicpc.net/problem/5502