대엉코딩

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

1. 풀이방법

- N개의 수중에 주어지는 M개의 수들이 각각 존재하는 지 확인해야합니다

- 선형탐색을 진행할 경우 O(N*M) 이므로 약 10,000,000,000 는 시간초과에 걸릴 것 같습니다.

- O(NlogN) 정렬 + O(M*logN) 이분탐색 으로 해결했습니다.

2. 주의사항

- 조건으로 인한 시간초과

3. 나의코드

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

int Narr[100000];
int N, M;
bool existnum(int target) {
	int ep = N - 1;
	int sp = 0;
	int mid;
	while (sp<=ep) {
		mid = (sp + ep) / 2;
		if (Narr[mid] == target) { return true; }
		else if (Narr[mid] < target) {
			sp = mid + 1;
		}
		else if (Narr[mid] > target) {
			ep = mid - 1;
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> Narr[i];
	}
	sort(Narr, Narr+N); //이분탐색을 위한 정렬
	cin >> M;
	int target;
	for (int i = 0; i < M; i++) {
		cin >> target;
		cout << existnum(target)<<"\n";
	}
	return 0;
}

오늘은 프로그래머스 해쉬문제를 풀면서 하나 알게된 사실이 있습니다..

c++ algorithm 라이브러리 sort()를 이용할 경우

문자열은 사전 순으로 정렬이 된 결과가 나옵니다.

unordered_map의 경우 잘 안써와서 미숙한데, 그래도 알아두어야 겠다 생각하여 따로 작성해서 

게시글로 올려야 겠네요....! 

오늘은 완전탐색 문제를 풀다가 사용한 c++의 next_permutation 입니다.

사실 알고리즘 동아리를 할 때, 한번 설명을 들은 적이 있어 알고는 있었는데 대부분의 문제풀이 때 그냥 DFS 완탐 으로 모든 경우의 수를 구해서 문제를 풀어왔었는데요.

오랫만에 문제를 풀어서 그럴수도 있겠지만, 익숙치 않은 IDE 에서 짜다보니 코드가 길어질수록 미세한 실수도 많이 나오고 다른 디버깅 환경에서 그 실수를 찾아내기가 생각보다 오래걸려서 next_permutation도 제대로 알아보고 익숙해져볼 생각입니다.

1. 조건

- next_permutation은 정렬을 조건으로 합니다.

- 물론, 원하는 출력에 따라 조건을 변경해서 출력하면 됩니다.

- 기본적인 5개의 후보로 부터 모든 가능한 5개 사이즈의 조합을 구하는 경우,

   이 후보들은 모두 오름차순 정렬이 되어 있어야 합니다. ( ex - 1 2 3 4 5 )

1-1. 

 - 특수한 상황이지만 기존 배열(벡터)의 상태가 { 7, 5, 1, 2, 3 }일 경우,

   7과 5는 앞에 고정된 상태로 1,2,3 만 변경됩니다.

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

	vector<int> arr_1{ 1,5,5,7 };

	do {
		for (int i = 0; i < arr_1.size(); i++) {
			cout << arr_1[i] << " ";
		}
		cout << "\n";
	} while (next_permutation(arr_1.begin(), arr_1.end()));
	cout << "\n";

	return 0;
}

** 잘못된 내용이 있으면 알려주세요 **

www.acmicpc.net/problem/1965

1. 풀이방법

- 간단하게 생각하면 매우 간단합니다. 

- 저 같은 경우 처음에 막혔던 부분이 보통의 dp문제에서 dp테이블은 각각의 n에 따른 정답? 을 가지고 있습니다.

- 이런식으로 짜려고 고민을 하다 보니 상당히 구현이 까다로웠습니다.

- 예를 들면 테스트케이스 가 1, 6, 2, 5, 7, 3, 5, 6   총 8개 인데

- 보통의 dp 테이블이면 만약 dp[6]을 뽑으면 최대치는 1,2,5,7 로서 4가 나와야 하고 

