이것 저것 &

문제링크:https://www.acmicpc.net/problem/2668

dfs문제입니다.

N의 범위가 100밖에 안되기 때문에 모든 인자에 대하여 사이클 여부를 확인하는 식으로 진행해도 시간초과가 발생하지 않습니다.

1. 각 인덱스마다 해당 값을 사이클을 가지는지 확인합니다.

        1) 방문여부, start와 current의 위치가 같다면 해당값을 포함합니다.

        2) 방문하지 않았다면 방문을 표시하고, arr[current] 로 이동해서 확인합니다.

2. 사이클을 가진다면 해당값을 result배열에 포함합니다. (이때 인덱스가 작은값부터 포함하기 때문에 정렬할 필요가 없습니다.)

정답코드입니다.

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

int n = 0, result_index = 0;
int arr[101] = { 0 };
int visited[101] = { 0 };
int result[101] = { 0 };

void dfs(int current,int start) {
	if (visited[current]) {
		if (current == start)
			result[result_index++] = start;
	}
	else {
		visited[current] = 1;
		dfs(arr[current], start);
	}

}

int main() {
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	
	for (int i = 1; i <= n; i++) {
		memset(visited, 0, sizeof(visited));
		dfs(i, i);
	}

	cout << result_index << endl;
	for (int i = 0; i < result_index; i++)
		cout << result[i] << endl;
}

문제링크:https://www.acmicpc.net/problem/2583

전형적인 dfs 문제입니다. (bfs로도 풀이는 가능합니다.)

분리된 공간의 넓이를 출력하면 되는 문제입니다.

위와같이 되어있어서 사각형을 판단하는데 어려움을 가지실 수 있습니다.

하지만 저건 그냥 일반점으로 보아도 무방합니다.

사각형 하나를 그냥 점으로 보세요.

보이시나요?

0~m, 0~n까지입니다. 

해당위치들을 표시해주고 dfs를 통해서 몇번 탐색이 가능한지 확인하고 결과를 도출합니다.

정답코드입니다.

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

int m = 0, n = 0, k =0;
int arr[102][102] = { 0 };
int x, y, x2, y2;

int result[101] = { 0 };
int sum = 0, result_index = 0;
int x_dep[4] = { 1,-1,0,0 };
int y_dep[4] = { 0, 0,-1,1 };

void dfs(int yy, int xx) {
	
	arr[yy][xx] = -1;
	sum++;

	for (int i = 0; i < 4; i++)
	{
		int yyy = yy + y_dep[i];
		int xxx = xx + x_dep[i];

		if (yyy >= 0 && yyy < m && xxx >= 0 && xxx < n) {
			if (arr[yyy][xxx] == 0)
				dfs(yyy, xxx);
		}

	}
	
}
int main() {
	cin >> m >> n >> k;

	for (int i = 0; i < k; i++) {
		cin >> x >> y >> x2 >> y2;

		for (int j = y; j < y2; j++) {
			for (int u = x; u < x2; u++) {
				arr[j][u] = 1;
			}
		}
	}


	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == 0) {
				sum = 0;
				dfs(i, j);
				result[result_index++] = sum;
			}
		}
	}

	sort(result, result + result_index);

	cout << result_index << endl;
	for (int i = 0; i < result_index; i++)
		cout << result[i] << " ";
	cout << endl;
}

저는 dfs가 가장 노력하는만큼 실력이 늘어나는 알고리즘이라고 생각합니다. :0

꼭 직접 작성해보세요. 화이팅! 

https://manamoa30.net/bbs/board.php?bo_table=manga&wr_id=2878234

최종국면이네요. 이제 끝이 보입니다 :)

문제링크: https://www.acmicpc.net/problem/1251

모든 경우의 수를 비교해봐야하는 브루트 포스 문제입니다.

즉, 완전탐색을 하는 것입니다.

비교적 쉬운 난이도였지만, 틀리기 좋았던 부분은 단어를 쪼갤때

1. 삼등분을 해야하기 때문에 중복이 되면 안된다.

