기록을

문제 링크는 다음과 같다.

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

위와 같은 예시를 보면, 쉽게 이차원 배열을 사용해야겠다는 생각을 떠올릴 수 있다.

특정 학년의 특정 성별을 가지는 학생의 수를 그대로 배열에 저장해준다.

k보다 인원이 작으면 방은 1개만 있으면 되고, 그 이상일 경우 k로 나눈 몫 + 1개만큼 방이 필요하다.

#include<iostream>
using namespace std;

int arr[2][7];

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

	int n, k;
	cin >> n >> k;

	int s, y;
	while (n--) { //n명의 정보를 2차원 배열에 저장
		cin >> s >> y;
		arr[s][y]++;
	}

	int room = 0;

	for (int i = 0; i < 2; i++) {
		for (int j = 1; j <= 6; j++) {
			if (!arr[i][j]) //특정 학년과 성별의 학생수가 0이면 continue
				continue;
			
			if (arr[i][j] < k) // k보다 작으므로 방은 하나만 있으면 됨
				room++;
			else { //k보다 크거나 같을 때
				if (arr[i][j] % k == 0) {
					//k로 나눠 떨어질 때
					room = room + arr[i][j] / k;
				}
				else {
					room = room + arr[i][j] / k + 1;
				}
			}
		}
	}

	cout << room << '\n';

	return 0;
}

문제링크

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

순서를 섞었을 때 문자열이 같아질 수 있느냐를 물어보는 문제였다.

단순히 문자열에서, 각 알파벳의 개수를 파악해주고 비교해주면 된다.

#include<iostream>
#include<string>
#include<math.h>
using namespace std;

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

	string org, cpr;
	int orga[26] = { 0, }, cpra[26] = { 0, };

	cin >> org >> cpr;

	for (int i = 0; i < org.length(); i++) {
		orga[org[i] - 'a']++;
	}
	for (int i = 0; i < cpr.length(); i++) {
		cpra[cpr[i] - 'a']++;
	}

	int cnt = 0;
	
	for (int i = 0; i < 26; i++) {
		cnt = cnt + abs(orga[i] - cpra[i]);
	}
	cout << cnt << '\n';

	return 0;
}
/*
strfry와 같은 원리. 단어에 쓰인 알파벳별 개수를 파악해서 비교.
입력 문자열의 길이가 다른 경우도 생각해줘야함
*/

문제링크

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

설명은 코드의 주석으로 대체하겠다.

#include<iostream>
#include<string>
using namespace std;
int A, B, C, arr[10];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> A >> B >> C;
	long long res = A * B*C;	
	string str = to_string(res);
	for (int i = 0; i < str.length(); i++) {
		arr[str[i] - '0']++;
	}
	for (int i = 0; i < 10; i++) {
		cout << arr[i] << '\n';
	}
	return 0;
}
/*
각 자리수의 숫자를 확인하기 위해 계산 결과를 long long에서 string 으로 변환
string으로 변환된 값의 각 자리수인 char에서 int로 변환을 -'0'을 활용
*/

문제 링크

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이 들어오는 경우 이진수로 변환할 때 조심해주면 된다.