목록전체 글 (60)

쫑쫑이의 블로그

백준 1717 집합의 표현 Java [분리집합, Union find]

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 서로 같은 집합에 속해 있는지 확인하기 위해 모든 원소 값들을 자기 자신을 부모로 설정한다 입력값의 가장 첫 값이 0이면 a의 부모에 b의 부모를 넣거나 b의 부모에 a의 부모를 넣는다 (둘 중에 한가지만 일관되게 사용) 1이면 a의 부모와 b의 부모가 같은지 확인한다 여기서 설명하는 부모는 가장 최상위에 자기 자신을 부모로 하는 원소이다 import ja..
알고리즘/백준 2022. 11. 22. 01:44
백준 10986 나머지 합 Java [누적합]

https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 규칙만 빨리 찾으면 쉬운(?) 문제지만, 규칙 찾는게 영 쉽진 않다 처음에 생각한 방식은 연속된 부분 구간의 합이니까 누적합을 생각해서 구해보았다 예제를 기준으로 1 3 6 7 9 이다 누적합을 구한 후 반복문으로 하나씩 탐색해가면서 앞에서 하나씩 빼가면서 나누어 떨어지는지 확인해보았다 이 방법대로하면 N^2의 시간복잡도로 시간초과이다 그래도 방법을..
알고리즘/백준 2022. 11. 21. 01:09
백준 1655 가운데를 말해요 Java [우선순위 큐]

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 가운데 값을 기준으로 왼쪽에 최대 힙, 오른쪽에 최소 힙을 만들어주고 두 힙의 사이즈가 같거나 왼쪽이 1 더 크게 만들어서 왼쪽의 peek 값을 출력값에 넣어준다 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { Buffe..
알고리즘/백준 2022. 11. 20. 00:44
백준 17425 약수의 합 Java [에라토스테네스의 체, 누적합]

https://www.acmicpc.net/problem/17425 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 자신보다 작은 수들의 모든 약수들의 합을 구해야하므로 누적합으로 계산한다 약수 계산은 에라토스테네의 체를 사용하여 작은 수부터 시작하여 배수들을 찾아서 값을 더해준다 에라토스테네스의 체.gif 간단한 예시로 1부터 시작해서 일반화를 하면 배열[1]에 배열[0] 더하기, 1의 배수에 모두 1추가 배열[2]에 배열[1] 더하기, 2의 배수에 모두..
알고리즘/백준 2022. 11. 19. 03:48
백준 7579 앱 Java [DP, 배낭문제]

https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 바이트를 확보하라는 문제라서 바이트를 가지고 dp를 만들어볼까 했는데 범위가 10,000,000까지라서 100 x 10,000,000 시간복잡도도 문제인데 공간복잡도도 문제가 생길 정도로 크다 (int 기준 약 4GB) 그래서 비용을 이용하여 dp로 풀기로했다 범위가 100까지라서 100 x 100 1만이면 여유있게 풀 수 있다 바이트와 비용을 입력 받은 후 반복문으로 비용이 0이면 무조건 종료시키고 확..
알고리즘/백준 2022. 11. 17. 01:03
백준 2467 용액 Java [투포인터]

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 입력값이 오름차순으로 정렬된 배열이므로, 왼쪽 끝과 오른쪽 끝값을 조건에 따라 하나씩 늘리거나 줄여가면서 0과 가장 가까운 값을 저장하고 출력한다 음수도 나올 수 있으니까 더했을 때 음수면 왼쪽값을 늘리고, 양수면 오른쪽 값을 줄인다 import java.awt.*; import java.io.*; import java.util.*; public class Main { public stati..
알고리즘/백준 2022. 11. 16. 01:50
이전 Prev 1 2 3 4 5 6 7 ··· 10 Next 다음