기록을

문제 링크

https://www.acmicpc.net/problem/1926

섬의 개수를 파악한다고 자주 기술했었는데, 간단하게 floodfill을 수행해주면 된다.

그림의 수를 파악하고, 그림의 넓이를 담아둘 때는 방문 처리 배열을 사용한다.

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

int map[500][500], dist[500][500];
int row, col;

queue<pair<int, int> > q;
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0, };

int cnt = 0;
void bfs(pair<int, int> start) {
	cnt++; //섬개수 확인
	q.push(start);
	dist[start.first][start.second]++; 
	int di = 2; //위에서 시작점 방문하면 거리 1이니까, 다음으로 들어갈 거리는 2

	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];

			if (nr < 0 || nc < 0 || nr >= row || nc >= col || map[nr][nc] == 0 || dist[nr][nc] > 0)continue;

			q.push({ nr, nc });
			dist[nr][nc] = di;
			di++;
			
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> row >> col;
	for(int i = 0 ; i < row ; i++)
		for (int j = 0; j < col; j++) {
			cin >> map[i][j];
		}

	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++) {
			if (map[i][j] == 1 && dist[i][j] == 0)
				bfs({ i, j });
		}
	//방문처리 배열에 카운트를 해뒀기때문에 그 안에서 최댓값을 구하면 된다.
	int Max = -1;
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			if (dist[i][j] > Max)
				Max = dist[i][j];
		}
	}
	cout << cnt << '\n' << Max << '\n';
	return 0;
}

문제링크

https://www.acmicpc.net/problem/1012

섬의 개수를 확인하는 방식으로 전형적인 bfs를 사용해서 풀이가 가능하다.

bfs 함수가 실행되는 횟수를 확인하면 된다.

방문하지 않았으면서 배추가 있는 곳이 bfs의 시작점이 된다.

범위 밖을 나가는 요소와 이미 방문한 지점, 방문할 필요가 없는 지점을 제외하면 되는 간단한 bfs이다.

#include<iostream>
#include<queue>
using namespace std;
int map[51][51], vis[51][51];
int m, n, k;

int cnt = 0;
queue<pair<int, int> > q;
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };
void bfs(pair<int, int> start) { //전형적인 bfs
	cnt++; //섬 개수 추가
	q.push(start);
	vis[start.first][start.second] = 1;
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];
			//범위 나가거나 배추가 없는 곳이거나 이미 방문한 곳이면 continue
			if (nr < 0 || nc < 0 || nr >= n || nc >= m || vis[nr][nc] == 1 || map[nr][nc] == 0)continue;
			
			q.push({ nr, nc });
			vis[nr][nc] = 1;

		}
	}

}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tc;
	cin >> tc;
	while (tc--) {

		cin >> m >> n >> k;

		int n1, n2;
		while (k--) {
			cin >> n1 >> n2;
			map[n2][n1] = 1;
		}

		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (map[i][j] == 1 && vis[i][j] == 0)
					bfs({ i, j }); //1인 지점 넘겨줘야함

		cout << cnt << '\n';

		//이후로 초기화
		for (int i = 0; i < n; i++) 
			for (int j = 0; j < m; j++) {
				map[i][j] = 0;
				vis[i][j] = 0;
			}
		cnt = 0;
	}

	return 0;
}

https://www.acmicpc.net/problem/2631

단순하게 dp로 접근하기 보다는, 한가지 아이디어가 필요하다.

바로 LIS (최장 부분 증가 수열)이다.

어린이들의 이동 횟수가 최소가 되기 위해서는, 움직이지 않을, 즉 기준이 되는 어린이들을 잡을 필요가 있다.

어린이들의 정렬은 오름차순으로 이루어진다.

따라서 무작위로 섞여있는 어린이들의 번호 가운데에서, 오름차순으로 정렬된 최장 부분 수열을 찾아야한다.

그 부분 수열은 그대로 두고, 나머지 어린이들을 움직여주면 되겠다.

따라서 LSI의 길이를 전체 어린이의 수에서 빼주면 된다.

LIS를 구하는 알고리즘을 숙지하도록 하자.

#include<iostream>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	int arr[200];
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	int d[200];
	int Max = 0;
	for (int i = 0; i < n; i++) { //LIS(최장 부분 증가 수열)구하기
		d[i] = 1;
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j] && d[i] < d[j] + 1) {
				d[i]++;
			}
		}
		if (Max < d[i]) Max = d[i];
		
	}

	cout << n - Max << '\n';
	return 0;
}

