2021년 1분기

백준 2098 - 외판원 순회 (DP)

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;

constexpr int MAX_CITY = 16;
constexpr int INF = 987654321;

int N;
int cities[MAX_CITY][MAX_CITY];
int dp[1 << MAX_CITY][MAX_CITY]; //방문여부(bit), 마지막 방문 도시 문제의 답은 dp[bit_fullVisit][0]이 될 것
int bit_fullVisit; //모든 도시 방문했을 때

struct VisitInfo
{
	VisitInfo(int bit_visit, int lastCity, int curCity) : bit_visit{ bit_visit }, lastCity{ lastCity }, curCity{ curCity }
	{
		
	}

	int bit_visit;
	int lastCity;
	int curCity;
};

queue<VisitInfo> visitQ;


//시작지점은 의미 없으므로 0부터 시작한다고 친다.
void visit(int bit_visit, int lastCity, int curCity)
{
	int curBridge = cities[lastCity][curCity];

	//길이 없으면 계산 종료
	if (curBridge == 0)
		return;

	int bit_curVisit = bit_visit | (1 << curCity);

	int newCost = dp[bit_visit][lastCity] + curBridge;
	int& curCost = dp[bit_curVisit][curCity];
	
	//이미 방문했으면 최소비용 갱신
	if (curCost != 0)
	{
		curCost = min(curCost, newCost);
		return;
	}
	else
		curCost = newCost;

	//다 방문했으면 최종 값 계산 후 계산 종료
	if (bit_curVisit == bit_fullVisit)
	{
		visit(bit_fullVisit, curCity, 0);
		return;
	}

	//안 간 곳 방문
	for (int i = 0; i < N; ++i)
	{
		bool hasVisited = ((1 << i) & bit_curVisit) > 0;
		if(false == hasVisited)
			visitQ.emplace(bit_curVisit,curCity, i);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	memset(dp, 0, sizeof(dp)); //0으로 전부 초기화
	memset(cities, 0, sizeof(cities)); //0으로 전부 초기화

	//입력 읽음
	cin >> N;
	bit_fullVisit =( 1 << N) - 1;

	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			cin >> cities[i][j];
	
	//dp 계산
	for (int i = 1; i < N; ++i)
		visitQ.emplace(0, 0, i);

	while (!visitQ.empty())
	{
		VisitInfo info = visitQ.front();
		visitQ.pop();

		visit(info.bit_visit, info.lastCity, info.curCity);
	}

	cout << dp[bit_fullVisit][0];

	return 0;
}

 

백준 2243 - 사탕상자 (세그먼트 트리)

#include <iostream>
#include <vector>

using namespace std;

constexpr int FLAVOR_NUM = (int)1e6;
constexpr int SEGTREE_NUM = 1024 * 1024; //세그먼트 트리용 리프 노드 갯수

int segtree[SEGTREE_NUM * 2 - 1 ] = { 0 }; //세그먼트 트리.. [SEGTREE_NUM -1] 부터가 1번 맛임. 

int N;

int totalCandy()
{
	return segtree[0];
}

//input의 flavor값을 세그먼트 트리의 리프 인덱스로 반환
int flavorToSegIdx(int flavor)
{
	return flavor - 1 + SEGTREE_NUM - 1;
}

// p1 : 바꿀 리프노드 인덱스, p2 : 변동량
void segtree_update(int leafIdx, int changevVal)
{
	int segIdx = leafIdx;
	while (segIdx > 0)
	{
		segtree[segIdx] += changevVal;
		segIdx = (segIdx - 1) / 2;
	}
}

//p1 : 무슨 맛(입력 그대로), p2 : 변동량
void changeCandy(int flavor, int changeVal)
{
	int segIdx = flavorToSegIdx(flavor);
	segtree_update(segIdx, changeVal);
}

int segtree_search(int rank, int idx)
{
	int leftIdx = idx * 2 + 1;
	int rightIdx = idx * 2 + 2;

	//리프도달, 리턴
	if (idx >= SEGTREE_NUM - 1) 
	{
		int answer = idx - (SEGTREE_NUM)+2;
		return answer;
	}
	
	int leftVal = segtree[leftIdx];

	if (rank <= leftVal)
		return segtree_search(rank, leftIdx);
	else
		return segtree_search(rank - leftVal, rightIdx);
}

int getFlavorAt(int rank)
{
	return segtree_search(rank, 0);
}


void popCandy(int flavor)
{
	cout << flavor << "\n";
	changeCandy(flavor, -1);
}

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

	cin >> N;
	int A, B, C;

	for (int loop = 0; loop < N; ++loop)
	{
		cin >> A >> B;
		//꺼내기
		if (A == 1)
		{
			int flavor = getFlavorAt(B);
			popCandy(flavor);
		}
		//넣기(빼기)
		else
		{
			cin >> C;
			changeCandy(B, C);
		}
	}
}

 

