[211020] 그룹 Virtual 코딩테스트 연습6 후기

그룹 연습으로 진행된 Virtual 코딩테스트 연습6 후기를 포스팅하려 한다.

문제셋을 풀면서 어떤 생각을 거쳐 해결했는지 기록해두면 이후에 풀이과정을 떠올리는 필연성을 매끄럽게 떠올릴 수 있을 것 같기 때문이다.

 

https://www.acmicpc.net/group/practice/9928/51

참여자가 나 혼자뿐이다...

참고로 알고리즘 분류는 보지 않았고, 티어는 성공했을 경우 표시로 진행하였다.

---

A - 인터넷 설치 을 처음 접했을 때, A번이니까 쉬울 것이라 예상했는데 생각보다 쉽지 않았다.

 

1번은 이미 인터넷에 연결돼있었고, N번만 인터넷에 연결시키면 되니까 N에서부터 거꾸로 생각해보았다. 처음 떠올렸던 것은 그리디나 dp이다. 그러나, 아무리 생각해도 관통하는 최적의 방법이 보이지 않아 그리디로 풀릴 것이란 생각은 빠르게 접었고, dp나 bfs를 생각해보았다. bfs도 나름 빠른 최단경로를 구하는 알고리즘이기 때문이다.

 

bfs를 생각하니까 최단경로라는 점에서 dijkstra를 떠올렸고, 역추적을 해서 k개의 비싼 간선을 제외하면 되지 않을까 생각했다. 그런데, 반드시 최단경로가 아니어도 k+1번째 비싼 간선이 가중치가 가장 작은 경우를 따로 구해보이기가 쉽지 않았다. 아, 이분탐색을 돌려서 이 때 가능할지 불가능할지 모드를 생각해볼까? 일단 아이디어가 떠오르지 않아 B - 기지국 로 넘어갔다.

 

B - 기지국 는 처음엔 기하학 + 스위핑 느낌이 강하게 들어서 좀 두려웠다. 기하학도 약한데, 스위핑까지 붙여져있으니 후덜덜 떨수밖에... 일단은 좀 관찰을 해봤는데, 기지국을 어디에 설치하여 얼마만큼 포괄하냐에 따라 앞으로의 상태가 달라지기 때문에 dp로 해결해볼 수 있을 듯했다. 만약 dp로 해결이 안되면 이차원 스위핑이기 때문에 빠르게 패스하려 했으나, 다행히 1차원 dp에, N 범위가 애매하지만 좀 작아서 for문으로 cur번째 이후의 모든 건물을 포함할지 포함하지 않을지를 결정하는 O(N^2) dp로 B번을 AC를 받았다.

 

다음으로 빠르게 C - 소가 길을 건너간 이유 6 로 넘어갔다. 다리와 소의 위치가 주어지는데, 구현 느낌이 좀 강하게 들었다. 패스할까 말까 고민하다가, 일단 아이디어는 생각해보기로 하였다.

다리를 어떻게 표시할까 고민하다가, 어차피 N 크기가 굉장히 작아서 아래 그림처럼 배열의 크기를 가로, 세로 둘 다 2씩 늘리고, 격자 사이사이에 다리를 나타내는 칸을 추가해주기로 하였다.

빨간색: 다리 /  검은색: 소가 위치할 수 있는 공간

따라서 다리를 입력받을 때 아래 코드처럼 처리하였다.

y1 *= 2; x1 *= 2; y2 *= 2; x2 *= 2;
y1--; x1--; y2--; x2--;
a[(y1 + y2) / 2][(x1 + x2) / 2] = -1;
visit[(y1 + y2) / 2][(x1 + x2) / 2] = true;

 

격자 사이사이에 있기 때문에 2배한 후 그 중간값을 -1로 채워주기.

다리를 건널 수 없도록 방문 여부를 미리 true로 채워준다.

그리고 열심히 bfs를 돌려주었다. 그렇게 C번 AC.

나중에 알고보니 그냥 삼차원배열을 잡은 후, 동서남북 중 못건너는 다리를 설정해주면 됐었다. 괜히 어렵게 풀었다.

 

다음으로 D - 퍼즐 자르기으로 넘어갔는데, 히스토그램이 주어질 때, 내부에서 가장 큰 직사각형의 넓이를 구해주면 되는 문제였다.

엄청나게 웰노운인 문제가 꽁으로 나와버렸다.

이 문제랑 완전히 일치한다.

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

6549번: 히스토그램에서 가장 큰 직사각형

stack을 이용한 O(N) 풀이로 가볍게 D번 AC를 받았다.

사실 정말 어려운 문제 중 하나인데, 웰노운이 돼버린 문제...

 

E - 두 동전으로 갈까 A - 인터넷 설치으로 갈까 고민하다가, 다시 한 번  A - 인터넷 설치을 보기로 했다.

K개의 비싼 간선을 어떻게 하면 제외시킬 수 있을까, 그리고 그 중에서 어떻게 하면 비싼 간선 중 가장 싼 간선을 뽑을 수 있을까... 고민하였다. 다익스트라 + 역추적으로 어떻게 비빌 수 있지 않을까 굉장히 고민이 됐다.

 

K개의 비싼 간선에 특수한 표시를 해주거나, priority_queue의 cmp 설정을 바꿔볼까 고민하다가,

K개의 비싼 간선은 비용을 들게 하고, 그 외의 간선은 비용을 들지 않게 해서 다익스트라로 특정 값 이하로 N번에 도달가능한지 dijkstra + binary_search로 하는 방법이 문득 떠올라 잊어버리기 전에 구현했다.

다행히 예제가 잘 나왔고, 내가 임의로 만들어본 TC 또한 잘 나와서 제출해서 A번 AC를 받았다!

 

AC를 받으니 티어가 떴는데 G1이었다.

그럼 그렇지, 이게 쉬울리가없지 싶었다.

A번이라길래 쉬울줄알고 쫄았는데, 다행히 이번에 연습을 만들 때 티어를 랜덤배치로 했었나보다.

 

다행히 다른 분들도 풀이를 떠올리기 어려워했으며, 이 풀이대로 푸는 것이 맞았다.

사실 이 문제는 못풀줄 알았는데 다행히 사고과정이 올바르게 거쳐간 듯하다.

E까지 풀까 고민하다가, 그냥 패스하고 운동하러 나갔다.

---

A번 풀이 방법을 떠올리기 정말 힘들었는데,

이렇게 사고과정 및 의식의 흐름을 써놓아서 정리하면 나중에 도움이 되지 않을까 싶어 기록한다.

 

이후에 문제 각각에 대한 포스팅도 해보든지 해야겠다.