이코테 복습

그래프 이론

커리큘럼

• n개의 강의(1~n번), 동시에 강의 수강 가능
• 선수 강의가 필요한 경우 선수 강의를 먼저 들어야 수강 가능
• 모두 수강까지 걸리는 최소시간을 출력

풀이특징

• 위상 정렬(topology sort) 알고리즘
• 노드별 누적시간을 저장: q에 넣을 때 target = max(target, now + cost) 로직이 필요

from collections import deque
import copy

n = int(input())
graph = [[] for _ in range(n)]
indegree = [0] * n
time = [0] * n

for i in range(n):
    inputs = list(map(int, input().split()))
    time[i] = inputs[0]
    for j in inputs[1:-1]:
        graph[j-1].append(i)
        indegree[i] += 1
        
def topology_sort():
    q = deque()
    result = copy.deepcopy(time)
    
    for i in range(n):
        if indegree[i] == 0:
            q.append(i)
    
    while q:
        now = q.popleft()
        
        for node in graph[now]:
            result[node] = max(result[node], result[now] + time[node])
            indegree[node] -= 1
            
            if indegree[node] == 0:
                q.append(node)
                
    return result
                
result = topology_sort()
for t in result:
    print(t)

이코테 유형별 기출문제

그리디

모험가 길드

풀이특징

• 오름차순 정렬
• 인원수 합 >= 현재 공포도 -> 그룹 += 1

# 떠날 수 있는 그룹 수의 최댓값
n = int(input())
array = list(map(int, input().split()))
array.sort()

result = 0 # 총 그룹의 수
count = 0 # 현재 그룹에 포함된 모험가의 수
for i in array:
    count += 1
    if count >= i:
        result += 1
        count = 0

print(result)

곱하기 혹은 더하기

풀이특징

• 0, 1 인 경우 +, 나머지의 경우 *

# 만들어질 수 있는 가장 큰 수
nums = input()
result = int(nums[0])
for i in range(1, len(nums)):
    num = int(nums[i])
    if result <= 1 or num <= 1:
        result += num
    else:
        result *= num

print(result)