리트코드 1143 - Longest Common Subsequence (DP)

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

class Solution {
public:
	int longestCommonSubsequence(string text1, string text2) {
		vector<vector<int>> dp;

		dp.resize(text1.length() + 1);
		for (int i = 0; i < dp.size(); ++i)
			dp[i].resize(text2.length() + 1, 0);

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

		return dp[text1.length()][text2.length()];
	}
};

 

프로그래머스 - 광고 삽입

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



int parseTimeToSec(string time)
{
	int hour = stoi(time.substr(0, 2)) * 3600;
	int  minute = stoi(time.substr(3,2)) * 60;
	int sec = stoi(time.substr(6, 2));
	return hour + minute + sec;
}

string convertSecToTime(int pSec)
{
	string hour = to_string(pSec / 3600);
	pSec %= 3600;
	string min = to_string(pSec / 60);
	pSec %= 60;
	string sec = to_string(pSec);

	string ret;
	if (hour.length() == 1)
		ret.append("0");
	ret.append(hour);
	ret.append(":");
	if (min.size() == 1)
		ret.append("0");
	ret.append(min);
	ret.append(":");
	if (sec.size() == 1)
		ret.append("0");
	ret.append(sec);

	return ret;
}

//진입시간, 나가는시간 반환
pair<int, int> splitAndParseLog(string log)
{
	int idx = log.find('-');
	string startTime = log.substr(0, idx);
	string endTime = log.substr(idx + 1);
	int startTimeSec = parseTimeToSec(startTime);
	int endTimeSec = parseTimeToSec(endTime);

	return pair<int, int>(startTimeSec, endTimeSec);
}


string solution(string play_time, string adv_time, vector<string> logs) {

	int playTimeSec = parseTimeToSec(play_time);
	int advTimeSec = parseTimeToSec(adv_time);

	vector<pair<int, bool>> timeLines; // first : 시간, second : 나가는 시간인지?
	timeLines.reserve(logs.size());

	for (int i = 0; i < logs.size(); ++i)
	{
		auto inOutTimePair = splitAndParseLog(logs[i]);

		timeLines.emplace_back(inOutTimePair.first, false);
		timeLines.emplace_back(inOutTimePair.second , true);
	}

	sort(timeLines.begin(), timeLines.end());

	int curViewer = 0;
	long long curViewTime = 0;
	int answerTime = 0;
	long long answerViewTime = 0;

	vector<int> viewers;
	viewers.resize(playTimeSec, 0);

	auto iter = timeLines.begin();

	for (int t = 0; t < playTimeSec; ++t)
	{
		//지난 시간의 시청자수 뺌
		if (t >= advTimeSec)
			curViewTime -= viewers[t - advTimeSec];

		while (iter != timeLines.end() && iter->first == t)
		{
			if (iter->first == t)
			{
				//시청자 나감
				if (iter->second)
					curViewer--;
				else
					curViewer++;
				iter++;
			}
		}

		viewers[t] = curViewer; //시청자 기록
		curViewTime += curViewer; //새로운 시청자 누적 시청시간 추가

		if (curViewTime > answerViewTime)
		{
			answerTime = t - advTimeSec + 1;
			answerViewTime = curViewTime;
		}
	}

	if (answerTime < 0)
		answerTime = 0;

	return convertSecToTime(answerTime);
}

 

