컴공생 누르지 마세요! 컴공생 울어요.

2019 카카오 기출 - 무지의 먹방 라이브 입출력 예시 소스코드 모든 음식을 시간 기준으로 정렬한 뒤, 시간이 적게 걸리는 음식부터 제거해 나가는 방식 우선순위 큐 이용 import heapq def solution(food_times, k): # 전체 음식을 먹는 시간보다 k가 크거나 같으면 -1 if sum(food_times)

이코테 p.312 곱하기 혹은 더하기 주어진 문자열의 각 자릿수에 더하기 혹은 곱하기 연산을 하여 만들 수 있는 최댓값 구하기 입력 예시 (1) 02984 출력 예시 (1) 576 입력 예시 (2) 02084 출력 예시 (2) 64 소스코드 피연산자 중 하나가 0 or 1이면 더하기 연산이 유리하고, 그 외에는 곱하기 연산이 유리함 # 입력받기 s = input() array = [] # 문자열을 리스트로 변환 for i in range(len(s)): array.append(int(s[i])) result = array[0] # 최종 결과값 for i in range(1, len(array)): # 피연산자 중 하나가 1보다 작은 경우 더하기 연산 if result

이코테 p.311 모험가 길드 입력 예시 5 2 3 1 2 2 출력 예시 2 소스코드 그룹 수를 최대화하려면 그룹 내 인원을 최소화해야 함 공포도를 오름차순으로 정렬한 후, 가장 작은 공포도를 가진 사람부터 그룹 구성 현재의 공포도만큼 그룹에 사람 추가 현재 그룹의 사람 수가 현재의 공포도보다 크거나 같아지면 그룹 수 +1 & 그룹 초기화 # 입력 받기 n = int(input()) array = list(map(int, input().split())) # 오름차순으로 정렬 array.sort() result = 0 # 총 그룹 수 count = 0 # 현재 그룹의 사람 수 for fear in result: count += 1 # 그룹에 사람 1명 추가 if count >= fear: # 현재 그룹의 ..

이코테 p.303 실전 문제 - 커리 큘럼 입력 예시 5 10 -1 10 1 -1 4 1 -1 4 3 1 -1 3 3 -1 출력 예시 10 20 14 18 17 내 소스코드 cost_array 리스트 cost_array[i]는 i번 강의를 듣는 데 걸리는 시간 graph 리스트 graph[1] = [0, 2, 3, 4]라면 1번 노드는 2, 3, 4번 노드와 연결되어 있음을 의미 0번 인덱스의 요소는 건너뜀 위상 정렬 알고리즘 사용 indegree가 0이 될 때 q에 삽입 & result 값 갱신 result[다음 노드] = max(result[다음 노드], result[현재 노드] + cost_array[다음 노드]) 주의할 점) 아래 소스코드의 result = cost_array처럼 단순히 대입 연산..

이코테 p.300 실전 문제 - 도시 분할 계획 입력 예시 7 12 1 2 3 1 3 2 3 2 1 2 5 2 3 4 4 7 3 6 5 1 5 1 6 2 6 4 1 6 5 3 4 5 3 6 7 4 출력 예시 8 내 소스코드 크루스칼 알고리즘으로 최소 신장 트리를 구한 후, 최소 신장 트리의 간선 중 비용이 가장 큰 간선 제거 # 루트 노드를 찾는 함수 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # 두 노드의 합집합 연산 정의 def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(..

이코테 p.298 실전 문제 - 팀 결성 입력 예시 7 8 0 1 3 1 1 7 0 7 6 1 7 1 0 3 7 0 4 2 0 1 1 1 1 1 출력 예시 NO NO YES 내 소스코드 서로소 집합 알고리즘의 합집합 연산과 찾기 연산 적용 N과 M의 범위가 모두 최대 100,000이므로 경로 압축 방식의 서로소 집합 자료구조를 이용하여 시간 복잡도를 개선함 a와 b 각각에 대한 찾기 연산의 수행 결과가 같은지 비교하여 그 결과를 result에 저장 후 출력 # 같은 팀 여부 확인 연산 정의 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # 팀 합치기 연산 정의 ..

위상 정렬 정렬 알고리즘의 일종 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용 ex) 선수과목을 고려한 학습 순서 결정 그래프에서 선후 관계가 있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있음 진입차수 (indegree) 특정한 노드로 들어오는 간선의 개수 위상 정렬 알고리즘 진입차수가 0인 노드를 큐에 넣는다 큐가 빌 때까지 다음 과정을 반복한다 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다 새롭게 진입차수가 0이 된 노드를 큐에 넣는다 위 과정을 반복하면서 큐에서 빠져나간 노드를 순서대로 출력하면, 그것이 바로 위상 정렬 수행 결과가 됨 모든 원소를 방문..

신장 트리 신장트리: 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건임 어떠한 그래프에서 신장 트리는 여러 개 존재할 수 있음 크루스칼 알고리즘 가능한 한 최소한의 비용으로 신장 트리를 찾을 때 사용 ex) N개의 도시가 존재할 때, 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우, 최소한의 비용으로 모든 도시를 연결할 때 사용 최소 신장 트리 알고리즘 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘 크루스칼 알고리즘이 대표적인 최소 신장 트리 알고리즘 그리디 알고리즘의 일종 모든 간선에 대하여 정렬을 수행한 뒤, 가장 ..