기록을

https://www.welcomekakao.com/learn/courses/30/lessons/42892

순회는 간단한 부분이기 때문에, 사실 관건은 좌표를 이용해서 트리를 어떻게 만들 것이냐이다.

기본적으로 위에서부터, root를 시작으로 아래로 채워갈 것이기 때문에, 입력받는 좌표를 y값 내림차순으로 정렬한다. y좌표가 동일한 경우 x좌표 오름차순으로 정렬해서, 왼쪽 자식부터 확인할 수 있도록 한다.

정렬을 할 때, 아무런 처리를 해주지 않고 정렬하게 되면, 본인이 원래 몇 번째 인덱스였는지 잃어버리기 때문에, 이후에 순회를 할 수가 없다.

따라서 입력을 받을 당시에, 본인의 인덱스를(노드 번호) 갖고 있도록 처리를 해주어야 한다.

본인은 구조체를 이용했고, 사실 벡터에 그냥 인덱스를 추가해줘도 상관이 없을 것 같다.

트리를 만들 때는, 링크드리스트의 형태를 취해서 만드는 것도 가능하고, 배열의 인덱스를 루트로 해서 하는 방법도 가능하다.

본인은 후자로 구현했다.

먼저 최대 공약수 gcd는 재귀로도 구현할 수 있고, 아래와 같이 반목문으로 구현할 수도 있다.

어느쪽이 큰 수인지 지정해줘야 한다.

이후에 큰수를 작은수로 나누고, 나눈 수를 다음에 나눠질 수로 정한다. 나머지는 다음에 나눌 수가 된다.

0으로 나눌 수는 없기 때문에 루프를 빠져 나간다고 외워도 좋고, 나머지가 0이 되었다는 것은 약수를 찾았다는 뜻이니까 루프를 빠져 나간다고 기억해도 좋겠다.

( ll은 long long 타입을 의미한다)

int gcd(ll a, ll b) {
    if (a < b) swap(a, b); //a를 큰수로
    while (b != 0) {
        ll r = a % b;
        a = b;
        b = r;
    }
    return a;
}

다음으로, gcd를 활용해서 최소 공배수 lcm을 구하는 과정도 간단하게 구현할 수 있다.

ll lcm(ll a, ll b) {
    return (a * b) / gcd(a, b);
}

최소 공배수의 정의대로, 두 수의 곱을 최대 공약수로 나눠주면 된다.

이를 활용해서, 여러개의 숫자의 최소 공배수를 구하는 과정을 보자.

ll finY = Y[0];
    for (int i = 1; i < Y.size(); i++)
        finY = lcm(finY, Y[i]);

finY에 벡터 Y의 원소들의 최소 공배수가 들어가게 된다. 먼저 벡터 Y의 0번째 값으로 finY를 초기화 한다.

그리고 다음 원소와 lcm을 구해서 저장하고, 또 저장한 lcm과 다음 원소의 lcm을 구하는 과정을 반복해주면 된다.

https://www.welcomekakao.com/learn/courses/30/lessons/42889

stage k의 실패율은, 현재 stage k에 머물러 있는 사람/스테이지 k이상 시도한 사람

이라는 것을 이용했다. 두 배열을 만든 이후에, 부동 소수점 오차를 방지하기 위해서 나누는 연산은 하지 않고, 통분시 분자값을 비교해서 대소를 비교했다.

https://www.welcomekakao.com/learn/courses/30/lessons/42888

문제를 보면, ID와 닉네임을 대응해서 최신값으로 유지해야 한다. 기본적으로 사람이 입장하면 map에 추가를 해주면 되겠고, 닉네임을 변경하는 것이면, map에서 key값인 id에 대응되는 value인 닉네임을 업데이트 해주면 된다.

주의할 것은, 나가는 기능을 수행했을 경우, map에서 그 id의 데이터를 삭제하면 안 된다는 것이다.

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;
}

*기하

그라함 스캔 과정

1. 극값 찾기(y값 작은거, 같다면 x값 작은거)

2. 극값기준 각도순 정렬

3. n번 루프돈다. 스택 크기 2이상 유지하면서 b[i] 0이하이면 pop. 밖에서 push

4. 필요에 맞게 마지막에 처음점 추가(다각형의 선분으로 무언가 할 때)

볼록껍질 최단거리 찾는법

1. 그라함 스캔을 돌려서 볼록 껍질을 형성한다. (마지막에 첫점 추가)

2. n번 루프돈다. j=1부터, j가 1이랑 다를때만 방향벡터 ccw가 양수이면 j++해준다.

j==s.size()-1이 되면 0으로 낮춰준다.

3. 양수가 아니게 되면 i와 j의 거리를 비교해서 최대인지 확인한다

-----------------------------------------------------------------------

*그래프

플로이드 와샬

1. n <= 500일때만 사용하자.

2. 바깥부터 k i j 순으로 루프 돌리고, k거쳐가는거랑 그냥가는거 길이 비교해서

작은 값으로 갱신해준다.

3. 모든 정점사이의 비용 계산에 용이 -> 모든 정점의 연결상태 파악 가능

벨만포드 -> 시작점 존재

0. 초기에 비용 무한대로 초기화. 시작점 비용은 0으로

1. 음수가중치가 존재할 때 사용. 사이클이 없어야한다.

2. 가장 바깥에서 n번 돌린다.(n번째에 갱신이 발생하면 음수사이클 존재)

3. 그 안쪽에서 정점 개수만큼 루프를 돈다.

4. 정점마다 연결된 간선 크기만큼 루프 돌면서, 목적지가 갖고 있는 거리가,

이곳에서 그 정점으로 가는 거리보다 크다면 갱신한다.

5. 이걸 확인할 때, 현재 위치까지의 비용이 무한이 아니어야 한다.

다익스트라

1. 가중치가 양수인 그래프의 최단거리를 젤 수 있다.

2. 방문처리와 우선순위큐가 필요하다(민힙), pii 배열의 인덱스가 시작점, first 비용, sec 목적지 

3. 비용을 무한대로 초기화해주고, 시작점은 0으로 만든다.

4. 시작점을 pq에 넣고, pq가 빌 때까지 실행한다.

5. pq에서 확인하는 지점을 방문처리 한다.(top)

6. 그 지점과 연결된 간선들을 확인할 것인데, 그 연결된 지점이 방문한 지점이면 스킵한다.

7. 거리비교해서 갱신조건 만족할 때만 push한다.

LCA (최소공통조상)

1. DFS로 각 노드의 깊이 계산, 2^0번째 부모 계산

2. 2^k번째 부모는 2^k-1번째 부모의 2^k-1번째 부모임을 이용해서 배열 채우기

3. 비교하고자 하는 노드의 높이를 같게 맞추기(탑다운으로) (뭐가 깊고 뭐가 얕은 노드인지 구분해서)

4. 이때 최대 높이는 (int)floor(log2(n))

5. 높이차이가 2^k보다 커질때마다 깊은점을 k번째 부모로 갱신

6. 높이를 맞춘 이후에, 두 노드가 같다면 그게 답

7. 이번에도 kmax부터 내려오면서 deep과 swall의 부모가 다르다면 둘다 k번째 부모로 갱신

8. 루프를 빠져나오면 0번째 부모가 답

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

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

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

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

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

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

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

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

priority queue가 터져서 최근에 메모리 초과를 몇번 받았다.