삼성전자 B형(Pro) 시간을 줄이기 위한 팁
시간을 줄여야 하는 이유
삼성의 SW 역량테스트의 경우에는 Test Case에 대하여 한번에 돌려서 평가하는 방식으로 진행되기 때문에 이를 고려한 초기화 과정이 반드시 들어가야 합니다. 이때, 초기화 방법을 어떻게 하냐에 따라서 시간이 줄어듭니다. 또한 문제 유형에 따라서 구현해야 하는 특정 함수의 호출 횟수가 100.000번 이상으로 작동하기 때문에 효율적으로 구성하지 않으면 반드시 시간 초과가 발생하게 됩니다. 따라서, 아래에서는 시간을 줄일 수 있는 몇가지 팁을 드리고자 합니다.
1. 조건에 맞는 장소 찾기
해당 유형 2차원 공간이 주어지고 높이가 다른 땅이 주어지는 경우입니다. 해당 땅위에 특정 형태를 가진 구조물을 설치한다고 가정했을 때 설치가 가능한 공간을 찾는 문제입니다. 해당 유형의 문제 풀이시 매번 탐색을 진행할 경우 넓은 공간으로 인해서 반드시 시간 초과가 나기 때문에 해시를 통해 초기에 같은 유형의 지형을 파악해서 저장할 필요가 있습니다. 예시를 보여드리자면 다음과 같습니다.
5x5 필드가 주어지고 가로가 3이고 세로 1인 구조물(2,1,2)을 설치한다고 가정해봅시다. 설치 조건은 설치한 다음 설치된 영역의 높이가 같아야한다고 가정해봅시다. 설치를 위해서는 좌측에서 우측으로 기준으로 높이에 관하여 뺄셈을 진행했을 때 (-1, 1) 이 되어야 한다는 것을 알 수 있습니다. 해당 조건을 충족하는 위치를 찾아보면 다음과 같습니다.
위 이미지와 같이 3군데를 찾을 수 있습니다. 이렇게 탐색된 영역에 대하여 기준점을 잡고 (-1,1)인 Key 값 내부에 해당 영역을 찾아갈 수 있는 좌표 정보를 넣어준다면 이후 설치 함수가 진행될 때 빠르게 가능한 위치를 찾을 수 있습니다.
2. 전체에서 특정 기준으로 최고인 대상 파악하기
해당 유형은 상품을 관리하는 형태의 DB를 구축하는 문제의 유형에서 나타납니다. 각 카테고리 별로 제품이나 상품에 대한 정보를 기준으로 우선순위 큐를 구축할 필요가 있으며 전체 상품에 대한 우선순위큐가 필요하기도 합니다. 다만, 최고인 대상만 파악하면 된다면 전체 상품에 대한 우선순위큐를 구축할 필요가 없습니다. 각 카테고리 별로 최고인 대상을 추출하여 이중에서 최고인 제품만 찾아내면 되기 때문입니다. 이렇게 우선순위큐 하나를 줄인다면 정렬하는데 드는 코스트를 줄여서 전체 동작 속도를 줄일 수 있습니다.
3. 공간 압축하기
해당 유형은 매우 큰 2차원 맵에 흩뿌려진 대상들이 있을 때 주어진 특정 좌표를 기준으로 조건에 부합하는지 탐색하는 과정에 유용합니다. 해당 문제의 경우의 맵의 가로 세로 길이가 최소 10,000을 넘어가는 경우가 많기 때문에 모든 경우에 대해서 탐색을 진행하는 경우 시간초과가 발생하게 됩니다. 따라서 공간을 줄여서 특정 영역에 대한 탐색만 진행하면 됩니다.
예시는 다음과 같습니다.
25 X 25 영역에 어떤 대상이 다음과 같이 흩뿌려 있다고 가정해보겠습니다. 현재는 눈으로 충분히 파악할 수 있을 정도지만 해당 영역이 수십 배 커지고 대상도 더 많아진다면 계산하는데 시간이 오래 걸릴 것입니다. 이때, 우선 순위에 들 수 없는 대상을 제외할 수 있는 수식이 문제에서 주어졌다면 해당 수식을 기준으로 맵을 압축할 수 있게 됩니다. 여기서는 5x5로 맵을 압축하게 되었다고 가정해보겠습니다.
압축을 진행하게 되면 다음과 같이 줄어들게 되면 문제 조건에 따라 달라질 수 있지만 주어진 좌표가 속해있는 위치를 포함하여 총 9개의 영역에 대한 탐색만 진행하면 후보를 고를 수 있게 됩니다.
마치며
해당 시간을 줄이는 팁 외에도 B형에는 다양한 유형의 문제들이 존재합니다. A형처럼 시뮬레이션이지만 시간 제한이 빡빡한 문제가 나오기도하며 Trie 같은 알고리즘을 적용해야 빠르게 풀 수 있는 문제도 존재합니다. 따라서, 해당 알고리즘을 익히시되 위에서 언급한 유형의 문제가 나오게 되신다면 위의 설명을 토대로 구현을 하시면 시간 안에 작동하는 코드를 작성하실 수 있으리라 생각합니다.