2024년 하반기 ICT인턴십 코딩테스트 후기🧑‍💻

알고리즘을 꾸준히 풀지 않으면 먼저 가 있던 알고리즘 실력이 뽀록난다는 얘기가 있다.
나는 이 이야기를 무척 좋아한다.

는 그냥 해본말이고, 코테는 기회가 되면 푸는게 좋은 것 같다. 알고리즘을 얼마나 열심히 풀었는지.. 스스로 평가하는 지표가 되기 충분하다.

겸사겸사 ict인턴십 코딩테스트를 보았다.

• 일시 : 24.7.10(수) ~ 24.7.11(목) 중 아무때나 시작
• 시간 : 6시간
• 문제 : 5문제
• 언어 : 지정된 언어(C++,Python, Java, JS... ) 등 웬만한 언어는 지원한다.
• 플랫폼 : 해커랭크

처음 접하는 플랫폼이었지만, 지난 후기들을 참고했을때 별로 어렵게 나오는 것 같지 않았고, 6시간이면 어떻게든 다 풀 수 있을 것 같았다.

그리고 캠이나 화면공유같은 제한이 없고, 검색에도 제한이 없는 것 같았다. 화면이 모니터링되고 있다고 나타나긴 하지만, 이게 정말 동작하는건지는 모르겠다.

테케는 약 십수개 정도이고, 테케의 입출력은 비공개이지만 출력을 통해 확인할 수 있다.

해커랭크라는 플랫폼이 익숙치 않았고, 모든 문제가 영어여서 조금? 난해한 부분이 있었다. 복붙이 안돼서 그냥 머릿속으로 직독직해하고 예시 테케를 보며 이해했다.

(문제 저작권으로 인해 자세한 설명은 적지 않았으며, 문제시 삭제하도록 하겠습니다.)

문제1

주어진 문자열에서 최소로 등장한 문자를 구하는?느낌의 문제였다. 길이도 길지 않고 이해하기도 쉬웠다.

• 장르 : 문자열
• 난이도 : Bronze 3 (추정)

문제2

자연수가 주어진 배열에서, 이웃한 값으로 거듭제곱 연산 + 모듈러 연산을 진행하는 문제였다.
$arr[i]^{arr[i+1]}$ 의 느낌?
$arr[i]$ 의 값이 적당히 커서, 계산 결과가 int 범위는 한참 벗어나므로 중간중간 모듈러 연산을 진행했어야 할 것 같다.
다만 나는 파이썬으로 했어서, 그냥 거듭제곱 했더니 통과돼서 제출해버렸다. 파이썬최고~

• 장르 : 사칙연산
• 난이도 : Bronze 2 (추정)

문제3

전진, 좌로돌기, 우로돌기 세 가지 커맨드를 수행하는 로봇이 있다.
커맨드를 조합하여 작성된 commands가 있고 무한히 반복될 때 로봇이 같은 동작을 진행하는 루프에 빠지는지 구하는 문제이다.

단순히 커맨드를 수행했을 때가 아니라, 여러번 수행했는데 루프에 빠지는 경우도 고려해야해서 로직을 떠올리기 조금 까다로웠다. ex)commands = [좌로돌기,좌로돌기]

처음엔 그래프 탐색인가 했지만, 커맨드를 1번,2번,3번,4번 수행했을 때 처음과 같은위치 & 같은방향을 가리키는 것을 조건으로 판단하였다.

• 장르 : 시뮬레이션 구현
• 난이도 : Silver 4 (추정)

문제4

와일드카드(?)가 포함된 길이가 7인 패턴이 있고, 0~8의 숫자가 매칭될 수 있다. 그리고 요구하는 조건에 맞게 매칭할 수 모든 경우의 수를 찾는 문제였던 것 같다.

어떤 방식으로 풀어도 되는게, 완전탐색을 돌려도 $9^7 = 4,780,000$ 이기 때문에 TLE, MLE가 날 수가 없었다.
정석대로 한다면 백트래킹을 이용한 풀이가 먼저 생각이 나지만, 나는 재귀를 이용하여 나오는 모든 문자열과 패턴을 매칭하는 방식으로 풀었다.

• 장르 : 백트래킹 Bruteforce
• 난이도 : Silver 3 (추정)

문제5

최대 1000 x 1000 크기의 2차원 리스트가 존재하고, 모든 범위, 크기의 정사각형의 합을 구한다. 그리고 조건에 부합하는 크기의 경계값을 구하는 문제였다.

첫 번째는 대놓고 2차원 누적합을 사용하라는게 보여서 계산하였다.
그리고 조건에 맞는 경계값을 구하는 과정에서 최악의경우 $O(N^3)$이 되어서 TLE가 난다.
2차원 누적합들을 전부 구하는 과정에서는 $O(N^2)$가 불가피하여 경계값을 구할 때 시간단축을 위한 트릭이 필요했다.
나는 이분탐색을 떠올렸고, 가장 쉬우면서 떠올리기 쉬운 풀이가 아닌가 싶다. 다만 나는 떠올리는데 많은 시간을 썼고, 이 문제를 푸는데 1시간 넘게 투자한 것 같다.

최종적으로 $O(N^2\log{N})$ 또는 그 이하의 시간복잡도로 풀어야한다.

• 장르 : 누적합 이분탐색
• 난이도 : Gold 2 (추정)

---

오랜만에 코테를 풀었는데, 앞 4문제에서는 쉬우면서도 잔잔한 실수를 하느라 시간을 좀 썼다. 그래도 5번 문제가 좀 어려웠는데 스스로 이분탐색을 떠올린 나..칭찬해^^