2. 세가지 덩어리가 순서대로 돌아와야한다.

오답코드가 있으시다면 해당 테스트케이스를 확인해보세요.

afbdba -> abdbfa

정답코드입니다.

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

string input,result;
string a, b;

int main() {
	cin >> input;

	result = "{"; 

	for (int i = 0; i < input.size()-2; i++) {
		for (int j = i+1; j < input.size()-1; j++) {
			
			string val;

			for (int u = i; u >= 0; u--)
				val += input[u];

			for (int u = j; u > i; u--)
				val += input[u];

			for (int u = input.size() - 1; u > j; u--)
				val += input[u];

			if (result > val) result = val;
			
		}
		
	}


	cout << result << endl;
}

문제링크: https://www.acmicpc.net/problem/1051

브루트포스 문제입니다. 모든 점에서 꼭짓점값들을 확인해서 가장크게 만들 수 있는 정사각형 넓이를 출력하는 문제였습니다. 정답률이 30퍼때라 좀 어려울 줄 알았는데 생각보다 너무 쉬워서 놀랐습니다.

각 점에서 오른쪽과 아래로 내려갈 수 있는 값들을 고려하면서 값을 도출합니다.

코드가 너무 쉬워서 설명은 생략하겠습니다. :)

아래는 정답코드입니다. 

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

int n, m, result = 1;
int arr[51][51] = { 0 };
string input;

int main() {

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
			cin >> input;
			for (int j = 0; j < input.size(); j++)
				arr[i][j] = input[j] - '0';
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int cnt = 0;
			for (int k = 1;; k++) {
				if ((j + k) >= m || (i + k) >= n) break;
				if (arr[i][j] == arr[i][j + k] && arr[i][j] == arr[i + k][j] && arr[i][j] == arr[i + k][j + k])
					if(cnt < k)
						cnt = k;
			}
			if ((cnt + 1) > result) result = cnt + 1;
		}

	}

	cout << result * result << endl;
}

문제링크:https://www.acmicpc.net/problem/2966

전형적인 브루트포스문제였습니다.

어렵지 않았을 것이라고 생각합니다.

너무 쉬운문제라서 설명은 생략하겠습니다.

#include <iostream>
using namespace std;

char a[3] = { 'A','B','C' };
char b[4] = { 'B','A','B','C' };
char c[6] = { 'C','C','A','A','B','B' };
char arr[101];
int cnt[3] = { 0 };

int n = 0, result = 0;

int main() {
	cin >> n;
	cin >> arr;

	for (int i = 0; i < n; i++) {
		if (a[i % 3] == arr[i]) cnt[0]++;
		if (b[i % 4] == arr[i]) cnt[1]++;
		if (c[i % 6] == arr[i]) cnt[2]++;
	}
	for (int i = 0; i < 3; i++)
		if (result < cnt[i]) result = cnt[i];
	cout << result << endl;
	if (cnt[0] == result) cout << "Adrian" << endl;
	if (cnt[1] == result) cout << "Bruno" << endl;
	if (cnt[2] == result) cout << "Goran" << endl;
}

문제링크:https://www.acmicpc.net/problem/2503

모든 경우를 고려해주며 결과값을 도출하는 브루트포스 문제였습니다.

숫자의 범위가 적기 때문에 어려운 점은 없는 문제였습니다.

1) 100~999까지의 수를 반복하며 확인 

2) 이때 0을 포함, 혹은 같은 자릿수를 가지는 수는 제외

3) 같은 자릿수를 가지면 strike값을 올리고 다른 자리에 해당 값이 있다면 ball값을 올려줍니다.

4) 조건을 만족하는 수가 있다면 결과값을 +1씩 올려줍니다.

2번조건을 간과해서 틀릴 수 있습니다. 문제조건을 한번더 확인하는 습관을 가져야겠습니다.

직접문제를 풀어보세요! :0 화이팅

