Partially Committed

https://www.acmicpc.net/problem/19622 19622번: 회의실 배정 3 서준이는 아빠로부터 N개의 회의와 하나의 회의실을 선물로 받았다. 각 회의는 시작 시간, 끝나는 시간, 회의 인원이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, www.acmicpc.net EASY~ 문제는 단순하다 회의실이 1 개 있고, n 개의 회의 정보가 주어진다. 회의 정보는 시작시간, 종료시간, 참석 인원으로 이루어져있다. 주어진 상황에서 가장 많은 인원이 회의를 참석할 수 있을 때, 그 인원의 수를 계산하면 된다. 회의 정보는 항상 시작 시간 < 종료 시간을 만족한 상태로 주어진다. 그리고 중요한 조건이 하나 있는데... K 번째 회의는 K-1, K+1 번째 회의랑만..

기업 코테에서 세그먼트 트리를 요구하는 경우는 흔치 않은 것 같지만 필요한 일이 생겨서 이참에 정리해보려고 한다.. 값이 변하지 않는 데이터가 주어졌을 때, 구간 합을 빠르게 구하는 방법은 prefix sum 을 이용하면 된다. https://www.crocus.co.kr/843 구간 합(Prefix Sum) 알고리즘 목차 1. 구간 합(Prefix Sum)이란? 2. 구간 합(Prefix Sum)이 어디에 쓰일까? 3. Prefix Sum Algorithm 4. Prefix Sum이 쓰이는 문제들 1. 구간 합(Prefix Sum)이란? 공부를 하다보면 부분 합, 구간 합의 개념이 헷갈릴 때 www.crocus.co.kr 만약, 데이터가 변한다면 Fenwick tree 를 구현해서 구간 쿼리를 효율적으..

1213번: 팰린드롬 만들기 (acmicpc.net)

1162번: 도로포장 (acmicpc.net) 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 다익스트라 + dp 이전에 **미확인 도착지 문제**를 통해 다익스트라의 기본 형태를 구현했었다. 도로포장은 다익스트라에 dp 를 곁들인 문제다 😐 문제를 간단히 요약하면, 양방향 그래프가 주어지면 1번 노드에서 N 번 노드로 최단 경로로 움직여야 한다. 이때, 좀 더 빠르게 움직이기 위해 **도로 포장** 을 k 번 수행할 수 있다. 도로 포장을 수행하면, 해당 도로의 가중치를 ..