이것 저것 &

#include <iostream>
using namespace std;

int n, q;
int arr[500001] = { 0, };
int qarr[500001] = { 0, };


int binarysearch(int v, int s, int e) { // recursion 

	//1.base condition
	if (s > e)
		return -1;

	//2.divide
	int m = (s + e) / 2;

	if (v == arr[m]) return m;
	else if (v > arr[m]) return binarysearch(v, m + 1, e);
	else return binarysearch(v, s, m - 1);

}



int binarysearch2(int v, int s, int e) { // while 

	int start_val = s;
	int end_val = e;

	while (start_val <= end_val) {
		int m = (start_val + end_val) / 2;
		if (v == arr[m]) return m;
		else if (v > arr[m]) start_val = m + 1;
		else end_val = m - 1;
	}

	return -1;
}

int main() {

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	cin >> q;
	for (int i = 0; i < q; i++)
		cin >> qarr[i];


	for (int i = 0; i < q; i++) {
		int val = binarysearch(qarr[i],0,n-1);
		cout << val;
		if (i != (q - 1))
			cout << ' ';
	}
	cout << endl;

	return 0;
}

#include <stdio.h>
#define MAXSIZE 100000

const int LM = (int)100001;
int index[LM], temp[LM];

void mergesort(int s, int e, int* a, int* b) {

    //1. base condition
    if (s >= e)
        return;

    //2.divide
    int mid = (s + e) / 2;
    

    //3. conquer
    mergesort(s, mid, a, b);
    mergesort(mid + 1, e, a, b);

    //4. merge
    int i = s, j = mid + 1;
    for (int k = s; k <= e; k++) {

        if (i > mid)
            b[k] = a[j++];
        else if (j > e)
            b[k] = a[i++];
        else if (a[i] > a[j])
            b[k] = a[j++];
        else
            b[k] = a[i++];
    }

    //5. copy
    for (int k = s; k <= e; k++) {
        a[k] = b[k];
    }
}

출처: https://www.acmicpc.net/problem/21608

구현문제입니다.

1. 단순구현으로 해결했다.

결론적으로 반복문을 통해서 각각의 학생들의 자리를 픽스시켜 주면 되기 때문에, 천천히 조건에 맞게 구현하면 된다.

2. 3가지 조건중 1번, 2번을 통해서 각각의 학생별로 해당하는 위치를 도출했다. 3번은 우선순위에 의해서 일반적인 반복문을 사용하면 자동으로 결정됨.

1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

그런데 왠 런타임 에러??

주의점은 만약 좋아하는 친구와, 빈칸 모두 없는 상황일때는 3번 조건에 의해서 가장 가까운 칸을 선택하도록 예외처리를 추가해주어야 한다. (본 코드 storePosition 함수 아래쪽 참고)

정답 코드

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

vector <int> friends[401];
vector <int> vec; // 순서저장
int arr[25][25] = { 0, }; // 위치가 픽스 되면
int n = 0;
int result = 0;

int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };

void storePosition(int& y, int& x, int v) {


	int rf = 0;
	int rb = 0;
	int ry = 0;
	int rx = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr[i][j] != 0)
				continue;

			int cy = i;
			int cx = j;
			int fav = 0;
			int bla = 0;


			for (int k = 0; k < 4; k++) {
				int ny = cy + y_ar[k];
				int nx = cx + x_ar[k];

				if (ny < 1 || ny > n || nx < 1 || nx > n)
					continue;

				for (int u = 0; u < 4; u++) {
					if (arr[ny][nx] == friends[v][u])
						fav++;
					else if(arr[ny][nx] == 0)
						bla++;
				}
			}

			if (fav > rf) {
				rf = fav;
				rb = bla;
				ry = cy;
				rx = cx;
			}
			else if (fav == rf) {
				if (bla > rb) {
					rb = bla;
					ry = cy;
					rx = cx;
				}
			}

		}
	}



	if (ry == 0 && rx == 0) { // 중요
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (arr[i][j] == 0) {
					ry = i, rx = j;
					break;
				}
			}
			if (ry != 0 && rx != 0)
				break;
		}

	}

	y = ry, x = rx;

}

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

	cin >> n;

	for (int i = 0; i < n*n; i++) {
		int temp;
		int temp2[4];

		cin >> temp;
		vec.push_back(temp);

		for (int j = 0; j < 4; j++) {
			cin >> temp2[j];
			friends[temp].push_back(temp2[j]);
		}
	}


	for (int i = 0; i < n*n; i++) {
		int v = vec[i];
		int y = 0; int x = 0;
		storePosition(y, x, v);
		arr[y][x] = v;



	}


	// 점수 계산 

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {

			int cy = i;
			int cx = j;
			int cnt = 0;

			for (int k = 0; k < 4; k++) {
				int ny = cy + y_ar[k];
				int nx = cx + x_ar[k];

				if (ny < 1 || ny > n || nx < 1 || nx > n)
					continue;

				for (int u = 0; u < 4; u++) {
					if (arr[ny][nx] == friends[arr[cy][cx]][u])
						cnt++;
				}

			}

			if (cnt == 1)
				result += 1;
			else if (cnt == 2)
				result += 10;
			else if (cnt == 3)
				result += 100;
			else if (cnt == 4)
				result += 1000;
		}
	}

	cout << result << endl;


	return 0;
}

문제링크: https://www.acmicpc.net/problem/12886

체감 골3 이상이었던 bfs 문제 ㅠㅠ

접근방식

1. dp방식, bfs방식 등이 가능할 것 같았다. 

2. 만만한 bfs로 도전

만약 a, b, c의 총합이 3으로 딱 나눠떨어지지 않는다면 무조건 결과는 0이다. 

1000x1000x1000 배열을 생성하게 되면 메모리 초과이다. 

이때, 총합의 합이 같기 때문에 1000x1000만으로도 a,b,c의 값을 저장할 수 있다는 것을 파악해야 한다.

큐에 들어가는 값은 정렬을 하여서 사용한다.

그 이유는 중복을 방지하기 위함과 런타임에러(OutOfBounds)를 방지하기 위함

문제풀이 

1.  큐를 사용한 bfs 구현

2. y_ar과 x_ar를 통해서 현재 값을 기준으로 탐색해야 하는 값들을 도출

정답코드

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

int visited[1001][1001] = { 0, };
int a, b, c, d = 0;

int bfs() {

	queue <pair<int, int>> que;
	que.push(make_pair(a, b));
	visited[a][b] = 1;

	while (!que.empty()) {
		int ca = que.front().first;
		int cb = que.front().second;
		int cc = d - ca - cb;
		que.pop();

		if (ca == cb && ca == cc)
			return 1;

		int n_x[3] = { ca,ca,cb };
		int n_y[3] = { cb,cc,cc };

		for (int i = 0; i < 3; i++) {
			int na = n_x[i];
			int nb = n_y[i];
			if (na < nb)
				nb -= na, na += na;
			else if (na > nb)
				na -= nb, nb += nb;
			else
				continue;
			int nc = d - na - nb;

		
			int ra = min(min(na, nb), nc);
			int rb = max(max(na, nb), nc);

			if (visited[ra][rb] == 0) {
				visited[ra][rb] = 1;
				que.push(make_pair(ra, rb));
			}

		}


	}

	return 0;

}

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

	cin >> a >> b >> c;
	d = a + b + c;

	if ((a + b + c) % 3 != 0)
		cout << 0 << endl;
	else
		cout << bfs() << endl;
	

	return 0;
}

문제링크: https://www.acmicpc.net/problem/11286

우선순위 큐를 사용하여서 해결하는 문제

접근방식

1.  절댓값에 대한 순서를 우선순위 큐를 활용하여 해결하자!

문제풀이 

1.  pair형태의 우선순위 큐 생성

2. min-heap형태로 구성!

근데, "절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력" 하라는 조건이 있으니 두번째 원소값을 변형 하여서 구현하기

정답코드

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

