Mist16's Dev Blog

문제

• 11053번 : 가장 긴 증가하는 부분 수열
• Rank : Silver II
• 링크 : https://www.acmicpc.net/problem/11053

풀이 전략

• for문을 사용하여, 현재 인덱스 앞에서 자기보다 큰, 방문할 수 있는 위치를 확인하여 진행한다.
  • 20 20 50 10 70 -> 20에서 50을 방문할 경우, 70 방문하는 경우로 재귀 함수 호출
    • 20 20 50 10 70 -> 70을 새로 방문 가능
    • 20 20 50 10 70 -> 더 방문할 곳이 없으므로 종료됨
• 해당 index를 방문할 때의 길이를 기록하여, 더 작은 부분수열로 방문하지 않도록 한다
  • A : 10 20 30 50 70  / i=4의 Length = 5 기록
  • B : 10 20 30 50 70  / i=4의 Length = 3 : 기록된 Length = 5보다 작으므로 방문하지 않음
• 일 때, 방문시 최대 길이를 기록해 둘 경우 Length = 5 에서만 방문하면 된다.
• 재귀함수로 구현하고, for loop를 사용한 호출이 끝난 후 최대 길이를 확인하여 기록한다.

void run(int idx, int current, int length)
{
	for (int i = idx; i < N; i++)
	{
		if (current < A[i] && visitLength[i] < length+1)
		{
			visitLength[i] = length + 1;
			run(i, A[i], length + 1);
		}
	}
	if (maxLength < length)
	{
		maxLength = length;
	}

}

전체 소스 코드

//Backjoon Problem No.11053
//https://www.acmicpc.net/problem/11053
//Mist16, 2022-03-01

#include <iostream>

using namespace std;

int A[1000]= { 0, };
int visitLength[1000] = { 0, };
int N = 0;

int maxLength = 0;

void run(int idx, int current, int length)
{
	for (int i = idx; i < N; i++)
	{
		if (current < A[i] && visitLength[i] < length+1)
		{
			visitLength[i] = length + 1;
			run(i, A[i], length + 1);
		}
	}
	if (maxLength < length)
	{
		maxLength = length;
	}

}

int main()
{
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	run(0, 0, 0);
	cout << maxLength;

	return 0;
}

Note

• 조건을 검사하지 않고, 방문하지 않을 경우에도 재귀함수를 호출할 경우에는 O(n!)가 되어 시간 초과로 실패하는 문제였다.

문제

• 17070번 : 파이프 옮기기
• Rank : Gold V
• 링크 : https://www.acmicpc.net/problem/17070

풀이 전략

• 파이프는 좌, 하단, 좌하단대각선으로만 움직인다.
  • 파이프라인이 재귀될 염려가 없으므로, 파이프 이동선을 기억할 필요는 없다.
• 모든 경우의 수를 탐색하여, 가능한 경우의 수를 합산한다.

//파이프 설치
int installPipe(int y, int x, int cond)
{
	int AllCases = 0;

	if (x == N-1 && y == N-1)
		return 1;

	if ((checkMap[y][x] & pipeCond::ConditionChecked) != pipeCond::ConditionChecked ) //unchecked, check
	{
		checkConstructProb(y, x);
	}
	//1. Left/LDown -> Left
	if (cond == pipeCond::Left || cond == pipeCond::LDown)
	{
		if((checkMap[y][x] & pipeCond::Left) == pipeCond::Left)
		{
			AllCases += installPipe(y, x + 1, pipeCond::Left);
		}
		
	}
	//2. Down/LDown -> Down
	if (cond == pipeCond::Down || cond == pipeCond::LDown)
	{
		if ((checkMap[y][x] & pipeCond::Down) == pipeCond::Down)
		{
			AllCases += installPipe(y + 1, x, pipeCond::Down);
		}
	}
	//3. All Cond -> LDown
	if ((checkMap[y][x] & pipeCond::LDown) == pipeCond::LDown)
	{
		AllCases += installPipe(y + 1, x + 1, pipeCond::LDown);
	}

	return AllCases;
}

• 이 때, 같은 위치의 파이프 설치여부를 여러번 체크하게 되므로, 다이나믹 프로그래밍으로 풀이한다.
  • enum을 사용하여 각 상태를 정의해둔 후, 비트연산자 배열에 저장한다.
  • 타설가능 파이프 외에 검사했는지 여부를 확인하게 하여, 타설불가능 지역을 계속해서 체크하는 것을 방지한다.