https://www.acmicpc.net/problem/2178

bfs에서 방문 처리를 거리 배열을 활용하여 수행하는 문제이다.

c++에서 c의 std io함수들과의 동기화를 끊어주는 ios::sync_with_stdio(false);

이것을 적어둔 상태로 scanf를 사용해서 맞왜틀을 반복했다.

visual studio에서는 알아서 잡아주는데, 백준 채점 환경에선 그렇지 않다.

#pragma warning(disable : 4996)
#include<iostream>
#include<queue>
using namespace std;
int n, m, map[101][101], dis[101][101];

queue<pair<int, int> > q;
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };
void bfs(pair<int, int> start) {
	q.push(start);
	dis[start.first][start.second]++;
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];

			if (nr < 0 || nc < 0 || nr >= n || nc >= m || map[nr][nc] == 0 || dis[nr][nc] > 0) continue;

			q.push({ nr, nc });
			dis[nr][nc] = dis[cur.first][cur.second] + 1;
		}
	}
}
int main(void) {
	//ios::sync_with_stdio(false); 이거 적어두고 아래에서 scanf 쓰면 gcc에선 틀린다
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%1d", &map[i][j]);


	bfs({ 0, 0 });
	cout << dis[n - 1][m - 1] << '\n';
	return 0;
}

문제 링크는 다음과 같다.

https://www.acmicpc.net/problem/1158

처음에는 직관적으로 링크드리스트를 사용해야겠다고 생각했다.

이후에 iterator가 리스트의 마지막을 가리키는 경우를 제대로 핸들하지 못해서

벡터를 이용한 풀이를 최종 풀이로 결정했었다.

큐를 활용하는 문제라는 것을 확인한 이후에 큐를 이용한 풀이를 작성했다.

큐를 휘어서 생각하면 원형의 형태로 볼 수 있다.

이에 착안해서 front 부분에 있는, 건너 뛰어야 할 요소들을 push 해준 이후에 pop 해주는 방식으로

원하는만큼 '점프'할 수 있다.

#include<iostream>
#include<queue>
using namespace std;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	queue<int> q;
	int n, k;
	
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		q.push(i);

	cout << '<';
	while (n--) {

		for (int i = 0; i < k - 1; i++) { //pop할 때, 한번의 건너뛰는 효과를 볼 수 있다. 그래서 k-1번만 건너뛴다.
			q.push(q.front()); //front에 있는 것을 다시 push 해주고
			q.pop(); //삭제해주면 위로 올리는 효과
		}
		cout << q.front();
		q.pop();
		if (!q.empty())
			cout << ", ";
	}
	cout << '>';

	return 0;
}

https://www.acmicpc.net/problem/11053

가장 긴 감소하는 부분 수열의 반대 문제되겠다.

당시에는 몰랐는데 꽤 여러곳에 응용되는 전형적인 알고리즘인 것 같다.

문제에서 주어진 예시를 활용해서 아이디어를 좀 더 깔끔하게 정리해보자.

10 20 10 30 20 50

위와 같은 예시가 주어졌다.

먼저 10까지만 봤을 때는, 부분 수열의 길이는 1이다.

이제 20을 확인해보자. 초기에 20을 확인하면, 수열의 성분은 20하나이기때문에 길이는 1이다.

즉 d[]의 초기값은 모두 1이라고 할 수 있다.

이제 10과 비교해서 확인해보자. 10은 20보다 작기때문에 기본적으로 증가 수열의 조건을 만족한다.

또 한가지 확인해야 할 것은, 10에 20을 연결했을때, 기존에 20과 연결되어있는 다른 수열보다 길이가 길겠느냐 하는 것을 생각해 보는 것이다.

20까지만 확인한 경우, 이전에 나온 성분이 10밖에 없기 때문에 다소 모호하게 보일 수 있겠다.

일단 d[1]의 값은 2이다. (10과 20이 증가 수열을 이루기 때문에)

다음으로 10을 살펴보자. 초기에 10 자체로 수열을 이룬다고 볼 수 있기 때문에 앞서 언급한 것처럼 초기값은 1이다.

