Kcode

2022.07.04 ㅠㅠ

www.acmicpc.net/problem/1713

구현, 시뮬레이션 문제

1. 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.
2. 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.
3. 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.
4. 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.
5. 사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.

N이 주어지면 N칸만큼 사진이 게시되어야 하는데 문제를 이해하기에 어려운 내용은 아니다.

구현에 있어서 살짝 까다로운 부분이 있다면 3번이다.

우선 나는 풀이를 구현하는데 있어 vector<pair<int,int>> 를 선언해주고

number와 몇 번 불렸는지 cnt로 사용했다.

우선 벡터에 push_back으로 추가되니 추천 받은 횟수가 가장 적은 학생이 두명 이상일 경우 앞에 있는 것을 지워주면

되는데 이것은 erase 메소드로 쉽게 처리할 수 있다.

또한 C++에는 <algorithm> 헤더 파일에 min_element() 가 존재하는데 람다 함수를 이용해서

pair<> 로 접근하는 것들에 대해서 쉽게 처리해줄 수 있다.

min_element(a.begin(), a.end(), [](const auto& lhs, const auto& rhs) {
			return lhs.second < rhs.second;
			})

이런 식으로 사용해주면 second가 가장 작은 원소를 찾아 그 iterator를 반환해준다.

전체 소스 코드

www.acmicpc.net/problem/13913

이번 문제는 경로를 추적해서 출력하는 문제였다.

조금만 생각해보면 금방 알 수 있는데, 현재 위치를 지나가는 배열 a를 만들어서

a[next] = cur 를 담고있다고 가정해보면 a[k] 에는 k에 도착하기 전 가장 마지막 위치가 담겨있을 것이고,

a[마지막 위치] 에는 그 위치에 오기 위한 위치가 점진적으로 들어있을 것이다.

그렇다면 구현은 간단하다.

기존 bfs를 통해 최단시간을 구할 때 a[next] = cur 만 추가해주고 이후에 재귀적인 호출을 통해

역추적해주면 된다.

www.acmicpc.net/problem/13549

숨바꼭질 2와 다르게 3은 cur * 2 지점으로 텔레포트할 때에 시간이 소요되지 않는다.

평범하게 큐로 bfs 할 경우 기존 cur -1, cur + 1을 하면서 K에 도착하게 되면

이후에 cur * 2 를 통해 도착하는 시간보다 더 크지만 이미 방문처리가 되어있으므로 값을

갱신시켜줄 수 없다.

어떻게 접근해야될까?

이 문제는 우선순위 큐를 최소 힙으로 선언한 후 time을 기준으로 정렬하게 해 주면 된다.

그러면 cur에 대해서 가장 짧은 time을 가진 노드를 먼저 방문해주게 된다.

기존 bfs코드와 다를 것 없이 priority_queue로만 바꿔주면 된다.

또 다른 방법이 있다. 바로 deque자료구조를 이용하는 것인데, deque는 priority_queue를 이용하는 것보다

더 빠르게 구할 수 있다!!

우선순위 큐의 특성상 삽입하는 데에 \(O(log N)\)의 시간 복잡도가 걸린다. 그러나 가중치가 0-1로만

이루어진 상황이라면 현재 위치 cur에서 다음에 이동할 부분은 0 또는 1만 차이 난다는 것을 알 수 있다.

그러니 deque의 앞쪽 부분에는 텔레포트(cur * 2) 하는 부분을 삽입해주고 cur - 1, cur + 1 부분은 1초가 걸리니

뒤에 삽입해주면 된다.

deque의 특성상 앞 뒤로 삽입하는 경우는 \(O(1)\)이 걸리므로 더 빠르게 구할 수 있다.

www.acmicpc.net/problem/12851

며칠 고민해봤는데 풀이 방법이 안 떠올라서 다른 블로그를 참고해서 풀었다.

두 개 정도의 풀이 방법이 있었는데 하나는 K로 가는 방법의 수를 배열 하나를 더 만들어서 접근하는 방법이고

다른 하나는 큐에서 팝 할 때 방문 체크를 해주는 방식이다.

첫 번째 방법은 시간이 항상 1씩 늘어난다는 것을 이용해서 d[next] == d[cur] + 1 이라면 cnt를 증가시키는 방법이다.

두 번째 방법은 현재 위치에서 팝 할때 방문처리를 해준다면 목적지 K는 항상 들어갈 수 있으므로

큐에 넣어주고 현 위치가 K이고 방문한 시간이 같다면 cnt를 증가시켜주는 방법이다.

두 번째 코드

글이 복잡하게 쓰여있지만 이해하기 그리 어렵지 않다.

result에 실패율이 높은 순으로 정렬해서 return 해주면 되는데 어떻게 실패율을 구할 것인가가 중요하다

우선 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수 인데

현재 스테이지 개수 / 현재보다 크거나 같은 스테이지의 개수로 치환 가능하다.