- 이때의 상자의 바깥껍질의 크기인 7을 저장하면 dp[7]을 구하려고 할 때 1,2,5,7,과 1,2,3, +5 를 비교하는 것이 힘들었습니다.

- 설명하기가 조금 곤란한데, 비슷한 고민을 하신 분들은 공감을 하시리라....조심스럽게 생각해봅니다....

- 그래서 이 문제의 경우 n이하의 각각의 정답(즉 최대 상자의 수)를 dp에 저장하는 것이 아니라 

- n에 크기를 늘려가면서 그때까지 차곡차곡 쌓기만한 크기를 저장해 놓은 다음 출력 전에 정렬을 해서 max 값을 

- 출력하였습니다. 물론 정렬(소팅)을 하지않고 최대값만 갱신해도 상관 없습니다.

- 이런식으로 할경우 사실 정렬 전에 dp[6]에는 상자의 개수 3 (1,2,3) dp[5]에는 4 (1,2,5,7) 이 들어가 있습니다.

- 그러므로 n이 6일 때의 정답이 테이블에 들어가 있는 것은 아닌 것이죠. 정렬을 해서 출력을 해줘야 정답이 나오는 

- 것 입니다. 하지만 이렇게 하면 문제의 요구사항에는 전혀 에러가 없고, 구현이 편해집니다.

2. 주의사항

- 위에 기재.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int dp[1001]; // 사실상 정확한 dp를 가지고 있는 테이블은 아니다.
int n;
int narr[1001]; //상자의 크기


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) { //초기화
		cin >> narr[i]; dp[i] = 1;
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j < i; j++) {
			if (narr[i] > narr[j] && dp[i]<dp[j]+1) {
				dp[i] = dp[j]+ 1;
			}
		}
	}
	sort(dp + 1, dp + (n + 1));
	cout << dp[n];

	return 0;
}

www.acmicpc.net/problem/11652

1. 풀이방법

- 정렬을 하고 , 앞에서부터 쭉 살피면서 연속된 수를 체크하고 교체 및 갱신을 수행한다.

- 값의 범위는 -2^64 ~ 2^64 까지 이므로 대략 10^19정도 이므로 카드의 값은 long long 타입을 사용해주자

- 값을 오름차순으로 정렬을 해준 후 작업을 수행

2. 주의사항

- 첫번째, 값이 달라질때만 갱신작업을 수행하므로 배열의 마지막이 왔을때는 비교작업을 한번 수행해주어야 한다.

- 두번쨰, 카드가 1개일 때를 생각해보면 maxcount=1, resultvalue=cardset[0]로 초기화 하자 

  (n이 1이면 for 문을 돌지 않으므로 ---> 100% 쯤에서 틀렸습니다가 나오면 이 문제)

- 물론 주의사항은 모두 구현 방식에 따라 다를 수 있습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int n;
long long cardset[100001];
int maxcount;
long long resultvalue;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> cardset[i];
	}
	sort(cardset, cardset + n);
	maxcount = 1;
	resultvalue = cardset[0];
	int tmpcount = 1;
	for (int i = 1; i < n; i++) {
		if (cardset[i] == cardset[i - 1]) { 
			tmpcount++;
			if (i == n - 1) { //달라질때에만 값을 갱신하므로 , 마지막은 따로 계산해주어야함
				if (tmpcount > maxcount) { //같을때는 갱신하지 않는다.
					maxcount = tmpcount; resultvalue = cardset[i];
				}
			}
		}
		else {  
			if (tmpcount > maxcount) { //같을때는 갱신하지 않는다.
				maxcount = tmpcount; resultvalue = cardset[i - 1]; 
			}
			tmpcount = 1; }
	}
	cout << resultvalue;
	return 0;
}

www.acmicpc.net/problem/2251

1. 풀이방법

- 물을 옮겨 담는 횟수에 제한이 없으므로 모든 경우의 수를 다 살펴보아야겠다고 생각하여

- dfs를 통해서 모든 경우의 수를 탐색했습니다.