이제 가장 앞의 10과 비교해보자. 10은 10과 이어져서 증가 수열을 이룰 수 없다. 마찬가지로 20과도 이어질 수 없다. 따라서 d[2] = 1이 되겠다.

다음으로 30을 살펴보자. 30에 대해서 10을 먼저 비교해보면, 30은 10과 이어서 증가 수열이 될 수 있다. 따라서 10과 함께 증가 수열을 이룬다고 할 때, d[3] = 2가 되겠다.

20과 비교해보자. 20은 10과 연결되어서 증가 수열을 이룰 수 있다고 앞에서 확인했었다. 그렇다면 30을 연결하면? 

길이가 3이된다. 30은 현재 10과 연결해서 길이 2의 부분 증가 수열을 이루고 있었는데, 20과 연결된다면 길이가 증가할 수 있다. 따라서 20과 연결되어서 길이가 3이된다. d[2] = 3이 된다.

이런 흐름의 알고리즘을 활용하면 된다.

#include<iostream>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	int arr[1000];
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	int d[1000];
	int Max = 0;
	for (int i = 0; i < n; i++) {
		d[i] = 1;
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j] && d[i] < d[j] + 1)
				d[i]++;
		}
		if (Max < d[i]) Max = d[i];
	}
	cout << Max << '\n';

	return 0;
}

https://programmers.co.kr/learn/courses/30/lessons/17681

비트연산 문제인데, 이진수로 변환한 뒤에 문자열 비교를 통해 풀었다. 0이 들어오는 경우 이진수로 변환할 때 조심해주면 된다.

https://www.acmicpc.net/problem/17140

열이든 행이든 연산 하나를 제대로 구현하면, 나머지 하나는 똑같다.

보통 개수를 셀 때, cnt[m[i]]++ 이런 방식으로 세는데, 이 경우에는 1회 이상 등장한 숫자의 개수도 함께 필요하고,

이 수들의 빈도와 수 자체를 가지고 정렬을 해야하기 때문에 다른 방식을 사용했다.

먼저 map을 사용해서 숫자별 개수를 기록했다. 이후에 벡터에 pair 형태로 옮기면서 정렬했다.

주의할 것이, 중간에 R연산을 할 때는 열의 길이가 갱신되고, C연산을 할 때는 행의 길이가 갱신되는데, 따라서 연산을 시작할 당시의 값으로 반복문의 범위를 잡아줘야, 중간에 반복문의 범위가 바뀌는 것을 방지할 수 있다.

https://www.acmicpc.net/problem/15684

초기 사다리의 정보를 입력받은 이후에, 사다리를 추가로 놓을 수 있는 곳들을 모두 찾아서 3개 이하로 사다리를 놓아보고, 문제에서 정해준 조건대로 i번에서 출발하면 i번 라인으로 도착할 수 있는지를 확인해주면 된다.

사다리를 모두 놓아보는 방법에는 여러가지가 있을 것 같은데, 본인은 먼저 사다리 하나를 놓을 수 있는 모든 경우를 찾아서 벡터에 담았다.

그리고 문제에서 3개 이하로만 확인하면 된다고 했기 때문에, 0개부터 3개까지 사다리를 놓아보고, i열에서 출발해서 i열로 도착할 수 있는지를 확인했다.

사다리를 놓을 수 있는 최솟값을 찾는 것이기 때문에, 중간에 어떤 경우라도 조건을 만족하면, 탐색을 멈추고 답을 출력한다.

사다리를 놓아볼 때는, 가령 (1,3) (1,4)에 놓아지는 사다리를 추가할 때는, 당연하게도 (1,4)에서 출발하는 사다리를 놓을 수 없기 때문에 이에 맞는 처리를 해주면 된다.

https://www.acmicpc.net/problem/16637

중요한 부분은

1. 수식의 길이를 n이라고 했을 때, 넣을 수 있는 괄호의 최대 개수 찾기

2. 수식을 계산하기

두 가지로 나눌 수 있다.

괄호의 최대 개수는 몇 개의 예시를 통해서 규칙을 찾을 수 있다.

계산을 할 때에는, 계산에 필요한 연산자와 피연산자를 구분해서 벡터에 저장해둔 이후에, 계산을 하게 되면, 연산자의 개수는 항상 피연산자의 개수보다 하나 적다는 것을 이용해서 깔끔하게 계산할 수 있다.