따라서 전처리를 통해 stages의 원소들이 몇 번 등장했는지와 가장 큰 값을 구해놓는다.

가장 큰 값은 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0으로 정의한다. 조건 때문에 필요한데

for 문을 돌리면서 i 값이 가장 큰 값보다 크다면 실패율을 0으로 push 해줘야 하기 때문이다.

pair벡터를 <int, double>로 선언해주는데 idx와 fail rate를 담는다.

첫 번째 예제를 보면

각각의 번호와 몇 번 등장했는지를 구해보면 이렇게 나오는데

스테이지의 총인원수가 8명이니

<1,1> <2,3> <3,2> <4,1> <5,0> <6,1> 

에서 1번의 실패율은 1의 second / n - sum(누적)이다.

정렬은 comp를 통해 쉽게 구현 가능하다.

www.acmicpc.net/problem/15686

생각보다 쉽게 풀었다. 치킨집이 총 13개까지 주어지는 조건을 봤고,

치킨집과 집을 매칭 시키는 것이 combination을 떠올리게 한다.

따라서 그래프 탐색이 아니라 조합, 경우의 수로 접근해봤다.

일단 보자마자 집을 원소로 가지는 a벡터, 치킨집을 원소로 가지는 b벡터를 인자로

받아 각 원소를 \(O(N^2)\)으로 순회하며 가장 작은 치킨 거리를 찾아 리턴해주는 함수를 만들었다.

이건 쉽게 구현 가능하고 이제 치킨집에서 총 M개의 원소를 뽑아서 각각 a, b를 매칭 시켜주면 된다.

처음에는 next_permutation을 이용한 순열로 접근했지만 모든 경우의 수를 따지면 시간초과가 난다.

그래서 지우고 조합으로 다시 접근해줬는데 n과m 문제를 풀어봤다면 쉽게 구현 가능하다.

www.acmicpc.net/problem/3190

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

deque를 사용하면 앞뒤로 삽입과 삭제를 용이하게 할 수 있다.

일단 방향을 정해주는데 북, 동, 서, 남을 차례로 0, 1, 2, 3으로 설정해준다.

이러면 dx, dy해주는 부분은

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

가 되고, 방향을 조절해주는 함수는 다음과 같이 쉽게 작성할 수 있다.

void dir(char C) {
	if (C == 'L') !d ? d = 3 : d--;
	else d == 3 ? d = 0 : d++;
}

처음에는 X와 C가 주어지면 X만큼 이동 후 C방향으로 회전시키는 것인 줄 알았는데

X가 현재 초를 가르키는 거라 고생 좀 했다.

우선 뱀이 움직이는 부분은 쉽게 구현 가능하다.

아무것도 아닌 부분은 '.', 뱀이 위치하고 있는 부분은 'o', 사과가 존재하는 부분은 '*'로 놓고

위처럼 구현하고 dir함수를 통해 방향을 바꿔준다.

이제 남은 구현부분은 이미 충돌했거나, 범위 밖을 벗어나는 경우 더 이상 X와 C를 받지 않고

빠져나와야 하는데 나는 뱀이 이동하는 bfs 함수를 boolean으로 작성하여 해결했다.

만약 중간에 반복문을 빠져나온게 아니라 query를 전부 수행했다면

이제 벽에 박을 때까지 진행시켜주면 된다.

최종 코드

www.acmicpc.net/problem/1446

문제는 그리디 하게 접근해야 한다는 것이다. 그냥 지름길이 주어졌다고 해서 지금 길만 탄다면

다른 컴포넌트에 있는 길로 가는 것이 더 빠를 수 있다.

어떻게 접근해야 할까?

핵심은 다익스트라를 돌리면서 현재 위치 + 1 에 지름길이 없다면 우선순위 큐에 

cost + 1 로 넣어주는 것이다.

이렇게 되면 자연히 d 이하의 모든 노드를 탐색하면서 지름길이 있다면 지름길을 타고, 아니라면

다음 컴포넌트가 큐에 들어가게 된다.

k 가 고속도로의 길이 d라고 하면 현재 위치 cur + 1 이 k보다 작아야 하고(고속도로를 역주행할 수는 없기 때문에)

그다음 위치가 현 비용 + 1 보다 크다면(INF라면) 

다른 컴포넌트이기 때문에 그 위치를 큐에 넣어줘야 한다.

www.acmicpc.net/problem/1915 

정사각형을 만족하기 위해서 어떤 규칙이 필요할까?

행렬 i, j 를 기준으로 왼쪽, 위, 왼쪽 위가 모두 1인 것만이 정사각형이 된다.

이걸 확장시켜주면, 최종적인 점화식은 \(D[i][j] = min(d[i-1][j], d[i][j-1], d[i-1][j-1]) + 1\) 이 된다.

물론 조건문으로 현재 위치가 1이고 그 주변도 1임을 미리 따져줘야 한다.

a 배열에는 정사각형을 만족하는 크기가 들어가 있을테니 제곱의 형태로 출력해주면 된다.