[코테] 2024 상반기 ICT 학점연계 프로젝트 인턴십 코딩테스트 문제 유형 및 후기

winluck·2024년 2월 6일

학교에서 벗어나고 싶어 ICT 인턴십에서 Springboot 위주로 지원하였고, 코딩테스트에 응시한 후기를 남기려 한다.

우선 프로그래머스와 다르게 <해커랭크> 라는 외국 PS 사이트에서 코딩테스트를 응시하였다. 개인적으로 시험 응시 중 오타가 아닌데 오타로 인식하고 발생하던 컴파일 버그가 많아서 꽤 불편했다.

나는 C++로 응시했는데, 다른 언어는 어떤 난이도였는지 잘 모르겠다.
개인적인 체감 난이도일 뿐이니, 큰 의미는 없다.

문제 유형 및 난이도

주어진 배열을 순회하며 특정 인덱스까지 왔을 때의 이때까지 순회한 값 중 가장 큰 값에서 가장 작은 값을 빼는 문제

arr[i] < arr[i+1]인 경우가 반드시 존재해야 하며, 그렇지 않으면 -1 반환
n이 10^5였기 때문에 완전탐색은 불가능하며, 먼저 arr[i]<arr[i+1]인 지점을 찾은 뒤 해당 인덱스부터 값을 갱신해나가면 된다.
1번이란 생각에 습관적으로 완전탐색을 시도하려다가 제약조건을 먼저 확인하자는 교훈 덕분에 O(n)으로 해결하고 넘어갔다. 다음에도 계속 주의해야겠다.

주어진 배열을 순회하며 low <= arr[i] <= high에 해당하는 수의 개수를 찾는 문제

low/high는 배열 형태로 들어오며 최대 10^9였기에 마찬가지로 완전탐색은 불가능했다.
초반엔 map을 활용해 시간복잡도를 줄이려 했으나 실패했다.
이분 탐색을 적용하여, low 값에는 lower_bound(), hight 값에는 upper_bound()를 적용하여 배열 내에서 두 인덱스를 구해 빼면 된다.

9466번: 텀 프로젝트
이 문제와 굉장히 유사하나, 로직이 거의 동일했음에도 불구하고 통과하지 못했다,,
~~내다버린 4시간~~

처리해야 할 1~n번까지의 작업 중, 작업마다 선행 작업이 존재하며, 해당 작업 관계를 기반으로 한 그래프 상에서 존재하는 사이클의 크기 및 개수를 분석해야 하는 문제

예를 들어 아래와 같다.
a = [1, 2, 3, 4, 6, 5]
b = [7, 6, 4, 1, 2, 1]

이 경우 작업은 아래와 같은 형태로 진행되며, 2와 6은 사이클을 이룬다.
7
|
1
|\
4 5
|
3

첫 번째 방식은 언급한 백준 문제처럼, DFS를 통해 사이클을 판정하고 사이클을 이루는 노드들의 갯수를 세어 총 결과에서 빼는 식으로 처리했다.
그런데 테스트케이스 중 절반만 통과했고, 나머지는 히든 테케라서 정답이 무슨 값인지조차 확인할 수 없는 상황이었다.
선행 작업이라는 아이디어를 살려 위상정렬을 시도하여 사이클을 이루지 않는 모든 노드들을 찾는 식으로 처리해보았으나 DFS 방식보다 더 많은 테케가 실패했다.
첫 번째 방식에서 사이클을 이루지 않는 노드의 총합을 찾는 것으로 전략을 바꾸어, 전역 배열 cycled[]를 활용해 사이클을 이루는 데 포함되는 경우 이를 true로 표기하여 정답 카운트 시 배제하고자 했으나 역시 실패했다.

로직을 작성할 때마다 떠오르는 예외가 너무 많아서 골치가 아팠다.
결국 절반의 테케만 맞은 채 4.5솔로 제출을 마감하였다.

RGB 값을 의미하는 24비트 문자열이 입력되었을 때 이 비트가 어느 색과 가장 유사한지 계산하여 해당 색 문자열(White, Black, Red 등)을 반환하는 문제

비트문자열을 8 * 3등분하여 각각 R/G/B로 잘라낸 후, 해당 값을 색깔별 테이블의 기준값과의 유클리드 거리를 계산하면 된다.
예: (255, 255, 255)와 Black(0, 0, 0)의 유클리드 거리는 (255-0)^2 * 3의 제곱근이다.
침착하게 시키는 대로 색깔별 거리를 계산하여 가장 가까운 색깔을 판정하여 해당 어휘를 반환하면 된다. 다만 가장 가까운 색깔별 거리 값이 여러 개면 예외처리가 필요했다.
루트를 씌우기 전 a = b이면 둘의 제곱근도 서로 같기에 굳이 double인 제곱근까지 계산해서 비교할 필요는 없었다.
생각해보니까 3등분할 때 substr 함수를 사용하지 않고 2차원 for문으로 약간 흙내나게 했던 것 같다.

이미지를 나타내는 0/1로 이루어진 2차원 격자 모양의 String 배열을 받아, 서로 1로 이루어진 동일한 영역의 개수를 찾는 문제

예를 들면 아래와 같다.
A
1 0 1
1 0 1
1 0 0
B
1 0 1
1 0 1
1 0 1

이 경우 왼쪽 3칸은 영역 내부 1의 개수와 위치까지 모두 같기에 "동일한 영역"이며, 오른쪽 칸은 서로 모양이 다르기 때문에 동일한 영역이 아니다. 따라서 정답은 1이다.

둘 다 아직 방문하지 않았고 값이 1인 지점에서 두 이미지에 대한 BFS를 통해 해당 영역의 모든 좌표를 vector에 담아 반환받은 후 이를 비교하여 판정하였다.
가장 어려워보였던 3번을 제외한 4문제를 약 1시간 50분 동안 검토 및 최적화까지 마친 뒤, 3번에 돌입했다.

4.5솔로 끝나서 너무 아쉽다. 인턴 붙었으면 좋겠다.

Discover Tomorrow