int checkMap[16][16] = { 0, };
enum pipeCond
{
	None = 0,
	Left = 1,
	LDown = 2,
	Down = 4,
	ConditionChecked = 8
};
//현재 위치에서 파이프 타설이 가능한지 체크
void checkConstructProb(int y, int x)
{
	int cond = pipeCond::ConditionChecked;
	//1. Left
	if (x + 1 < N)
	{
		if (pipeMap[y][x + 1] == 0)
			cond = cond | pipeCond::Left;
	}
	//2. Down
	if (y + 1 < N)
	{
		if (pipeMap[y + 1][x] == 0)
			cond = cond | pipeCond::Down;
	}
	//3. Left-Down
	if ((cond & pipeCond::Left) == (int)pipeCond::Left &&
		(cond & pipeCond::Down) == (int)pipeCond::Down)
	{
		if (pipeMap[y + 1][x + 1] == 0)
		{
			cond = cond | (int)pipeCond::LDown;
		}
	}
	checkMap[y][x] = cond;
}

전체 소스 코드

//Backjoon Problem No.17070
//Mist16, 2022-01-22

#include <iostream>

using namespace std;

enum pipeCond
{
	None = 0,
	Left = 1,
	LDown = 2,
	Down = 4,
	ConditionChecked = 8
};

int pipeMap[16][16] = { 0, };
int checkMap[16][16] = { 0, };
int N = 0;



//현재 위치에서 파이프 타설이 가능한지 체크
void checkConstructProb(int y, int x)
{
	int cond = pipeCond::ConditionChecked;
	//1. Left
	if (x + 1 < N)
	{
		if (pipeMap[y][x + 1] == 0)
			cond = cond | pipeCond::Left;
	}
	//2. Down
	if (y + 1 < N)
	{
		if (pipeMap[y + 1][x] == 0)
			cond = cond | pipeCond::Down;
	}
	//3. Left-Down
	if ((cond & pipeCond::Left) == (int)pipeCond::Left &&
		(cond & pipeCond::Down) == (int)pipeCond::Down)
	{
		if (pipeMap[y + 1][x + 1] == 0)
		{
			cond = cond | (int)pipeCond::LDown;
		}
	}
	checkMap[y][x] = cond;
}

//파이프 설치
int installPipe(int y, int x, int cond)
{
	int AllCases = 0;

	if (x == N-1 && y == N-1)
		return 1;

	if ((checkMap[y][x] & pipeCond::ConditionChecked) != pipeCond::ConditionChecked ) //unchecked, check
	{
		checkConstructProb(y, x);
	}
	//1. Left/LDown -> Left
	if (cond == pipeCond::Left || cond == pipeCond::LDown)
	{
		if((checkMap[y][x] & pipeCond::Left) == pipeCond::Left)
		{
			AllCases += installPipe(y, x + 1, pipeCond::Left);
		}
		
	}
	//2. Down/LDown -> Down
	if (cond == pipeCond::Down || cond == pipeCond::LDown)
	{
		if ((checkMap[y][x] & pipeCond::Down) == pipeCond::Down)
		{
			AllCases += installPipe(y + 1, x, pipeCond::Down);
		}
	}
	//3. All Cond -> LDown
	if ((checkMap[y][x] & pipeCond::LDown) == pipeCond::LDown)
	{
		AllCases += installPipe(y + 1, x + 1, pipeCond::LDown);
	}

	return AllCases;
}

int main()
{
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//input n, pipemap;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> pipeMap[i][j];
		}
	}
	cout << installPipe(0, 1, pipeCond::Left);

	return 0;
}

여담

• 골드 하위권 문제까지는 빠르게 풀 수 있는 거 같다. 고난이도 문제에 도전해볼 것.

문제

• 1202번 : 보석 도둑
• Rank : Gold II
• 링크

풀이 전략

• 보석의 정보를 담은 구조체를 만들어 list에 입력받은 뒤, price 기준으로 정렬하여 비싼 보석부터 확인하였다.
  • bool operator<(const Jewel s) const를 구현하여 정렬
• 가방의 경우 multiset에 저장한 뒤, lower_bound를 사용하여 비싼 보석부터 하나씩 매칭.
• 보석을 전부 확인하거나, 가방이 가득 찬 경우 종료.

소스 코드

//Backjoon Problem No.1202
//Mist16, 2022-01-21

#include <iostream>
#include <list>
#include <set>
using namespace std;

struct Jewel
{
	int weight;
	int price;
	Jewel(int wei, int pri) : weight(wei), price(pri) {}

	//정렬시 price 기준으로 소트되도록 설정
	bool operator<(const Jewel s) const
	{
		return this->price > s.price;
	}
};

list<Jewel> jewels;
multiset<int> Bags;