프로그래머스 - 3 x n 타일링

#include <string>
#include <vector>

using namespace std;

long long prevSum; //이전 숫자까지의 답 누적 합
long long prevPrevSum; //이전 이전 숫자까지의 답의 누적 합
constexpr long long DIV = 1000000007;

int solution(int n) {
    long long answer = 0;
    prevPrevSum = 0;
    prevSum = 3;
    for(int i=2;i<=n/2;++i)
    {
        answer = 3 * prevSum -  prevPrevSum + 2 + DIV;   
        answer %= DIV;
        prevPrevSum = prevSum;
        prevSum = ( prevSum + answer ) % DIV;
    }
    return (int)(answer);
}

 

프로그래머스 - 베스트앨범

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>

using namespace std;

bool cmpPlayMap(pair<int, int>& a, pair<int, int>& b)
{
	if (a.first == b.first)
		return a.second > b.second;

	return a.first < b.first;
}

vector<int> solution(vector<string> genres, vector<int> plays) {

	vector<int> answer;

	unordered_map<string, int * > genreMap; //장르, 장르 총 플레이타임
	unordered_map<string, vector<pair<int, int>>> playMap; //장르, (플레이타임, 고유번호)
	
	for (int i = 0; i < genres.size(); ++i)
	{
		string key = genres[i];
		int play = plays[i];

		auto genreMapItem = genreMap.find(key);
		auto playMapItem = playMap.find(key);

		// 키가 있음
		if (genreMapItem != genreMap.end())
		{
			*(genreMapItem->second) += play;

			playMapItem->second.emplace_back(std::make_pair(play, i));
		}
		else
		{
			genreMap.insert({ key, new int(play) });

			vector<pair<int, int>> idxPlayPairs;
			idxPlayPairs.emplace_back(std::make_pair(play, i));
			playMap.insert({ key, idxPlayPairs });
		}
	}

	vector<pair<int, string>> sortedGenreMap;
	sortedGenreMap.reserve(genreMap.size());
	
	for (auto iter = genreMap.begin(); iter != genreMap.end(); iter++)
	{
		sortedGenreMap.emplace_back(std::make_pair(*(iter->second), iter->first));
	}
	sort(sortedGenreMap.begin(), sortedGenreMap.end());

	for (int i = sortedGenreMap.size() - 1; i >= 0; --i)
	{
		string key = sortedGenreMap[i].second;
		auto playMapItem = playMap.find(key);
		auto playList = playMapItem->second;

		sort(playList.begin(), playList.end(), cmpPlayMap);

		int idx = playList.size() - 1;
		answer.push_back(playList[idx--].second);
		if(idx>=0)
			answer.push_back(playList[idx].second);
	}


	return answer;
}

 

프로그래머스 - 게임 맵 최단거리

#include<vector>
#include <queue>

using namespace std;

int dirs[4][2] = { {1,0}, {-1, 0}, {0,1},{0,-1} };

struct Node
{
	int x, y;
	Node(int x, int y) : x{ x }, y{ y }	{}
};


int solution(vector<vector<int> > maps)
{
	int answer = -1;
	int m = maps.size();
	int n = maps[0].size();

	queue<Node> nodeQueue;
	nodeQueue.emplace(0, 0);

	while (false == nodeQueue.empty())
	{
		Node curNode = nodeQueue.front();
		nodeQueue.pop();
		for (int i = 0; i < 4; ++i)
		{
			int newY = curNode.y + dirs[i][0];
			int newX = curNode.x + dirs[i][1];
			int newDist = maps[curNode.y][curNode.x] + 1;

			if (newY >= 0 && newX >= 0 && newY < m && newX < n)
			{
				if (maps[newY][newX] == 1)
				{
					nodeQueue.emplace(newX, newY);
					maps[newY][newX] = newDist;

					if (newY == m - 1 && newX == n - 1)
						return newDist;
				}
			}
		}
	}
	return answer;
}

 

 

 

