2022년도 현대모비스 코딩 테스트 유사 문제

  • 2022/08/07
  • 5-minute read

Problem

Table of Contents

설탕 배달 (BOJ 2839)

  • 3kg, 5kg의 설탕 봉지가 있음
  • 특정 무게의 봉지를 들고 갈 때, 봉지의 개수를 최소화하고 싶음
  • 얼핏보면 Greedy Algorithm을 적용하면 되지 않나? 싶은 생각이 든다.
  • 실제로 3kg을 최소의 개수로 들면서, 5kg을 많이 가져갈 수록 봉지 수를 줄일 수 있으므로, 이와 같은 방법도 타당하다고 할 수 있다.
  • 다른 방법으로는 Dynamic Programming을 이용하여, 각 무게를 만들어낼 때, 몇 개의 봉지가 최소 봉지인지를 Tabulation하여 각 봉지의 개수를 확인하는 방법도 있다.
  • 따라서 입력된 무게를 운반하는 최소 봉지의 개수를 출력으로 내주면 되며, 만약 불가능한 무게라면 -1을 반환하면 된다.

설탕 배달 풀이 - Greedy Algorithm

  • 우선 Greedy Algorithm을 적용한다면, 3kg을 최소로 들고 가면서, 5kg을 최대한 많이 드는 방법이 봉지의 개수를 줄이는 방법이다.
  • 그런데 일반적인 Greedy Algorithm을 적용하여, 5kg을 들 수 있는 만큼 최대한 들고, 3kg을 채운다면 아래와 같은 문제가 생길 수 있다.
  • 예를 들어, 9kg을 들어야 한다면, 5kg 1개를 우선 선택하고 나면 4kg이 남는데, 그런 경우 3kg으로는 만들어 낼 수 없으므로, -1을 반환하게 되지만, 실제로는 9kg을 3kg 3개로 만들어낼 수 있으므로, 답은 3이 되는 것을 볼 수 있다.
  • 이와 같은 상황을 고려한다면, 3kg을 최소한 적게 가져가기 위해, 3kg을 하나씩 줄여가면서, 5kg으로 나뉘어지는 지 확인하는 방법을 적용하면 된다는 것을 알 수 있다.
  • Greedy Algorithm의 경우 현재 상황의 최적의 선택 값이, 전체의 최적이 되는 경우에 적용이 되는데, 이 문제에서는 현재 상황에서 3kg 봉지를 가장 적게 가져가는 방법이, 전체 봉지의 개수를 가장 줄일 수 있는 방법이라고 볼 수 있다.
  • 코드는 다음과 같이 작성할 수 있다.
N = int(input())

result = 0
while N % 5 != 0:
    result += 1
    N -= 3
    if N < 0:
        result = -1
        break

if result == -1:
    print(result)
else:
    result += N // 5
    print(result)

설탕 배달 풀이 - Dynamic Programming

  • 두 번째로 Dynamic Programming을 적용한다면, Bottom-Up방식을 적용하여 Tabulation을 사용하여 문제를 해결할 수 있다.
  • 시작하기 위한 값은 1, 2, 3, 4, 5kg을 만들어 낼 수 있는 최소 개수인 DP[1] = -1, DP[2] = -1, DP[3] = 1, DP[4] = -1, DP[5] = 1으로 설정하고 시작한다.
  • 그 이후, n kg을 만들어 내기 위해서는 DP[n-3]과 DP[n-5] 중 작은 값을 선택하면 최소 개수를 유지할 수 있다.
  • DP[n] = min(DP[n - 3], DP[n - 5])가 되는 것이다.
  • 코드는 다음과 같다.
N = int(input())

dp = [0] * (5001)
dp[1] = -1
dp[2] = -1
dp[3] = 1
dp[4] = -1
dp[5] = 1

for i in range(6, N + 1):
    if dp[i - 3] == -1 and dp[i - 5] == -1:
        dp[i] = -1
    elif dp[i - 3] == -1:
        dp[i] = dp[i - 5] + 1
    elif dp[i - 5] == -1:
        dp[i] = dp[i - 3] + 1
    else:
        dp[i] = min(dp[i - 3] + 1, dp[i - 5] + 1)

print(dp[N])

평균 (BOJ 1546)

  • 시험 성적 N개가 주어졌을 때, 이 중 최대 값을 M이라 하면, 모든 성적을 점수 / M * 100으로 변경
  • 모두 변경된 점수의 새로운 평균을 구하는 프로그램 작성
  • 일반적인 구현 문제
  • 입력을 잘 받고, list타입을 편하게 다룰 수 있다면 쉽게 해결할 수 있는 문제로 예상

평균 문제 풀이

  • N을 입력 받고, 전체 성적을 받아서 수정한 후, 새로운 평균을 계산하는 과정은 다음과 같습니다.
  1. N을 입력 받기
  2. 전체 성적을 입력 받기
  3. 전체 성적 중 최대 값을 찾기 (M)
  4. 전체 성적을 점수 / M * 100으로 바꾸기
  5. 새롭게 계산된 성적의 평균 계산하기
  • 코드는 다음과 같습니다.
