기록을

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