기록을

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

배열 돌리기 목록을 꼭 "모두 사용해야 한다"고 했다. 또한 배열을 돌리는 순서에 따라서 결과가 달라지기 때문에, 순열을 사용해서 돌릴 순서를 정해준다.

모든 경우를 다 돌려봐야 하고, 주의할 사항은, 한 순열을 돌린 이후에, 반드시 배열을 원래 상태로 초기화 시켜줘야 한다는 것이다.

배열을 돌릴 때에는, 모든 값을 보존하면서 돌리는 것이 불가능 하다. 돌리는 순서, 방향에 따라서 반드시 모서리중 어느 한 값은 손실이 발생할 수 밖에 없는데, 그 값을 정해서 미리 담아두고, 마지막에 채워주면 된다.

본인은 가장 좌측 상단의 값을 기억해두고, 그 위치를 없어지는 값으로 정했다. 마지막에 그 값이 옮겨가야 할 곳에 넣어주면 된다.

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://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/10254

좌표 평면위의 점의 최장 거리를 이루는 두 점은 하나의 볼록 껍질 위에 존재한다는 것을 이용해서 푼다.

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

모든 노드의 연결 관계를 파악해야한다.

n 이 500이므로 플로이드 와샬을 사용할 수 있고, 모든 정점으로부터 다른 모든 정점까지의 비용을 파악할 수 있다.

비용은 1로 두고, 갈 수 있는지 없는지만 파악하면 된다.

주의할 사항은, degree를 계산할 때, 자신에서 자신으로 가는 것은 카운트하지 않아야 한다는 것이다.

자기 자신으로의 경로 비용 초기화를 어떻게 했는지에 따라 잘 처리해주면 되겠다.

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

투포인터를 활용해주면 된다.

길이를 언제 갱신하고, 무한루프를 어느 위치에서 종료할 것인지만 명확히 해준다면 무리없이 풀리는 문제이다.

현재까지 더한 구간합이, 넘겨야할 합보다 크다면 일단 그 시점의 길이가 최소 길이인지 비교해서 갱신해준다.

이후 왼쪽 인덱스 포인터를 증가시키고 길이를 감소시키고, 변화된 상태가 조건을 만족하는지 확인해주고 이런 흐름이다.

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

상관없는지 모르겠으나 원래는 kij순으로 루프 돌아야한다

문제 이름에서부터 플로이드 와샬 알고리즘을 사용해야 한다는 것을 암시하고 있는 문제이다.

주의할 것은, 이전까지 INF 값으로 limits.h 헤더에 있는 INT_MAX를 사용했는데, 이 값에 어떤 값이 더해지는 연산을 하게되면 오버플로우가 발생한다.

다익스트라, 벨만포드에서는 괜찮았지만 플로이드에서 이런 일이 생기니, 그냥 속편하게 내가 INF를 지정해서 써야겠다.

INF는 항상 (간선 가중치의 최댓값 ) * (정점 개수 - 1 ) 보다 크게 잡아줘야 한다.

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

벨만 포드 알고리즘을 사용하는 문제는 음수 가중치를 가지고 무언가를 하는 문제들인데, 거리 / 비용을 음수로 주기는 표현이 애매하기 때문에 이 문제에서처럼 시간을 가지고 문제를 만드는 것 같다. 웜홀, 시간 여행 등의 주제로 나오는 것 같다.

초기에 간선들의 정보를 받아주고, 다익스트라와 동일하게 모든 정점으로 가는 비용을 무한대로 초기화 한다.

그리고 n-1번에 거쳐서, 모든 정점들의 모든 간선들을 탐색해주고, 마지막 한 번은 음수 사이클 검사용으로 탐색해준다.

마지막 1번의 검색에서, 즉 가장 바깥 루프의 n번째 탐색시에, 경로 / 비용의 갱신이 발생한다면, 이 그래프는 음수 사이클을 포함하고 있다는 의미이다.

그렇지 않으면, 당연히 n개의 정점을 최소비용으로 이동하는 데에 n-1개의 간선이면 충분하기 때문이다.

n-1개 이상 간선을 사용한다는 것은? 어딘가에 음수 사이클이 있기 때문에 계속 그곳을 지나가게끔 갱신이 발생되고 있다는 의미이다.

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

다익스트라 알고리즘을 구현해주면 된다.

방문했던 노드를 다시 방문하지 않도록 해주어야 TLE를 피할 수 있을 것이다.

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

가중치가 있는 그래프의 최소 비용 / 최단 경로를 구하는 문제이다.

가중치들이 모두 양수이기 때문에 다익스트라를 이용한다.

먼저 시작점으로부터 i번 노드까지 가는 총 비용을 의미하는 dist[i]를 무한대로 초기화한다.

알고리즘이 시작되면, 시작점으로부터 시작점까지의 비용은 0인 것이 자명하기 때문에 dist[시작점] = 0으로 바꿔준다.

그리고 시작점으로부터의 거리가 가장 낮은 것부터 뽑을 것이기 때문에 min heap을 사용한다.

이 때, pair에 특정 노드번호와, 그 노드까지 가는 비용을 함께 관리할 것이다. 주의할 점은, pair의 대소 비교는 first부터 일어나기 때문에 반드시 비용을 first에 넣어줄 수 있도록 한다.

이후로는 현재노드까지 오는 비용 + 이동할 수 있는 노드로의 이동 비용 < 다음 노드까지 가는 총비용

위의 경우에 다음 노드까지 가는 총 비용을 갱신해준다.

갱신되는 경우에, heap에 갱신되는 지점을 넣어주도록 하자.