INTERVIEW - Coding Test (2021 Sep)

September 14, 2021 3 minute read

2021년도 9월 둘째 주 주말은 잊지 못할 주말이 될 것 같다. 무려 코딩테스트 3개가 몰려 있던 주말이었다.

9/11 09:30 ~ 12:30

L000사 지옥의 주말의 시작을 알리는 테스트.

5? 6?문제였는데, 몇일 지나지도 않았는데 문제 내용을 완전히 다 까먹었다… 그도 그럴 것이, python으로 오랜만에 코딩 문제를 풀다 보니 참조 관련해서 꼬이는게 너무 많았다. (원본 리스트가 계속 바껴요ㅠ)

두개 반 정도 풀다가 ㅈㅈ. 좌절 모드 on.

9/11 14:00 ~ 19:00

K0000사 7문제 중 4.5문제 해결. 갓 파이썬 배운 1년 반 전 쯤에 같은 회사의 테스트를 본 적이 있었는데, 그 때 당시 2문제 풀고 좌절을 맛본거에 대비해서는 매우 잘 본 수준. (그래도 늘긴 늘었나 보다.)

오전 3시간에 이어 5시간에 걸친 테스트로 아주 녹초가 되었다.

못 푼 문제 중에 well-known 이라고 알려진 문제가 있어서 여기서 잠깐 리뷰해 보겠다.

2차원 누적합(Cumulative Sum)

2차원 배열 (board)에서 특정 사각형 영역의 값을 일괄적으로 ‘d’만큼 더하거나 빼는 쿼리가 들어온다. 쿼리가 끝나고, 최종 배열에서 0보다 큰 원소들의 개수를 세는 문제.

정확도와 효율성까지 보는 문제였으며, 여기서 정확도만 맞추는 코딩은 그냥 쿼리가 올때마다 board의 값을 변화시켜주면 되는 문제라 매우 쉽다. 문제는 효율성!

우선 2차원 배열의 누적합 배열이 어떤 것인지 살펴보자. 아래와 같이 3 X 4 배열이 있다고 할 때, 누적합을 구하는 과정은 다음과 같다.

2 3 1
4 5 1
4 1 2

먼저, arr[1][1]의 값은 그 이전의 모든 값의 합인 3 + 2 + 2 + 4가 된다. 이 때, 마치 dp 처럼 이전 계산할 수 있는 방법이 있는데, 좌측과 위쪽의 값을 더하고 왼쪽 위의 값을 빼주면 된다.

arr[i][j] = arr[i-1][j] + arr[i][j-1] - arr[i-1]arr[j-1]

이제 2차원 배열의 누적합을 구하는 방법을 알았다, 이제 문제의 쿼리들을 이 누적합을 이용해서 한 번에 처리하게끔 해주면 된다.

4 X 5 의 board를 예를 들어 보자. 아래 보드에서 query가 “(1,1), (2,2), +5” 라면,

쿼리 배열은 (board 배열과는 다름을 주의하자) 아래와 같이 만들어 주자.

0  0  0  0
5  0 -5  0
0  0  0  0
-5  0  5  0

이렇게 4개의 꼭지점에만 값을 처리해주면, 나중에 이 쿼리 배열을 누적합 배열로 만들면 원래 문제에서 원했던 쿼리의 영역에만 ‘d’값이 더해짐을 알 수 있다.

지금 위의 하나의 쿼리만 적용된 쿼리 배열을 누적합을 만들면,

위와 같이 쿼리 “(1,1), (2,2), +5” 이 적용된 것을 알 수 있다.

이를 이용해서 쿼리들을 우선 쿼리배열로 합친 후, 누적합을 통해 최종 변화를 확인하여 문제의 ‘효율성’을 통과할 수 있다.

9/12 13:00 ~ 16:30

‘N0000’사 6문제 중 3.5문제 해결. 근데 사실 첫번째 문제는 깍두기 문제라.. 5문제 중 2.5문제라고 봐야 할 것 같다. 이 시험에서는 지나고 보니 아쉬웠던 문제가 두 문제나 있었다. (SQL 포함)

SQL 문제

고객 정보와 아이템 정보 테이블이 있다. 고객 정보에는 ‘Budget’이 있고, 아이템에는 ‘Price’ 정보가 있으며, 고객이 최대한 살 수 있는 아이템들의 정보를 한 row 씩 ‘고객 name, 고객 Budget, 아이템 name, 아이템 Price’로 반환해야한다.

일단 내가 이 문제에서 껄끄러웠던 부분은, 살 수 있는 아이템이 있으면 잔고를 고객 별로 차감하면서 잔고가 0 이상일 때만 반환해야하는데 그렇게 하기는 SQL에서 쉽지 않았다.

나중에야 꺠달았는데, 우선 아이템 정보 테이블을 가격 순으로 정렬하고, ‘SET 변수’를 통해서 현재까지의 아이템을 모두 샀을 때의 가격인 Cumulative Sum 컬럼을 추가한다.

최종 테이블은 이 Cumulative Sum과 고객의 Budget과 비교하여 ‘WHERE’에 넣으면 된다… 끝…

5번 문제

솔직히 분명 예전에 풀었던 문제였던거 같은데 쓸데 없이 익숙하지 않은 SQL 문제 푸느라 시간을 날려먹은 것도 있고, 이번 코딩 테스트 주말에 ‘비트 마스크’ 개념 자체를 쓸 생각을 안했던게 컸다.

1차원 평면에서 rrrlrlr 등 주어진 sequence가 있으면 해당 sequence로 만들 수 있는 (순서가 동일한) sub-sequence 중에 원하는 end point로 가는 경우의 수를 구하는 문제였다.

완전 탐색을 ‘비트 마스킹’ 기법으로 해당 신호가 sub-sequnce에 포함하는지 안하는지로 해서 모든 경우의 수를 확인하면 된다.

마치며

삼성 SW Certi Pro 레벨 따고 나서 3개월 정도 코딩 문제를 들여다 보지도 않았던게 화근인거 같다. Pro 레벨 따논게 있어서 어느 정도 코딩 문제는 문제 없다고 생각해 버린 것.

위 3개의 코딩 테스트 모두 딱 한 개만 더 풀었더라면 안정권이었을 것 같다는 느낌이 든다. 지금 되게 간당간당하다.

좀만 더 열심히 할 걸 아쉽다… 결과 나올 때 까지 기다려야지 뭐ㅠ

Dada Ahn