- 종료조건을 걸어야 할까를 고민하다가 a,b,c 에 관한 3차원배열을 선언하여,

- 이미 체크를 했던 물의양 set이면 재귀를 통해 들어가지 않도록 하여 종료가 되게끔 구현하였습니다.

- 붓는 물의 양은 붓는 쪽의 물의 양과 부으려는 물통의 빈자리 중 더 적은 양 만큼을 부었습니다

2. 주의사항

- 종료조건 파악 및 구현

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int a, b, c;
bool already[201];
bool visitcheck[201][201][201];
vector<int> resultarr;

struct waterball {
	int ax, bx, cx;
};

void dfs(int ta, int tb, int tc) {
		visitcheck[ta][tb][tc] = true;
		if (ta==0) {
			if (already[tc] == false) {
				resultarr.push_back(tc);
				already[tc] = true;
			}
		}
		if (ta != 0 && tb != b) { //a에서 b로
			int tmpw = min((b - tb), (ta)); //b의 남은공간과 a의 물의 양중 작은 것
			if(visitcheck[ta-tmpw][tb+tmpw][tc]==false) dfs(ta - tmpw, tb + tmpw, tc);
		}
		if (ta != 0 && tc != c) { //a에서 c로
			int tmpw = min((c- tc), (ta)); //b의 남은공간과 a의 물의 양중 작은 것
			if (visitcheck[ta - tmpw][tb][tc+tmpw] == false) dfs(ta - tmpw, tb, tc+tmpw);
		}
		if (tb != 0 && tc != c) {//b에서 c로
			int tmpw = min((c - tc), (tb)); 
			if (visitcheck[ta][tb - tmpw][tc+tmpw] == false) dfs(ta , tb-tmpw, tc + tmpw);
		}
		if (tb != 0 && ta != a) {//b에서 a로
			int tmpw = min((a - ta), (tb)); 
			if (visitcheck[ta + tmpw][tb - tmpw][tc] == false)dfs(ta + tmpw, tb - tmpw, tc);
		}
		if (tc != 0 && ta != a) {//c에서 a로
			int tmpw = min((a - ta), (tc));
			if (visitcheck[ta + tmpw][tb][tc-tmpw] == false)dfs(ta + tmpw, tb , tc - tmpw);
		}
		if (tc != 0 && tb != b) {//c에서 b로
			int tmpw = min((b - tb), (tc));
			if (visitcheck[ta][tb + tmpw][tc-tmpw] == false)dfs(ta, tb + tmpw, tc - tmpw);
		}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> a >> b >> c;
	dfs(0, 0, c);
	sort(resultarr.begin(), resultarr.end());
	for (int i = 0; i < resultarr.size(); i++) {
		cout << resultarr[i] << " ";
	}
	return 0;
}

www.acmicpc.net/problem/18511

1. 풀이방법

- 처음 문제를 보고 눈에 띈 숫자는 N이 최대 100,000,000 이므로 선형적으로 증가시켜가며 N과 비교하면 시간초과

- 그러면 주어진 집합을 보고 숫자를 구성해서 N과 비교를 해야 겠다.

- 그래서 자릿수 계산하고 앞자리 수 부터 비교를 해 가면서 어떤 원소를 자릿수에 넣고 해야겠다~~ 라면서 하다보니

- 되게 다양한 경우의 수가 있고 생각보다 너무 복잡하였습니다.....하

- 그래서 문제를 다시 읽어보니..... 매우 쉬워지는 이유가 하나 있었습니다 K의 원소의 개수가 최대 3개 라는 것....!

- 저는 K의 집합 원소가 1~9 이고 집합의 원소의 수 도 역시 최대 10개라고 당연시? 생각해서...

- 이 모두를 조합하는 수는 너무 많다 라고 생각했었는데 아니였습니다...

- 최대 3개 이므로 그냥 모든 조합을 만들어 내서 N가 비교하고 N보다 작거나 같을경우의 수를 모두 벡터에 넣고