#include <iostream>
#include <algorithm>
using namespace std;
int n = 0, result = 0;
int arr[100][3] = { 0 };
int arr2[9] = { 0 };
int main() {

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
	}

	for (int i = 100; i <= 999; i++) {
		if (i % 10 == 0) continue; //0 안들어가게
		if ((i / 10) % 10 == 0) continue;

		if (i / 100 == (i / 10) % 10) continue;
		if (i / 100 == i % 10) continue;
		if (i % 10 == (i / 10) % 10) continue;
		bool jud = true;

		for (int j = 0; j < n; j++) {
			for (int k = 1; k <= 9; k++) arr2[k] = 0;
			bool first = false, second = false, third = false;

			int strike = 0, ball = 0;
			int num = i;
			
			if (num / 100 == arr[j][0] / 100) strike++,first=true;
			arr2[arr[j][0] / 100]++;

			if ((num / 10) %10 == (arr[j][0] / 10)%10) strike++,second=true;
			arr2[(arr[j][0] / 10) % 10]++;

			if (num % 10 == arr[j][0] % 10) strike++,third=true;
			arr2[arr[j][0] % 10]++;
			
			if (!first&&arr2[num / 100]) ball++;
			if (!second&&arr2[(num / 10) % 10]) ball++;
			if (!third&&arr2[num % 10]) ball++;

			if (strike != arr[j][1] || ball != arr[j][2]) {
				jud = false;
				break;
			}

		}
		if (jud == true) {
			
			result++;
		}
	}
	cout << result << endl;
	return 0;
}

문제링크:https://www.acmicpc.net/problem/2589

최단거리 탐색을 할때는 bfs 알고리즘을 사용합니다.

보물위치의 최단거리를 출력하는 문제였습니다. 

어느지점을 기준으로 출발하느냐에 따라 결과가 달라지기에 조금 생각해야하는 문제였습니다.

근데 높이,너비가 50까지임으로 저는 모든점에서의 최장거리를 계산해서 문제의 답을 구했습니다.

한가지 예외처리를 못했던 테스트케이스입니다.

4 4

LLWW

WWWW

WWWW

WWWW

이경우 1이 나와야하지만 

간혹 2가 나오는 코드들이 있습니다.

조건문에 (a!= y + de_y[i] || b != x + de_x[i])를 추가해줌으로써 해결했습니다. (출발지점으로 되돌아 오면 안되기 때문에)

기존의 bfs문제들을 풀어보셨다면 쉬운문제였을겁니다.

정답코드입니다. 직접 손으로 작성해보세요 :) 화이팅

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int height, width;

string arr[51];
int visited[51][51];
int que[2501][2];
int started,ended;
int de_x[4] = { 1, 0, 0,-1 };
int de_y[4] = { 0, 1,-1, 0 };
int result = 0;

void bfs(int a, int b) {
	started = 0, ended = 0;
	que[ended][0] = a;
	que[ended][1] = b;
	ended++;

	while (started != ended) {
		int y = que[started][0];
		int x = que[started++][1];
		
		for (int i = 0; i < 4; i++) {
			if ((y + de_y[i])>=0 && (y + de_y[i])<height && (x + de_x[i])>=0 && (x + de_x[i])<width)
				if (arr[y + de_y[i]][x + de_x[i]] == 'L' && !visited[y + de_y[i]][x + de_x[i]] && (a!= y + de_y[i] || b != x + de_x[i]))
				{
					visited[y + de_y[i]][x + de_x[i]] = visited[y][x] + 1;
					que[ended][0] = y + de_y[i];
					que[ended++][1] = x + de_x[i];
					
				}

		}
		
	}

	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			if (arr[i][j] == 'W') continue;
			if (result < visited[i][j] ) result = visited[i][j];
		}
	}


}
int main() {

	cin >> height >> width;
	for (int i = 0; i < height;i++)
		cin >> arr[i];

	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			if (arr[i][j] == 'W') continue;
			memset(visited, 0, sizeof(visited));
			
			bfs(i,j);


		}
	}

	cout << result << endl;
}