priority_queue <pair<int, int>> que;
int n = 0;
int num = 0;

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

	cin >> n;
	while (n--) {
		cin >> num;
		if (num == 0) {
			if (que.size() == 0)
				cout << 0 << "\n";
			else {
				cout <<  que.top().first * que.top().second  << "\n";
				que.pop();
			}
		}
		else {
			if(num > 0)
				que.push(make_pair(-1 * abs(num),-1));
			else
				que.push(make_pair(-1 * abs(num), 1));
		}

	}

	return 0;
}

문제링크: https://www.acmicpc.net/problem/15924

dp문제이고 top-down방식으로 해결하였다.

접근방식

1. 모든 경우를 고려해야 하는데 브루트 포스로는 시간초과가 날 것같다

즉, dp로 해결하는 문제

2. top-down방식으로 쉽게 해결이 가능하다.

문제풀이 

1.  모든 좌표에서 도달 가능한 좌표를 탐색

이때, dp에 값을 저장해두었다가 같은 좌표를 탐색할때는 곧바로 반환해주는 형태로 구현

정답코드

#include <iostream>

using namespace std;

int n, m;
char arr[3001][3001];
long long dp[3001][3001];
long long result = 0;

long long solved(int y, int x) {
	if (y == n && x == m)
		return 1;

	long long& ret = dp[y][x];
	if (ret != -1)
		return ret;
	ret = 0;
	if (arr[y][x] == 'B') {
		if ((y + 1) <= n)
			ret += solved(y + 1, x);
		if ((x + 1) <= m)
			ret += solved(y, x + 1);
	}
	else if (arr[y][x] == 'E') {
		if ((x + 1) <= m)
			ret += solved(y, x + 1);
	}
	else {
		if ((y + 1) <= n)
			ret += solved(y + 1, x);
	}

	ret %= 1000000009;

	return ret;
}

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

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
			dp[i][j] = -1;
		}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			result += solved(i, j);

	cout << result % 1000000009 << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/13703

dp문제이고 top-down방식으로 해결하였다.

접근방식

1. 모든 경우를 고려해야 하는데 브루트 포스로는 시간초과가 날 것같다

즉, dp로 해결하는 문제

2. top-down방식으로 쉽게 해결이 가능하다.

문제풀이 

1.  높이 수면에 닿는 경우는 항상 배제시켜주고, 

시간이 다 될때 까지 수면에 닿지 않았다면 + 1 을 추가해주는 형태로 진행함

정답코드

#include <iostream>
using namespace std;

long long dp[64 * 2][64];
int n, k;

long long solved(int kk, int nn) {
	
	if (kk == 0)
		return 0;
	if (nn == 0)
		return 1;

	long long& ret = dp[kk][nn];
	if (ret != -1)
		return ret;
	ret = 0;

	ret += solved(kk-1, nn-1);
	ret += solved(kk+1, nn-1);

	return ret;
}

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

	cin >> k >> n;

	for (int i = 0; i < 64*2; i++)
		for (int j = 0; j < 64; j++)
			dp[i][j] = -1;

	cout << solved(k, n) << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/1715

문제 접근에 대해서 이해하면 쉽게 구현한 문제이다.

우선, 그리디한 방식으로 문제를 도출할 수 있다는 것을 이해해야 한다!

접근방식

1. 생각해보면, 항상 작은수를 먼저 처리해주면 최소값이 도출이 된다는 것을 알수 있다.

2. 그렇다면 새로 추가되는 수는 어떻게 관리해주어야 할까? 

새로 수를 넣어줄때 마다 정렬을 해야하나? 

아니다!

그냥 편하게 우선순위 큐를 사용하면 될 일이다. 

자동으로 lgn번의 탐색으로 수를 정렬된 상태로 보관해주기 때문에

해당 문제에 가장 적합한 자료구조이다.

문제풀이 

1.  구현 자체는 너무나도 단순하다.

priority_queue를 사용하여 문제를 해결하자.

정답코드입니다.

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

int n = 0;
priority_queue <int> que;
long long result = 0;

int main() {
	cin >> n;

	int temp;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		que.push(temp * -1);
	}

	while (que.size() != 1) {

		int a = que.top() * -1;
		que.pop();
		int b = que.top() * -1;
		que.pop();

		result += (a + b);

		que.push( (a + b) * -1);


	}

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