기록을

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

백준 16637번 괄호 추가하기라는 문제인데, 이 문제를 풀면서 했던 뻘짓을 기록해두려고 한다.

3+8*2 이런 문자열이 있다고 할 때, 결과값을 내도록 구현하려면 어떻게 해야할까?

그냥 str[0] ~ str끝까지 한 문자 한 문자 확인하려고 생각하는 순간 굉장히 피곤해진다.

324 + 232 이런 경우처럼, 한 자리수가 아닌 숫자가 존재할 수 있기 때문이다. 처음에 이렇게 접근했다가, 결과적으로 아래와 같은 뻘짓을 하게 되었다.

위와 같은 뻘짓을 하지 않으려면, 연산자와 피연산자를 분리해서 벡터(배열)에 저장하고 있으면 된다. 연산하기가 훨씬 수월하다.

이렇게 간단하게 계산할 수 있다.

정상적인 수식이라면, 연산자의 개수가 피연산자의 개수보다 하나 적을 것이므로, 깔끔하게 위와 같은 반복문을 만들어낼 수 있다.

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

궁수 세 명을 최적의 위치에 배치해서, 가장 많은 적을 죽이도록 하는 문제이다.

따라서 열의 길이를 이용해서, 궁수가 위치할 수 있는 세 곳을 먼저 조합으로 뽑는다.

각각의 궁수에 대해 bfs를 돌린다. 앞에서부터 멀리있는 곳까지 확인할 것이다.

이때 중요한 것이 몇가지 있다.

궁수들은 같은 거리라면 왼쪽에 있는 적부터 공격한다. 따라서 bfs를 수행할 때, 탐색의 순서를 좌, 상, 우 이렇게 해줘야 한다.

또한 궁수들은 동시에 같은 적을 공격할 수 있다고 했기 때문에, 하나의 궁수를 가지고 탐색을 하다가 적을 발견했을 때에, 바로 그 적을 없애면 안 된다.

그걸 없애버리면 동시에 같은 적을 공격할 수 있다는 조건에 위배되기 때문이다.

set에 추가만 해주고, 이번 턴에 죽일 적을 찾았으므로, 바로 현재 궁수의 bfs를 종료해주면 된다.

세 궁수의 탐색이 사정거리만큼 모두 이루어지고 나면 set을 활용해서 지도에서 적을 지우고, set을 비워준다.

시기적절하게 초기화를 해주고, 적들을 지도에서 제거하고, 적들을 이동시키는 잔처리가 중요한 문제였다.

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

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

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

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

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

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

정확성 테스트는, 그냥 조건대로 시뮬레이션을 돌리면 통과할 수 있지만, 효율성 테스트는 통과할 수 없다.

k의 범위가 매우 큰데, 나이브하게 풀면 k번 탐색해야하기 때문이다.

k번 탐색할 게 아니라, 최대로 음식의 개수만큼만 탐색하도록 구현할 수 있다.

음식을 먹는 데 소요되는 시간을 오름차순으로 정렬하고, 

(현 시점에서 가장 적은 시간이 소요되는 음식의 시간 * 남아있는 음식의 수)만큼의 시간을 한 번에 감소시킬 수 있다.

당연히 k도 갱신되어야 하고, 위에 계산한 시간이 k보다 작아야 가능하다.

저 시간이 k보다 크다면, 음식별 소요 시간으로 정렬해 두었던 것을, 다시 본래의 인덱스로 돌려준다. 이것 때문에 초반에 pair에 음식별 소요시간과 그 음식의 번호를 함께 저장하는 것이다.

이제는 나머지 연산을 활용해서, 먹어야할 음식을 찾아주면 된다.

문제 풀이 소요 시간을 획기적으로 감소시켜야 할 때 생각해 볼만한 것들

1. 정렬

2. modular 연산

3. 이분탐색

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

k번 순회하도록 해서 정확도밖에 맞추지 못한 코드이다.

순회 방법을 줄일 아이디어가 필요하다.

처음에 든 생각은, 배열에서 0이 아닌것의 개수와, 배열의 최솟값을 곱하면 이만큼을 한 번에 먹는 것으로 처리할 수 있다는 것.

다른 생각은 정렬해서 k보다 작을동안 묶어서 빼준 이후에, 한 번에 먹을 수 있는 게 k보다 커지면 다시 순회하는 방법이 있을 것 같다.

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

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

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

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

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

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

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

본인은 후자로 구현했다.

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