언제나 처음처럼

[문제 링크]

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

[문제 링크]

분할정복은 문제를 부분 문제로 뚝 자르고 잘라져서 나온 조각에 대해 똑같이 처음 했던 것처럼 뚝 자르기를 반복하여 정답을 찾아내는 방식인거같다.

다만 완전탐색과 조금 다른점이 있다면 문제마다 구현해야할 기저사례, 점화식을 깊게 생각해봐야하고, 이를 구현하는 것이 까다롭다는 것이다. 대강 원리는 이해했으니 문제를 많이 풀어보면서 문제 유형에 익숙해지고 구현력을 키워야겠다.

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

[문제 링크]

분할정복 알고리즘 부분은 교재에 나와있는 소스코드와 동일하다.

다만 책에서 설명이 안되어있는데, 매개변수로 반복자를 참조하기 위해서는 비 const 반복자를 전달해야한다.

tree.begin() 이 반환하는 반복자는 const 반복자이므로 따로 비 const 반복자를 선언하고 tree.begin()으로 초기화해줘야 한다는 점만 주의하면 될 것 같다.

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

[문제 링크]

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

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

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

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

[문제 링크]

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

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

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

[문제 링크]

갈색타일(B)의 개수는 빨간타일(R)이 몇 줄로 이루어져 있느냐에 따라 달라진다.

따라서 빨간타일(R)이 1줄 일 때 부터 (R/2)줄 까지 갈색타일 개수를 구하고 입력받은 B와 일치할 때 결과를 출력해주면 원하는 정답을 얻을 수 있다.

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