안녕하세요. Softeer 운영 담당자 입니다.

2021년 10월 22일 현대자동차그룹의 재직자 코딩대회 2021 HMG Softeer Programming Festival 의 예선대회가 진행되었습니다.

현대자동차그룹의 수많은 재직자 분들께서 관심과 열정으로 참여해주신 덕분에 성공적으로 예선대회를 마칠 수 있었습니다.

이번 대회를 통해 처음으로 알고리즘 코딩 문제를 접한 분들도 계실테고

졸업 이후 오랜만에 알고리즘 코딩 문제를 풀어보신 분들도 계실 것 같습니다.

아무쪼록 참여해주신 모든 분들에게 축제와 같은 재미있는 시간이 되었기를 바랍니다.

이번 예선 대회에 사용된 문제는 총 7문제로 3시간 동안 경연이 진행되었습니다.

대회 문제는 연습문제로 제공되며, 아래와 같이 간단한 해설을 제공해 드리오니

대회에 아쉬움이 있으셨던 분들은 다시 한번 연습 문제를 풀어보시기 바랍니다.

향후 Softeer의 문제풀이를 제공하는 ALGO TUTOR 를 통해 해설 강의도 제공해드릴 계획입니다.

감사합니다.

예선 1번_비밀메뉴

N＜M 이면 답은 Normal이다.

그렇지 않은 경우, 주어진 수열이 나타나는 위치는 N-M+1가지가 가능하다. 이를 반복문으로 모두 확인해 주면 된다.

위치를 정했을 때, 주어진 수열이 나타나는지의 여부도 O(M)의반복문으로 확인할 수 있다. 따라서 총 시간 복잡도는 O(NM)이다.

예선 2번_전광판

부분문제1

A와 B는 1로만 구성된 숫자이다. 즉 A와 B는 각각 1, 11, 111, 1111, 11111중 하나이다.

모든 숫자가 1임을 알고 있으므로, 각 수의 길이만이 중요하다. N을 A의 길이, M을 B의 길이라고 하면, 답은 2|N-M| 이다.

부분문제2

0-9 각각의 숫자가 7개의 전구 상태에 따라 어떻게 나타나는지를

아래와 같이 각 자리수에 대응하는 전구에 번호를 붙였다고 가정하자.

그러면 각 숫자를 전구로 표현하기 위해 어떤 전구들을 켜야 하는지를 정확하게 표현할 수 있다. 각 숫자 x에 대해, 문자열 S[x]를 다음과 같이 정의하자.

S[x][i]는, 숫자 x를 표현하기 위해 i번 전구를 켜야 하면 1, 꺼야하면 0이다.

예를 들어, S[0]은 1110111이고, S[4]는 0111010이다. 모든 S[x] 값들을 문제를 보고 손으로 작성하여 코드에 넣을 수 있다.

그러면 문제는 S[A]와 S[B] 사이에 값이 서로 다른 위치가 몇 개인지 세는 문제가 되고, 이는 반복문으로 처리할 수 있다.

부분문제3

A와 B 각각의 자리 (일의 자리부터 만의 자리까지)에 대해 독립적으로 2번 부분문제를 해결한 뒤, 모든 답을 더하면 전체 문제의 답이 된다.

2번 부분문제와 달리 특정 자리가 비어 있을 수 있는데, 이 경우 S[empty] = "0000000"과 같이 정의하면 2번 부분문제의 풀이를 똑같이 적용할 수 있다.

예선 3번_회의실 예약

먼저 각 회의실 별로 회의 정보를 모아야 한다. 문자열, map(dictionary) 및 vector(list) 타입을 이용해 같은 이름의 회의실을 모을 수 있다.

각 회의실에 대해 시간을 모으고 나면 이를 순회하며 인접한 시간 사이에 빈틈 (1시간 이상의 간격)이 있는지를 확인해주고 개수를 센다.

개수에 따라 올바른 정보를 출력한다.

예선 4번_좌석관리

시간 제한이 넉넉하게 주어져 있어 O(N^2 · M^2 ·Q)의 시간으로 나이브하게 작업을 처리해도 충분히 빠르게 해결할 수 있다.

작업을 처리하는 것은 문제에서 주어진 그대로를 따라하면 된다.

예선 5번_이미지 프로세싱

연산이 주어질 때마다 격자판에서의 BFS 를 통해 같은 색을 가지는 4-connected 영역을 구한 뒤, 해당 영역의 색을 모두 바꿔 주는 것을 반복하면 된다.

예선 6번_로드 밸런서 트랙픽 예측

부분문제 1의 경우 문제에서 제시된 방식 그대로 시뮬레이션을 수행하면 O(NK)시간에 된다.

