푸으름

✏️ 문제 링크 https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 세그먼트 트리의 한 종류인 느리게 갱신되는 세그먼트 트리를 구현하는 문제입니다. 구간에다가 특정 값을 더하게 되는 연산을 하게되면 일반적인 세그먼트 트리로 구현하게 되면 시간초과가 발생하게 됩니다. 이를 해결하기 위해 만들어진게 느리게 갱신되는 세그먼트 트리입니다. 특정 구간에 값을 ..

✏️ 문제 링크 https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 최소 신장 트리를 구현하는 문제입니다. 기본적인 MST구현 알고리즘에서 조건을 1가지만 추가하면 됩니다. 기존의 MST는 부모 노드가 다르다면 Union을 하지만, 위 문제는 남초대학교와 여초대학교라는 조건이 있습니다. 따라서, Union을 하기 위해서는 두 노드의 학교 성별이 달라야 하고 부모 노드가 달라야..

✏️ 문제 링크 https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 최소 신장 트리 구현에 관한 문제입니다. 가장 먼저 MST구현 반복문의 횟수 설정입니다. 원래 기존의 MST는 사용한 에지의 개수가 정점의 개수 - 1만큼 될 때가지반복문을 돌려야 하지만 위 문제의 경우에는 연결하지 않아도 되는 발전소의 개수가 주어지기 때문에 에지의 개수가 N-K가 될 때까지만 반복문을 돌..

✏️ 문제 링크https://www.acmicpc.net/problem/1738 1738번: 골목길첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 주어www.acmicpc.net ✏️ 문제 설명  ✏️ 문제 풀이벨만-포드 알고리즘을 이용하는 문제입니다. 처음에는 문제를 대충 읽고 벨만-포드를 돌린 후 음수 사이클의 여부에 따라서 정답을 출력하려고 했으나 문제를 다시 읽어보니 금품의 양이 최대가 되어야 한다는 점을 깨달았습니다. 그래서 방식을 고민하다가 입력받는 가중치를 음의 부호를 붙여서 입력받는 방식을 생각했습니다. 이렇게 하게 되..