2022년도 SAFFY 8기 코딩 테스트 유사 문제

2022/06/01
4-minute read

Problem

홀짝 칵테일 문제 설명
홀짝 칵테일 풀이
선수과목 문제 설명
선수과목 풀이
Review

홀짝 칵테일 (BOJ 21312)

문제 내용이 꽤 길다…
결과적으로 보면 내용은 다음과 같았다
칵테일은 고유 번호의 곱을 의미한다
칵테일(곱셈의 결과)이 짝수보다는 홀수가 맛있다 (홀수 > 짝수)
홀수끼리 또는 짝수끼리는 숫자가 크면 더 맛있다 (큰 수)
정리해보면, 3개의 숫자의 조합된 값의 곱을 이용하여, 홀수 중 제일 큰수, 불가능하면 짝수 중 제일 큰 수를 출력하면 되는 문제

홀짝 칵테일 풀이

홀수 $\times$ 홀수 $=$ 홀수
홀수 $\times$ 짝수 $=$ 짝수
짝수 $\times$ 짝수 $=$ 짝수
위 세 가지 내용을 알고 있는 상태라면 문제가 쉽게 풀린다

3개의 숫자를 받고, 각 값이 홀수인지 짝수인지 확인한다.
홀수가 하나라도 있다면, 홀수의 곱을 출력한다.
홀수가 하나도 없다면, 3개 숫자의 곱을 출력한다.

numbers = list(map(int, input().split())) # 숫자 3개를 list로 입력 받는다.
isOdd = [False] * len(numbers) # 홀수 테이블 초기화

for i in range(len(numbers)): # 모든 수에 대해 홀수 or 짝수 여부 판단
    if numbers[i] % 2 == 1:
        isOdd[i] = True

result = 1
if True in isOdd: # 홀수가 존재하면
    for i in range(len(numbers)): # 모든 값 중
        if isOdd[i] == True: # 홀수를 확인해서
            result *= numbers[i] # 홀수면 곱한다

else: # 모두 다 짝수면
    for i in numbers: # 모든 값을
        result *= i # 그냥 곱한다

print(result) # 결과를 출력한다.

선수과목 (BOJ 14567)

선수과목이라는 문제의 제목을 보자마자… 위상 정렬이 생각났다..
지난주에 들은 위상정렬의 대표 예시가 선수과목이었기 때문….
한 학기의 과목 수 제한은 없으며, 매학기 개설되므로 완벽하게 위상정렬 문제라고 할 수 있다.
내용을 정리하자면 다음과 같다.
입력으로 전체 과목수, 선수 과목 조건의 수가 우선 주어진다.
ex) 3 2 $\rightarrow$ 전체 과목수 = 3, 선수 과목 조건의 수 = 2
그 다음줄부터 선수 과목 조건이 순차적으로 주어집니다. (선수 과목 조건의 수만큼)
ex) 2 3 $\rightarrow$ 2번을 들어야만 3번을 들을 수 있다는 의미 (2 $\rightarrow$ 3 방향 그래프)
최종 출력으로 각 과목을 몇 번째 학기에 들을 수 있는지 공백으로 구분하여 출력

선수과목 풀이

위상 정렬 문제이므로 위상 정렬 방법을 똑같이 적용하면 된다.
추가할 사항이라면, 몇 번째 학기에 들을 수 있는지 적어야하므로, 이전 선수 과목이 몇 번째 학기에 듣는 과목인지에 따라, 이에 대한 내용을 저장하는 부분도 필요하다.
그냥 python의 input()함수를 사용하였더니 시간 초과가 떠서, sys.stdin.readline을 사용하였더니 문제가 해결 되었다.

N개의 과목과 M개의 조건을 받으면서 Edge Table과 진입차수 Table을 업데이트한다.
진입차수 Table을 확인하여 진입차수가 0인 과목을 Queue에 넣으면서, 1학기로 표시한다.
아래의 내용을 Queue에 값이 없을 때까지 반복한다.
- Queue에서 값을 하나 꺼낸다.
- 해당 과목에서 연결되는 다른 과목의 진입 차수를 1 줄인다.
- 줄어든 진입 차수가 0이면 Queue에 넣으면서, 과목의 학기 수 + 1 학기로 처리한다.
완료되면 학기 수가 저장된 Table을 출력한다.

from collections import deque # Queue 사용을 위한 deque
import sys # 입력을 빠르게 받을 수 있는 sys.stdin.readline을 사용하기 위한 sys

input = sys.stdin.readline # input함수를 sys.stdin.readline으로 동작하게 하기

N, M = map(int, input().split()) # 전체 과목 수 및 선수 과목 조건수를 N, M에 받는다

Edges = [[] for _ in range(N + 1)] # 전체 Edge Table 초기화

indegree = [0] * (N + 1) # 진입 차수 Table 초기화

for i in range(M): # 모든 조건을 확인하여
    start, target = map(int, input().split()) # 선수과목(start), 과목(target)
    Edges[start].append(target) # 선수과목(start)의 그래프에 과목(target)을 넣는다
    indegree[target] += 1 # 해당 과목(target)의 진입차수를 +1을 한다

q = deque() 
result = [0] * (N + 1) # 해당 과목의 들을 수 있는 학기를 입력하기 위한 Table

for i in range(1, N + 1): # 전체 과목을 확인하여 진입차수가 0인 과목을 Queue에 넣기
    if indegree[i] == 0:
        q.append(i)
        result[i] = 1

while q: # Queue에 값이 없을 때까지 진행
    now = q.popleft() # Queue에서 값을 하나 꺼내서
    for i in Edges[now]: # 해당 과목을 선수과목으로 하는 과목들의
        indegree[i] -= 1 # 진입차수를 1을 줄이고
        if indegree[i] == 0: # 진입차수가 0이 되면
            q.append(i) # 그 과목도 Queue에 넣는다
            result[i] = result[now] + 1 # 그리고 그 과목의 최소 학기는 선수 과목의 학기 + 1 로 한다

for i in range(1, len(result)):
    print(result[i], end=' ') # 전체 과목을 듣기 위한 최소 학기 수를 출력한다.

Review

최근에 수업들은 학생이 SAFFY 시험을 보고 왔다고 해서 어떠했냐고 물었더니…
1번 문제는 코딩을 좀 할 줄 아는지 묻는 문제 (홀짝 칵테일과 유사)
2번 문제는 알고리즘은 좀 풀 줄 아는지 묻는 문제 (선수 과목과 유사)
라고 해서 두 문제에 대해 한 번 리뷰를 진행해보았다.
다행히… SAFFY는 크게 고민 안하고 풀 수 있는 문제라 참 다행…
지난 주에 위상 정렬 강의를 보고 정리했던 것 때문에 나름 쉽게 풀었던 것 같다.
다른 기출도 괜찮으면 정리해보겠습니다.

2022년도 SAFFY 8기 코딩 테스트 유사 문제

Problem

Table of Contents

홀짝 칵테일 (BOJ 21312)

홀짝 칵테일 풀이

선수과목 (BOJ 14567)

선수과목 풀이

Review

comments