문제 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이 init tree[node]에 넣어줄 때 하위 노드들의 곱 % MAXVAL update 리턴타입 long 업데이트 타겟 인덱스가 범위 밖일 때, return tree[node] if(start == end)일 때, tree[node] = newVal return tree[node] = 하위 노드들의 곱 % MAXVAL multiple 구간 범위가 범위 밖일 때, return 1 구간 범위가 ..
문제 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 풀이 이 문제에서는 간선과 가중치가 주어지며 이를 바탕으로 출발점(S)에서 목적점(E)까지 도달하면 된다. 한 가지 고려해야할 점은, 모든 노드를 탐색하게 되면 시간초과가 발생하기 때문에 이분탐색을 적용해야한다. 풀이 순서로는 1. 입력을 받으면서 가중치의 최댓값(r)을 찾아준다. 2. 이분탐색을 진행한다. 2-1. m(중간값)을 기준으로 dfs 탐색을 통해 목적지까지 유효한지 확인해본다. 2-2...
문제 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 풀이 bfs, dfs, MST로 푸는 방법이 다양하지만, 복습을 할겸 MST 방법으로 풀어보았습니다. MST에서는 union-find 알고리즘을 사용했습니다. 1. union-find 알고리즘으로 집합을 구성해주고 2. parents 배열을 기반으로 list 배열에 해당 친구에서 발생하는 친구비를 add 했습니다. ex) 1번 친구와 같은 집합에 속하는 친구가 1, 2, 4라면 1, 2, 4..
문제 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 풀이 제목 그대로 그래프 간선들을 연결했을 때 연결 요소의 개수가 몇 개인지 파악하는 문제 Union-find 방법과 bfs 방법으로 풀어보았다. 1) union-find 풀이 간선의 정보에 따라 a와 b가 서로 다른 집합일 경우, parents 배열을 갱신해주었음 set을 이용해 순회하며 다른 부모의 개수만 저장하였고 size를 출력했음(map으로도 가능하며 시간/공간은 거의 비슷) 2) bf..
문제 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (1 ≤ N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 www.acmicpc.net 풀이 stack을 이용해서 푸는 문제 stack 배열을 만들고 N번을 순회하면서 1) stack[a]가 비어있지 않으며 stack[a].peek() 값이 b보다 크다면 조건이 만족하지 않을 때까지 반복하며 stack[a]를 pop해준다.(동작 수행을 한 것이기 때문에 ans ++) 2) stack[a]가 비어있거나 b값이 stack[a].peek()값보다 크다면 stack[a]에 b를 push해준다.(동작 수행을 한..
문제<figure id="og_1712941140012" contenteditable="false" data-ke-type="opengraph" data-ke-align="alignCenter" data-og-type="website" data-og-title="3986번: 좋은 단어" data-og-description="이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 " data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/prob..
문제 18116번: 로봇 조립 성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의 www.acmicpc.net 풀이 쿼리에 맞게 집합을 형성하거나(I) 집합 내의 원소 개수를 출력(Q) 하는 문제 집합 형성(I): a와 b를 union 해준다.(여기서 union은 union-find의 메서드와 동일) 원소의 개수 출력(Q)을 위해서는 cnt배열(초기화 1)을 만들어 union 과정에서 값을 더해주면 된다. 출력 값은 cnt[find(찾는 값)] 코드 import java.io.*; import java.util.*; public class Main { static int..
문제 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 풀이 최소 스패닝 트리(MST)에 기반하여 쿼리에 따라 연산을 해주는 문제 0으로 시작하는 연산은 a와 b의 집합을 합쳐줌 1로 시작하는 연산은 a와 b가 같은 집합에 속하는지 확인(같다면 "YES" 다르다면 "NO") 코드 import java.io.*; import java.util.*; public class Main { static int N; static int[] parents; public static vo..
