2022 SK ICT FAMILY 1차 코딩테스트 후기

우연히 프로그래머스 갔더니 챌린지가 있어서 경험도 쌓을겸 챌린지에 신청했다. 아직 군인 신분이라 채용까지 이어지지는 않겠지만 어떤식으로 나오는지 궁금해서 신청해봤다.

12일 오전 10시에 열린 코테는 총 3시간동안 4문제로 진행됐다. 기업 코테 자체가 처음이라 상대적인 난도를 매길 순 없겠지만 내 기준으로 생각보다 어렵지 않게 출제된 것 같았다.

1번 문제는 정렬과 그리디로 해결이 가능했다. 1,5,10,50,100,500원짜리 동전의 최소공배수가 500이므로 500을 기준으로 효율을 계산해준 후 내림차순 정렬해줬다. 앞에서부터 차례대로 그리디 방식으로 화폐를 만들어주면 끝

2번 문제는 단순 구현문제였다. n*n배열을 바람개비모양으로 각 모서리에서 중앙으로 오는 과정을 구현해야 하는데 먼저 바람 방향에 따른 이동 방향을 배열로 만들어두고 각 모서리에서 n-1, n-3, ... 0 만큼 방향 바꿔가며 수를 채워줬다. n이 홀수면 가운데에 수 하나를 더 채워야 한다

3번 문제는 dp 문제였다. 0,0 에서 i,j까지 경우의 수를 미리 구해두고, 대각선마다 {(0,0)~(대각선시작)} * {(대각선끝)~(width,height)} 을 계산한 값들을 모두 더해줬다. (대각선끝)~(width,height)는 결국 (0,0) ~ (width-대각선끝x, height-대각선끝y)이므로 dp로 쉽게 해결할 수 있었다.

4번 문제는 재귀(dfs) + 약간의 아이디어가 필요한 문제였다. 트리에서 i~j거리 + j~k거리 = i~k거리가 되는 i,j,k 쌍의 개수를 찾는 문제였다. 처음 생각한 것은 하나의 리프노드에서 다른 리프노드까지 이동하는 경로 중 3개를 순서 없이 뽑는 것이었다. 모든 리프노드를 짝지어서 하기엔 시간초과가 날 것 같아서 dfs로 가닥을 잡아보았다. 결국 3개의 점을 뽑아야 하는데 현재 노드 기준 3개의 점을 뽑으려면 (왼쪽 서브트리에서 2개, 오른쪽 서브트리에서 1개), (왼쪽 서브트리에서 1개, 오른쪽 서브트리에서 2개), (왼쪽 서브트리에서 2개, 자기자신), (오른쪽 서브트리에서 2개, 자기자신), (왼쪽 서브트리에서 1개, 자기자신, 오른쪽 서브트리에서 1개) 이런 경우들이 나온다. 즉 서브트리에서 필요한 정보는 조건에 맞게 2개 점을 뽑는 경우의 수와 조건에 맞게 1개 점을 뽑는 경우의 수(=서브트리의 노드 개수)이다. 
{서브트리에서 조건에맞게 2개 점 뽑는 경우의 수, 서브트리의 노드 개수}를 구한 다음 서브트리1, 현재노드, 서브트리2에서 조건에 맞게 3개의 점을 뽑는 경우의 수를 구해주었다. 문제에서 무조건 이진트리가 나온다는 조건이 없어서 낚일뻔했지만 서브트리를 한번씩만 방문해서 정보를 구했고, 시간 복잡도는 O(V+E), 트리니까 O(N)으로 잘 해결한 것 같다.

결과는 통과다.

좋은 기회라고 생각하고 열심히 2차 코테도 풀어봐야겠다.