백준 2585 - 경비행기

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

//https://www.acmicpc.net/problem/2585
class problem
{
private:
	int n, k;
	vector<pair<int, int>> stations;
	const static int MaxFuel = 14143;
	const static int goalXY = 10000;

	//주어진 연료통 용량으로 목표까지 연결할 수 있음?
	bool decision(int fuel)
	{
		int maxSqrDist = fuel * fuel * 100;

		queue<pair<int, int>> q;	//Queue of (station index, numPassedStation)
		q.emplace(0, 0);

		vector<bool> checked;
		checked.resize(n + 1, false); //+1인 이유는 시작점을 더했기 때문
		checked[0] = true;

		while (false == q.empty())
		{
			int curStationIdx = q.front().first;
			int numPassedStation = q.front().second;

			int curX = stations[curStationIdx].first;
			int curY = stations[curStationIdx].second;

			q.pop();

			//못찾음
			if (numPassedStation > k)
				break;

			//목표지점 도달 가능
			if (getSqrDist(curX, curY, goalXY, goalXY) <= maxSqrDist)
				return true;

			for (int i = 0; i < n + 1; ++i)
			{
				if (false == checked[i])
				{
					int newX = stations[i].first;
					int newY = stations[i].second;
					int newDist = getSqrDist(curX, curY, newX, newY);

					if ( newDist <= maxSqrDist)
					{
						q.emplace(i, numPassedStation + 1);
						checked[i] = true;
					}
				}
			}
		}

		return false;
	}

	int getSqrDist(int x1, int y1, int x2, int y2)
	{
		return (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2);
	}

public :
	void read()
	{
		cin >> n >> k;
		stations.reserve(n+1);
		stations.emplace_back(0, 0); //시작점
		for (int i = 0; i < n; ++i)
		{
			int x, y;
			cin >> x >> y;
			stations.emplace_back(x, y);
		}
	}

	int solve()
	{
		int left = 0, right = MaxFuel;

		while (true)
		{
			int mid = (left + right) / 2;

			//통과 => 줄이자
			if (true == decision(mid))
			{
				right = mid;
			}
			//실패 => 늘리자
			else
			{
				left = mid + 1;
			}

			if (left >= right)
				return left;
		}

		return 0;
	}
};

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

	problem p;
	p.read();
	cout << p.solve();
}

 

 

백준 1786 - 찾기 (문자열 - KMP)

#include <iostream>
#include <vector>
#include <string>
using namespace std;
// https://bowbowbow.tistory.com/6
vector<int> getPi(const string& str) 
{
	vector<int> pi;
	int len = str.length();
	pi.resize(len, 0);
	for (int i = 1; i < len; ++i)
	{
		for (int j = pi[i-1];;)
		{
			if (str[i] == str[j])
			{
				pi[i] = j + 1;
				break;
			}
			else
			{
				if (j == 0)
					break;
				else
					j = pi[j - 1];
			}
		}
	}
	return pi;
}

vector<int> kmp(const string& T, const string& P)
{
	auto pi = getPi(P);
	vector<int> ret;

	int lenT = T.length();
	int lenP = P.length();

	int curIdx = 0;
	int i = 0;
	while (curIdx <= lenT - lenP)
	{
		//한 글자씩 맞는지 검사
		for (; i < lenP; ++i)
		{
			if (T[curIdx + i] != P[i])
				break;
		}

		//i==lenP일때 전체가 매칭된 경우
		if (i == lenP)
		{
			ret.push_back(curIdx);
			--i;
		}

		//적당히 다음 위치를 세팅해줌.
		int curPi = 0;
		if (i > 0)
			curPi = pi[i - 1];

		if (i - curPi == 0)
			curIdx++;
		else
			curIdx += i - curPi;

		i = curPi;
	}

	return ret;
}

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

	string T, P;
	getline(cin, T);
	getline(cin, P);
	auto ans = kmp(T, P);
	cout << ans.size() << endl;
	for (int i = 0; i < ans.size(); ++i)
	{
		cout << ans[i] + 1;
		if (i != ans.size() - 1)
			cout << " ";
	}
	return 0;
}

 

 