부분문제 2의 경우, 서버에 K개의 요청이 들어왔다. 이 요청들이 각 p_{i,j}에 얼마나 분배되는지를 나눗셈 연산으로 계산할 수 있으므로, 분배해 나간다. 이러한 분배의 과정을 위상 정렬 순서대로 반복하면, 모든 서버에 분배되는 요청 개수를 구할 수 있다.

예선 7번_마이크로 서버

부분문제1

$300 \times 3 = 900$ 이므로 300MiB짜리 서비스 3개를 하나의 마이크로서버에 넣을 수 있다.

최대한 많은 서비스를 한 서버에 넣는 것이 이득임이 명백하므로, 답은? $\lceil N/3 \rceil$ 이다.

부분문제2

$301 \times 3 = 903 > 900$ 이므로, 한 서버에 최대 두 개의 서비스만 실행시킬 수 있다.

각 서버에는 서비스 한 개 또는 서비스 두 개를 실행시킬 것이므로, 서비스 두 개를 실행하는 서버가 많을수록 더 좋다. 즉,? $m_i + m_j \le 900$ 을 만족시키는? $(i, j)$ ?쌍 개수를 최대화해야 한다.

일단? $m_1 + m_N > 900$ 인 경우,? $N$ 번째 서비스는 다른 어떤 서비스와도 같이 실행될 수가 없다. ( $900 < m_1 + m_N \le m_2 + m_N \le \cdots$ 이므로) 이 경우? $m_N$ 을 제거하고 전체 문제를? $m_1, m_2, \cdots, m_{N-1}$ 에서 해결하도록 문제 크기를 줄일 수 있다.

$m_1 + m_N \le 900$ 이므로, 적어도 두 서비스를 한 서버에 띄울 수 있는 방법이 있다. 그런데 이 때, 1번 서비스와? $N$ 번 서비스를 한 서버에 띄우는 것이 가능한 최적해 중 하나임을 증명할 수 있다.? $m_1$ 과? $m_N$ 을 제거하고 전체 문제를? $m_2, \cdots, m_{N-1}$ 에서 해결하도록 문제 크기를 줄일 수 있다.

구현할 때에는 실제로 제거하는 것이 아니라, 문제를? $m_{i..j}$ 에서 해결하는? $i$ 와? $j$ 만을 저장해 두면 된다. 그러면 "제거"가 단순히? $i$ ?또는? $j$ 를 1 증가/감소 시키는 것과 같으므로 상수 시간에 처리할 수 있다.

부분문제3

부분문제 1과 2의 풀이를 합쳐서 생각한다.

각 서버에 마이크로서비스를 띄울 수 있는 방법은 아래 세 가지이다.

서비스 3개: 300MiB짜리 서비스 3개를 실행하는 방법밖에 없다
서비스 2개: 합이 900 이하인 서비스 2개를 실행한다
서비스 1개: 아무 서비스나 골라서 실행한다 (주어진 서비스의 요구 RAM이 모두 900 이하이므로)

이 점에서, 아래와 같은 식으로 접근한다.

서비스 3개짜리 서버 대수? $k$ 를 고정한다. 입력에서 300이? $3k$ 번 이상 등장하면 된다. 즉? $m_1 = m_2 = \cdots = m_{3k} = 300$ 이면 된다.
이제? $m_{3k+1}$ ,? $\cdots$ ,? $m_N$ 에 해당하는 서비스들은 서비스 2개 / 1개짜리 서버에만 실행된다고 가정할 수 있다. 이 수열에 대해 부분문제 2의 풀이를 적용하면 된다.

$k$ 로 가능한 경우가? $O(N)$ 가지이고, 부분문제 2를 푸는 데에? $O(N)$ ?시간이 드므로, 시간복잡도는 총? $O(N^2)$ 이다.

부분문제4

부분문제 3의 관찰을 하되, 부분문제 2를? $O(N)$ ?대신? $O(900 - 300)$ 에 해결할 수 있다.? $300 \le m_i \le 900$ 이므로 같은 값이 여러 번 중복되어 들어 있을 것이므로, 수열? $m$ ?그 자체 대신 그 빈도수 배열? $freq$ 을 구하여 같은 pairing을 한꺼번에 처리할 수 있다.

소프티어

학습 튜터

2021 HMG Softeer Programming Festival 예선 대회 문제 해설

예선 1번_비밀메뉴

예선 2번_전광판

부분문제2

예선 3번_회의실 예약

예선 4번_좌석관리

예선 5번_이미지 프로세싱

예선 6번_로드 밸런서 트랙픽 예측

예선 7번_마이크로 서버