[Codeground] 5월 20일 삼성전자 A형 시험

갑자기 메일이 한통 왔다.

삼성 대학생 프로그래밍 경진대회 (SCPC)에 참가한 이력을 보고 연락을 줬다고 했고 SW Test를 받을지 메일이 왔다.

이전에 나는 SCPC 2차까지 응시한 경험이 있었는데 이 메일을 보고 뭔가 했다.

3월에 삼성 소프트웨어 멤버십 1차를 합격해서 2차를 치나 했는데 2차인지도 잘 모르겠고 그냥 A형을 치러 오라고 하였다.

시험이 총 A-B-C가 있는데 A부터 치라고 하였고 우선 5/20일에 시험을 치기로 하였다.

그렇게 5/20일에 삼성에서 알려준 위치에 가서 시험을 응하게 되었다.

문제는 다음과 같았다.(저작권상 문제 전문을 공개하지 못하고 어떤 유형이었는지만 기억나는대로 말하겠습니다.)

N*N 그래프가 주어진다. (1<=N<=20 (대략적인 N 범위이다.))

예를들어 4*4의 그래프를 보자. 이 그래프는 다음과 같이 형성된다.

각 노드에는 1~M 사이의 숫자가 들어간다.(1 <= M <= 100,000 (대략적인 M범위이다.))

어떤 노드 x,y에서 출발하여 사각형을 그리며 다시 x,y로 와야하는데 이때 1. 같은 노드 방문 금지, 2. 같은 번호를 가진 노드 방문 금지,

3. 무조건 사각형을 그려서 와야한다. 는 조건이 있다. 그리고 이때 가장 많이 노드를 방문한 사각형의 방문횟수를 찾아야한다.

이 조건을 통해 문제를 다음과 같이 구상할 수 있었다. 위의 조건을 만족하는 사각형을 그리는 사이클 사이클 중 가장 사이클이 큰 것을 찾아야 한다.

처음에는 유니온파인드라고 생각했다. 무슨 생각으로 그렇게 했는진 몰라도 일단 유니온과 파인드를 만들어보았다.

10분도 지나지 않아 멍청한 짓을 한 것을 깨닫고 N제한을 보고난 후 완전 탐색으로 해결 될 것이라 생각했다.

(사실상 A형 문제에서 유니온 파인드가 나온 확률은 없어보인다.)

결국 BFS로 처음 시작해서 코드를 1시간가량 소모하여 완성했는데 꼬이는 점이 많았다.

각 노드에서 방문노드가 꼬이기 시작했다. 그렇게 1시간 30분을 소모하고(총 3시간을 준다.)

다시 DFS로 접근했다. BFS 코드를 이전에 나쁘지 않게 만들어두었기에 모든 최적화 과정을 DFS로만 만들며 BFS과정을 옮겨줬더니

테스트 케이스들이 모두 통과했다.

하지만 삼성은 이렇게 쉽게 내지 않을거라고 생각하고 하드 테스트케이스를 직접 만들어 돌려보았다.(모든 값이 MAX일때)

이때 50개의 테스트케이스중 46번에서 TLE가 났다.

하지만 어쩔수없었다 이 코드가 최선이었고 메모이제이션, 최적화 등등 모든 과정을 내가 할 수 있는 모든 것을 했기 때문에 이대로 제출했다.

5월 23일이 되었다.

결과 메일이 왔고 다행히 PASS를 받았다.

다음 시험은 B형인데 이게 소멤 2차시험 -> 3차시험인지 그냥 또다른 B형시험인지는 정확히 모르겠다.

더 열심히해서 PS에 대한 능력을 더 길러보고 싶은 하루인 것 같다.