- 그 중 최대값을 출력하였습니다.

2. 주의사항

- 문제를 똑바로 파악하고 시작할 것 !!!!

3. 나의코드

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

int n, k,tmp;
vector<int> numarr;
vector<int> resultarr; //n을 쪼개놓자

bool compare(int& lhs, int& rhs) {
	if (lhs > rhs) return true;
	else return false;
}

void makecase(int num,int cnt) {
	if (cnt!=0 && num <= n) { 
		resultarr.emplace_back(num);
	}
	if (num > n) return;
	for (int i = 0; i < k; i++) {
		if (cnt == 0) { makecase(num * numarr[i],cnt+1); }
		else makecase(num*10+numarr[i],cnt+1);
	}
}

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

	cin >> n >> k;
	
	for (int i = 0; i < k; i++) {
		cin >> tmp;
		numarr.emplace_back(tmp);
	}
	sort(numarr.begin(), numarr.end(), compare);
	makecase(1,0);
	sort(resultarr.begin(), resultarr.end(), compare);
	cout << resultarr[0];
	return 0;
}

www.acmicpc.net/problem/1655

1. 풀이방법

 - 직관적인 풀이 : 중간값을 의미를 떠올리면 수빈이가 숫자를 하나 외칠 때 마다 정렬을 수행 후 중간에 위치한

                        값을 뽑아내면 된다 . ---> 시간초과 (아마? 작성해서 제출해보진 않았습니다.)

 - 우선순위 큐를 이용했습니다.

   (1단계)

      -가장 큰 값을 뽑아내는 pqless와 가장 작은 값을 뽑아내는 pqgreater를 선언 후 

      - 매 단계 마다, 그 전의 중간값을 기준으로 pqless에 넣을지 pqgreater에 넣을지를 판단해서 우선순위 큐에 삽입

   (2단계)

      - 중간값을 뽑아내기 위해서는 한쪽 우선순위 큐만 너무 커져 버리면 안됩니다 즉 데이터의 수가 1차이 이하로 나야

         하므로 2이상 차이가 날경우 큰 쪽의 우선순위 큐의 값을 작은 크기의 우선순위 큐 로 옮겨주는 작업을 수행

   (3단계)

      - 중간값을 뽑아내서 출력 (다음단계를 위한 중간값 저장)

      - 문제 조건에 따라서 두 우선순위큐의 사이즈를 비교한후 (편의상) 왼쪽 위에 뽑아낼지 오른쪽 위에서 뽑아낼지

         결정하면 됩니다.

2. 주의사항

 - 개인적으로는 우선순위 큐 두개를 사용해야 겠다 라는 생각이 든 이후 부터는 상대적으로 매우 쉬웠습니다.

 - 문제 조건에 따른 단계별 구현만 차근차근 해주시면 되겠습니다.

3. 나의코드

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

int N;
int centervalue;

priority_queue<int, vector<int>> pqless;
priority_queue<int, vector<int>, greater<int>> pqgreater;

void InputToQueue(int num) {
	if (num <= centervalue) { pqless.push(num); }
	else { pqgreater.push(num); }
}
void ModifyQueue() {
	if (pqless.size() > pqgreater.size() + 1) { //2이상 차이날 경우
		int modinum = pqless.top();
		pqless.pop();
		pqgreater.push(modinum);
	}
	else if (pqgreater.size() > pqless.size() + 1) { //2이상 차이날 경우
		int modinum = pqgreater.top();
		pqgreater.pop();
		pqless.push(modinum);
	}
}
void GetCenterValue() {
	if (pqless.size() >= pqgreater.size()) {
		centervalue = pqless.top();
	}
	else {
		centervalue = pqgreater.top();
	}
	cout << centervalue << "\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	int tmp;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		if (i == 0) {
			pqless.push(tmp); centervalue = tmp; cout << centervalue << "\n"; continue;
		}
		InputToQueue(tmp);
		ModifyQueue();
		GetCenterValue();
	}
	return 0;
}