Dev On The Coffee Dev On The Coffee

# 문제 내 풀이 import sys input = sys.stdin.readline limit_number = 100000 sys.setrecursionlimit(limit_number) # 재귀 제한을 여유 있게 해제 # 특정 원소가 속한 집합을 찾기 (Find 연산) def find_parent(parent, x): # 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # 두 원소가 속한 집합을 합치기 (Union 연산) def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, ..

# 서로소 집합 (Disjoint Sets) 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 예를 들어, {1, 2}, {3, 4}는 서로소 관계이지만, {1, 2}, {2, 3}은 2라는 공통된 원소가 존재하므로 서로소 관계가 아니다. # 서로소 집합 자료구조 (Union Find 자료구조) 서로소 집합 자료구조(Union Find 자료구조)는 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 서로소 집합 자료구조에는 두 가지 연산이 존재하는데, 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 합집합(Union) 연산과 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 찾기(Find) 연산이 그것이다. # 서로소 집합 자료구조의 동작 과정 1. 기본 동작 과정 (..

# 문제 모범 답안 - 벨만 포드 알고리즘 공부 import sys input = sys.stdin.readline INF = int(1e9) # 무한을 의미하는 값으로 10억 설정 def bf(start): # 시작 노드에 대해서 초기화 dist[start] = 0 # 전체 n번의 라운드(round)를 반복 for i in range(n): # 매 반복마다 "모든 간선"을 확인 for j in range(m): cur = edges[j][0] next_node = edges[j][1] cost = edges[j][2] # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우 if dist[cur] != INF and dist[next_node] > dist[cur] + cost: dist[ne..

# 문제 내 풀이 n, m = map(int, input().split()) nums = list(map(int, input().split())) # 카드 숫자 입력 받기 result = 0 # M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합 # 전체 카드 숫자 중 3개를 뽑는 모든 경우의 수를 완전 탐색해 비교 for i in range(n - 2): for j in range(i + 1, n - 1): for k in range(j + 1, n): pick_sum = nums[i] + nums[j] + nums[k] if result < pick_sum and pick_sum

# 문제 내 풀이 - 문제 풀이 실패, 수정 답안 n, k = map(int, input().split()) items = [(0, 0)] # 물품 정보 입력 받기 for i in range(n): w, v = map(int, input().split()) items.append((w, v)) # 2차원 DP 테이블 생성 및 초기화 dp = [[0] * (k + 1) for _ in range(n + 1)] # 냅색 알고리즘 수행 for i in range(1, n + 1): # 물품 중 하나를 선택 w = items[i][0] v = items[i][1] # 1 ~ k까지의 무게에 대해 다이나믹 프로그래밍 진행 for j in range(1, k + 1): # 선택한 물품의 무게가 가방 허용 무게를 넘..

# 문제 내 풀이 - 문제 풀이 실패, 수정 답안 n = int(input()) nums = [-1001] # 인덱스를 맞추기 위해 가장 작은 수를 하나 삽입 nums = nums + list(map(int, input().split())) # 점화식을 기록하는 테이블을 만들고 초기화 n_sum = [-1001] * 100001 n_sum[1] = nums[1] # 왼쪽부터 차례로 합을 더해나가면서 새로운 수와 비교 for i in range(2, n + 1): n_sum[i] = max(n_sum[i - 1] + nums[i], nums[i]) # 결과 출력 print(max(n_sum)) 생각해볼 점 정석적인 DP 테이블만 생각했는데, 약간 변형하여 점화식을 기록해나가는 방법도 있음을 알았다. 생각을..

# Deadlock 1. Deadlock이란? 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태를 말한다. 여기서 자원이란 하드웨어와 소프트웨어 등을 모두 포함하는 개념이며, 이러한 자원을 사용하는 절차로는 Request, Allocate, Use, Release가 있다. 2. Deadlock이 발생하는 4가지 조건 Deadlock이 발생하려면 아래의 4가지 조건을 모두 만족해야 한다. - Mutual Exclusion : 매 순간 하나의 프로세스만이 자원을 사용한다. - No Preemption : 프로세스는 자원을 강제로 빼앗기지 않고 스스로 내어 놓는다. - Hold and wait : 자원을 가진 프로세스가 다른 자원을 기다릴 때, 보유 자원을 놓지 않고 계속 가지고 있는다. - ..

# 벨만 포드 알고리즘 (Bellman-Ford Algorithm) 1. 벨만 포드 알고리즘 개요 벨만 포드 알고리즘(Bellman-Ford Algorithm)은 다익스트라 알고리즘과 거의 유사하다. 다만, 다익스트라 알고리즘과 달리 벨만 포드 알고리즘은 음의 값을 가지는 간선을 포함하여 알고리즘을 수행할 수 있다는 점이 큰 차이점이다. 위와 같이 5번 노드에서 2번 노드로 가는 간선의 비용이 -2인 그래프가 있다. 이 경우, 음의 간선이 존재하지만 얼마든지 오른쪽 테이블처럼 최소 비용을 계산해낼 수 있다. 그러나 음의 간선의 순환이 포함되어 있는 경우 최소 비용을 계산하는데 어려움이 생길 수 있다. 위 그래프는 음의 간선 비용이 -4인데 이 값이 상당히 작기 때문에 '3번 노드 -> 5번 노드 -> 2..