기록을

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