언제나 처음처럼

[문제 링크]

c++ stl 컨테이너인 map을 사용하면 쉽게 풀 수 있는 문제라 생각한다.

map 컨테이너는 [ ] 로  key값을 이용해 간단하게 value값을 찾을 수 있으며, O(logN) 시간복잡도를 보장한다.

필자는 key값이 string인 map과 int인 map을 두개 만들어서 입력되는 문제가 string일 경우와 int일 경우 if문을 통해 각각 다른 map컨테이너를 검색하도록 구현하였다.

참고로 시간초과로 고생 하시는 분들께서는 ios_bass::sync_with_stdio(0); cin.tie(NULL); 을 추가하고 cout과 cin을 사용해보는 것을 추천합니다.

#include <iostream>
#include <cstdlib>
#include <map>
#include <string>
using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);

	map<string, int> poketStr;
	map<int, string> poketNum;
	int N, M, num=1;
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		string str;
		cin >> str;
		poketStr.insert(make_pair(str, num));
		poketNum.insert(make_pair(num++, str));
	}

	for (int i = 0; i < M; i++)
	{
		char question[21];
		cin >> question;
		if (question[0] < 'A')
		{
			int qNum = atoi(question);
			cout << poketNum[qNum] << '\n';
		}
		else
		{
			cout << poketStr[question] << '\n';
		}
	}
	return 0;
}

알고리즘 200일 프로젝트 - 43day

[문제 링크]

분할정복과 이분탐색이 섞인 문제인거같다. 이분탐색 풀이법이 생각나지 않아 다른사람들의 풀이법을 참고하였다. 3일 후에 다시한번 풀어봐야 겠다.

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

vector<int> dayMoney;
int N, M, sum;

bool Solution(int money)
{
	int temp = money, withdraw = 1;
	for (int i = 0; i < N; i++)
	{
		if (dayMoney[i] > money)
			return false;
		if (temp - dayMoney[i] < 0)
		{
			temp = money;
			withdraw++;
		}
		temp -= dayMoney[i];
	}
	return M >= withdraw;
}
int main(void)
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		int n;
		cin >> n;
		dayMoney.push_back(n);
		sum += n;
	}

	// binary_search //
	int start = 1, end = sum; // sum은 M이 1인 모든 금액을 더한 값
	int result;
	while (start <= end)
	{
		int mid = (start + end) / 2;
		if (Solution(mid))	// 인출횟수가 M보다 작거나 같음 -> 인출금을 줄여보자
		{
			result = mid;
			end = mid -1;
		}
		else
			start = mid + 1;
	}
	cout << result << endl;
	return 0;
}

알고리즘 200일 프로젝트 - 39day

[문제 링크]

https://onlytrying.tistory.com/46

쿼드트리 문제와 동일하다. 다른점은 보드 크기가 3^N X 3^N 인 것과 보드를 쪼갤 때 4조각이 아닌 9조각으로 쪼갠다는 것이다.

쿼드트리 문제와 마찬가지로 (startY, startX)좌표를 시작으로 3^N X 3^N 크기 만큼의 보드를 검사한다.

숫자가 모두 같다면 더이상 쪼개질 수 없으므로 보드의 숫자를 카운팅 해준다.

필자는 0으로 초기화한 크기가 3인 배열을 하나 만들고 Array[보드의 숫자 + 1]++ 으로 숫자를 카운팅하였다.

#include <iostream>
using namespace std;

int board[2188][2188];
int numberCnt[3]; // MINUS ONE = 0, ZERO = 1, ONE = 2

void Solution(int N, int startY, int startX)
{
	if (N == 1) // 없어도 무방한 기저사례지만 코드 직관성과 효율성을 위해 추가
	{
		++numberCnt[board[startY][startX] + 1];
		return;
	}

	bool check = true;
	for (int i = startY; i < startY + N; i++)
	{
		for (int j = startX; j < startX + N; j++)
		{
			if (board[startY][startX] != board[i][j])
			{
				check = false;
				break;
			}
		}
		if (!check) break;
	}
	if (check)
	{
		++numberCnt[board[startY][startX] + 1];
		return;
	}

	int nextN = N / 3;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			Solution(nextN, startY + (nextN*i), startX + (nextN*j));
}
int main(void)
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> board[i][j];

	Solution(N, 0, 0);

	for (int i = 0; i < 3; i++)
		cout << numberCnt[i] << endl;
	
	return 0;
}

알고리즘 200일 프로젝트 - 38day

[문제 링크]

https://onlytrying.tistory.com/42

AOJ의 QUADTREE 문제와 유사한 형태의 문제라고 생각한다. 따라서 알고리즘도 비슷하게 구현하였다.

먼저 (startY, startX)좌표를 시작으로 N X N 크기만큼 보드값을 검사한다. 모든 값이 일치한다면 숫자 1 or 0 으로 압축할 수 있다. 값이 일치하지 않다면 N/2 크기의 보드 4개로 나누고 나눠진 보드에 대해 위와 같은 작업을 반복한다.

나눠진 보드들이 반환하는 문자열을 합치고 시작 위치에 '(', 끝 위치에 ')'을 붙여주면 원하는 결과를 출력할 수 있다.

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

vector<string> board;