프로그래머스 - 섬 연결하기

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

struct DisjointSet
{
    vector<int> parent, rank;
    DisjointSet(int n) : parent(n), rank(n,1)   { for(int i=0;i<n;++i) parent[i]=i; }
    
    int find(int u) const
    {
        if(u==parent[u]) return u;
        return find(parent[u]);
    }
    
    bool isSameSet(int u, int v)
    {
        return find(u)==find(v);
    }
    
    void merge(int u, int v)
    {
        u = find(u); v=find(v);
        if(u==v) return;
        if(rank[u]>rank[v]) swap(u,v);
        parent[u]=v;
        if(rank[u]==rank[v]) ++rank[v];
    }
};

int solution(int n, vector<vector<int>> costs) {
    
    int answer = 0;
    int lineAdded = 0;
        
    auto comp = [](vector<int> a, vector<int>b)->bool{return a[2]>b[2];}; // cost가 낮은 순으로 정렬
    priority_queue<vector<int>, vector<vector<int>>, decltype(comp)> minHeap{comp};    
    for(auto cost : costs)
    {
        minHeap.push(cost);
    }    
    DisjointSet set(n);  
    

        
    while(lineAdded<n-1)
    {
        vector<int> edge = minHeap.top();
        minHeap.pop();
        if(set.isSameSet(edge[0],edge[1]))
        {
            continue;
        }
        else
        {
            answer+=edge[2];
            set.merge(edge[0],edge[1]);
            lineAdded++;
        }
    }
    return answer;
}

 

 

백준 2206 - 벽 부수고 이동하기

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

int DIRS[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };

struct Node
{
	int x,y,dist;
	bool hasBrk;
	
	//ctor
	//Node(int x, int y, int dist) : x{ x }, y{ y }, dist{ dist }, hasBrk{ true }
	//{	}

	Node(int x, int y, int dist, bool hasBrk) : x{ x }, y{ y }, dist{ dist }, hasBrk{ hasBrk }
	{	}
};

bool visit[2][1000][1000] = { false };
bool map[1000][1000] = { false };

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

	int N, M;

	//READ
	cin >> N >> M;

	for (int i = 0; i < N; ++i)
	{
		string temp;
		cin >> temp;
		for (int j = 0; j <M; ++j)
			map[i][j] = (temp[j] != '0');
	}

	//SOLVE
	int ans = -1;
	queue<Node> q;
	q.emplace(0, 0, 1, true);
	visit[0][0][0] = true;

	while (!q.empty())
	{
		Node curNode = q.front();
		q.pop();

		//find answer
		if (curNode.x == M - 1 &&
			curNode.y == N - 1)
		{
			ans = curNode.dist;
			break;
		}

		for (int i = 0; i < 4; ++i)
		{
			int newY = curNode.y + DIRS[i][0];
			int newX = curNode.x + DIRS[i][1];
			int newDist = curNode.dist + 1;

			if (newY >= N || newX >= M || newY < 0 || newX < 0)
				continue;

			if (curNode.hasBrk)
			{
				if (visit[0][newY][newX] == true)
					continue;

				if (map[newY][newX] == 0)
				{
					q.emplace(newX, newY, newDist, true);
					visit[0][newY][newX] = true;
				}
				else
				{
					q.emplace(newX, newY, newDist, false);
					visit[1][newY][newX] = true;
				}
			}
			else
			{
				if (visit[1][newY][newX] == true)
					continue;

				if (map[newY][newX] == 0)
				{
					q.emplace(newX, newY, newDist, false);
					visit[1][newY][newX] = true;
				}
			}
		}
	}

	cout << ans;
	return 0;
}