int N, K;

int main()
{
	int tempWeight, tempValue;
	long long int totalPrice = 0;
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> K;
	for (int i = 0; i < N; i++)
	{
		cin >> tempWeight >> tempValue;
		jewels.push_back(Jewel(tempWeight, tempValue));
	}
	for (int i = 0; i < K; i++)
	{
		cin >> tempWeight;
		Bags.insert(tempWeight);
	}
	jewels.sort();

	//가장 비싼 보석부터, 가능한한 가장 작은 가방에 적재
	for (auto iter1 = jewels.begin(); iter1 != jewels.end(); iter1++)
	{
		auto iter2 = Bags.lower_bound(iter1->weight);
		if (iter2 != Bags.end())
		{
			totalPrice += iter1->price;
			Bags.erase(iter2);
			//모든 가방이 찼을 경우 종료
			if (Bags.size() == 0)
			{
				cout << totalPrice;
				return 0;
			}
		}
	}
	cout << totalPrice;
	return 0;
}

여담

• 10만 개 이상의, 대량의 데이터를 가공하는 문제에서 자료구조 선택으로 인한 시간 문제가 발생하는 경우가 있다.
  • 각 자료구조별 순차접근/임의접근, 삽입/삭제 효율에 관해 정리해보는것도 좋을 듯.

문제

• 16566번 : 카드 게임
• Rank : Emerald V
• 링크

풀이 전략

• STL::Vector을 사용하여 한번에 입력받은 후 정렬 실행
  
  • 입력 이전에 reserve 공간 확보(대량의 move 실행 방지)
• 카드 입력을 비교하여 상대방의 카드가 MAX 이상, MIN 이하일 경우, 최저 카드를 제출
• 중간값일 경우 이진 검색을 실행하여 해당 카드를 이길 수 있는 카드를 찾아 제출
• 제출 후, 뽑은 카드는 Vector에서 삭제

결과

• 공개Test case, 자체 Test Case는 성공하나, 제출 진행시 시간부족으로 실패 처리
• 백준 테스트 환경에서 대형 케이스(카드 4백만, 뽑을 카드 1만)를 시도할 경우, 시간부족으로 실패하는 것으로 보임.
• Vector 대신 자체 이진 그래프를 작성하여 시도해볼 것

소스 코드

//Backjoon Problem No.16566
//Mist16, 2022-01-21

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


class cardDeck
{
private:
	vector<int> cardSet;

public:

	void setSize(int num)
	{
		cardSet.reserve(num);
	}
	void insertCard(int num)
	{
		cardSet.push_back(num);
	}

	void sortCards()
	{
		sort(cardSet.begin(), cardSet.end());
	}
    
	void deleteCard(vector<int>::iterator iter)
	{
		cardSet.erase(iter);
	}

	vector<int>::iterator getMinCard()
	{
		auto iter = cardSet.begin();
		return iter;
	}
	vector<int>::iterator getMaxCard()
	{
		auto iter = cardSet.end();
		iter--;
		return iter;
	}

	int popCard(int target)
	{
		vector<int>::iterator popOutCard;
		int outCardNum;
		if (target >= *getMaxCard() || target <= *getMinCard()) //losing hand
		{
			popOutCard = getMinCard();
			outCardNum = *popOutCard;
			deleteCard(popOutCard);
			return outCardNum;
		}
		else
		{
			popOutCard = findCard(target);
			outCardNum = *popOutCard;
			deleteCard(popOutCard);
			return outCardNum;
		}
	}

	vector<int>::iterator findCard(int target)
	{
		auto start = cardSet.begin();
		auto end = cardSet.end() - 1;
		int size = cardSet.size();

		while (1)
		{
			auto middle = start + (size / 2);
			if (size == 1)
			{
				return start;
			}
			size = size - (size / 2);

			if (*middle == target)
			{
				return middle + 1;
			}
			else if (*middle < target)
			{
				start = middle;
				continue;
			}
			else
			{
				end = middle;
				continue;
			}
		}
	}

};

int N, M, K;
cardDeck myDeck;

int main()
{
	int cardNum = 0;

	//입출력 속도 관리용
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> K;

	//reserve 함수를 사용하여, 미리 vector의 공간을 확보해둔다
	myDeck.setSize(M);

	for (int i = 0; i < M; i++)
	{
		cin >> cardNum;
		myDeck.insertCard(cardNum + 1);
	}
	myDeck.sortCards();

	for (int i = 0; i < K; i++)
	{
		cin >> cardNum;
		cout << myDeck.popCard(cardNum) << "\n";
	}
}