string Solution(int N, int startY, int startX)
{
	bool check = true;
	for (int i = startY; i < startY+N; i++)
	{
		for (int j = startX; j < startX+N; j++)
		{
			if (board[i][j] != board[startY][startX])
			{
				check = false;
				break;
			}
		}
		if (!check) break;
	}
	if (check) return string(1,board[startY][startX]);

	int nextN = N / 2;
	string board1 = Solution(nextN, startY, startX);
	string board2 = Solution(nextN, startY, startX + nextN);
	string board3 = Solution(nextN, startY + nextN, startX);
	string board4 = Solution(nextN, startY + nextN, startX + nextN);

	return '(' + board1 + board2 + board3 + board4 + ')';
}
int main(void)
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		string str;
		cin >> str;
		board.push_back(str);
	}
	cout << Solution(N, 0, 0) << endl;
	
	return 0;
}

알고리즘 200일 프로젝트 - 38day

[문제 링크]

2^N X 2^N 크기의 보드가 주어졌을 때, 이를 4등분 하면 2^(N-1) X 2^(N-1) 보드 4개로 나뉘게 된다.

또한 입력받은 좌표는 반드시 4개의 보드 중 한개의 보드 내에 존재하게 된다. 입력받은 좌표를 포함하는 보드에 대해 계속 나누면서 나뉜 보드의 크기가 2^1 X 2^1 이 되었을 때, 선택된 2X2 크기의 보드에는 반드시 입력받은 좌표가 존재하게 된다.

좌표와 일치하는 블록이 전체 보드판에서 가지는 값(방문 순서)을 출력해주면 원하는 결과를 얻을 수 있다.

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

int Solution(int N, int col, int row, int start, int findCol, int findRow)
{
	if (N == 1)
	{
		if (col == findCol && row == findRow) return start;
		else if (col == findCol && row + 1 == findRow) return start + 1;
		else if (col + 1 == findCol && row == findRow) return start + 2;
		else return start + 3;
	} 

	int halfCol = pow(2, N) / 2 + col;
	int halfRow = pow(2, N) / 2 + row;

	if (findCol < halfCol && findRow < halfRow)
		return Solution(N - 1, col, row, start, findCol, findRow);

	else if (findCol < halfCol && findRow >= halfRow)
		return Solution(N - 1, col, halfRow, start + pow((pow(2,N)/2),2), findCol, findRow);

	else if (findCol >= halfCol && findRow < halfRow)
		return Solution(N - 1, halfCol, row, start + pow((pow(2, N)/2), 2) * 2, findCol, findRow);

	else
		return Solution(N - 1, halfCol, halfRow, start + pow((pow(2, N)/2) , 2) * 3, findCol, findRow);
}

int main(void)
{
	int N, r, c;
	cin >> N >> r >> c;
	cout << Solution(N, 0, 0, 0, r, c) << endl;
}

알고리즘 200일 프로젝트 - 37day

[문제 링크]

하노이탑은 1번 막대(from)에서 시작하는 경우 2번 막대(by)를 거쳐 3번 막대(to)에 쌓는다.

즉 1번 막대(from)에서 마지막 원판을 제외한 n-1개 원판을 3번 막대(to)를 거쳐 2번 막대(by)에 쌓은 다음, 남은 원판을 목적지인 3번 막대(to)에 쌓고, 원판이 쌓인 막대가 바뀌었으니 똑같이 2번 막대에서 1번 막대를 거쳐 3번 막대에 쌓는 작업을 반복하는 것이다.

이는 움직이기 전 하노이탑에서 시작 지점과 원판 갯수(n)만 바뀐 같은 문제가 반복되는 형태라는 것을 알 수 있고, 이는 분할 정복 알고리즘을 통해 해결할 수 있다.

하노이탑 이동 횟수는 원판수(n)에 따라 정해진 공식이 있지만, 본 코드에서는 cnt라는 변수로 횟수를 카운팅하고, 이동 경로를 queue에 담아 마지막에 출력해주는 형태로 구현하였다.

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

queue<pair<int, int>> moving;
int cnt;
void hanoi(int n, int from, int by, int to) // from에서 by를 거쳐 to로
{
	if (n == 1)
	{
		moving.push(make_pair(from, to));
		cnt++;
	}
	else
	{
		hanoi(n - 1, from, to, by);
		moving.push(make_pair(from, to));
		cnt++;
		hanoi(n - 1, by, from, to);
	}
}

int main(void)
{
	int n;
	cin >> n;
	hanoi(n, 1, 2, 3);
	cout << cnt << endl;
	while (!moving.empty())
	{
		cout << moving.front().first << ' ' << moving.front().second << '\n';
		moving.pop();
	}
	return 0;
}

알고리즘 200일 프로젝트 - 36day

[문제 링크]

string 컨테이너와 반복자를 사용하여 손쉽게 해결한 문제였다.

Adrian의 찍는 순서는 "ABC", Bruno의 찍는 순서는 "BABC", Goran의 찍는 순서는 "CCAABB" 임을 알 수 있기 때문에

찍는 순서를 string에 저장하고 반복자를 한칸씩 증가시키는 방법으로 입력된 문자열과 비교하였다.

알고리즘 200일 프로젝트 - 32day

[문제 링크]

입력받은 숫자들을 전부 vector에 담아 2중 for문을 돌려도 정답은 쉽게 찾을 수 있겠지만, 효율성을 늘리기 위해 하나의 for문을 사용하는 쪽으로 구현하였다.

자연수의 최대값이 100을 넘지 않기 때문에 계수정렬을 이용하였고, for_each 함수를 사용하여 벡터에 담긴 모든 원소를 탐색하였다.

알고리즘 200일 프로젝트 - 32day