N = int(input())
scores = list(map(int, input().split()))

max_score = max(scores)

scores = map(lambda x: x / max_score * 100, scores)
# for i in range(N):
#     scores[i] = scores[i] / max_score * 100

print(sum(scores) / N)

네 수 (BOJ 10824)

  • 자연수 A, B, C, D가 주어졌을 때, A와 B를 붙인 수와 C와 D를 붙인 수의 합을 구하는 프로그램
  • 예를 들어 A = 20, B = 30이면, A와 B를 붙이면 2030이 된다.
  • 문자열을 붙이는 기능 및 이를 정수로 바꾸어서 계산하는 내용을 아는 지를 묻는 문제
  • 간단하게 해결할 수 있다.

네 수 풀이

  • A, B, C, D를 문자열로 입력을 받아서 일반적으로 정수로 바꾸는 작업을 하지만, 여기서는 그냥 붙여야하므로, 문자열 그대로 진행하는 것이 편하다.
  • 문자열은 서로 +할 경우, 뒤에 붙어진다는 점을 이용하면 쉽다.
  • 코드는 다음과 같다.
A, B, C, D = input().split()

AB = int(A + B)
CD = int(C + D)

print(AB + CD)

단어의 개수 (BOJ 1152)

  • 영어 대소문자와 공백으로 이루어진 문자열이 입력
  • 해당 문자열의 단어의 개수를 구하는 프로그램
  • 단어는 공백을 기준으로 구분됨
  • 일반적인 문자열 처리 문제
  • 최종 단어의 개수를 출력

단어의 개수 풀이

  • 입력되는 내용을 보면 문자열 왼쪽, 오른쪽, 가운데 모두 공백이 있을 수 있음
  • 따라서, strip()함수를 적용하면, 문자열 좌, 우에 있는 공백은 제거할 수 있음
  • 문자열의 경우 split()함수를 적용하면 쉽게 공백을 기준으로 나누어줄 수 있음
  • 코드는 다음과 같습니다.
input_str = list(input().strip().split())
print(len(input_str))

회전 초밥 (BOJ 2531)

  • 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 주어짐
  • N개의 줄에 벨트 위에 적힌 초밥의 종류가 입력
  • 입력된 벨트 위의 한 점에서 k개의 접시를 연속으로 먹으면 할인되며, 이 경우 c에 적힌 종류의 초밥을 하나 무료로 제공, c 종류 초밥은 벨트 위에 없어도 요리사가 만들어 줄 수 있음
  • 손님이 먹을 수 있는 초밥 가짓 수가 최대가 되도록 하는 프로그램을 작성

회전 초밥 풀이

  • 우선 N, d, k, c를 입력으로 받는다.
  • 나머지 N줄에 입력된 초밥의 종류를 확인한다.
  • 연속해서 k개를 먹을 때, 종류가 최대한 많은 경우를 확인한다.
  • 종류가 최대한 많은 경우가 여러가지 일 경우, 쿠폰 번호 c가 포함되지 않은 경우를 선택한다.
  • 최대 초밥의 가짓수를 정수로 출력한다.
  • N개의 정수로 이루어진 list의 일부에 해당하는 list가 중복이 적은 경우를 찾으면 된다.
  • 중복을 제거하기 위해 list를 set으로 변경하는 기술을 사용할 수 있다.
  • 또한 set에 c가 포함되어 있는지 아닌지 여부를 in을 통해 확인한다.
  • 코드는 다음과 같다.
N, d, k, c = map(int, input().split())
belt = []
for _ in range(N):
    belt.append(int(input()))

belt = belt + belt[0 : k - 1]

max_cnt = 0
for i in range(N):
    tmp_belt = set(belt[i:i+k])
    if c in tmp_belt:
        tmp_max = len(tmp_belt)
    else:
        tmp_max = len(tmp_belt) + 1
    if tmp_max > max_cnt:
        max_cnt = tmp_max

print(max_cnt)

Review

  • 수업들은 학생이 봤다는 현대 모비스 코테 문제
  • 1, 5번 문제를 제외하고는 너무 기초적인 문제였다.
  • 문제 난이도가 너무 오락가락 하는 느낌이 있는 듯?
  • 2, 3, 4는 그냥 주는 문제고, 1번, 5번을 맞추냐 못맞추냐의 문제 같기도…
  • 확실히 완전 컴퓨터 공학과 쪽에서 지원하는 쪽에서 진행하는 코테가 아니라면, BFS&DFS, 시뮬레이션, DP 등의 문제보다는 Greedy나 일반적인 구현 문제가 많이 나오는 것으로 보인다.
  • 나쁘지 않은 경험이었던 것 같다.

comments