목록알고리즘/백준 (45)

쫑쫑이의 블로그

백준 12738 가장 긴 증가하는 부분 수열 3 Java [LIS]

https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 이전에 푼 가장 긴 증가하는 부분 수열 2 문제보다 수열 A를 이루는 숫자가 범위가 더 크고, 음수도 들어온다 푸는 방법은 다르지 않지만 이번에는 Arrays.binarySearch 메서드를 사용해서 풀이를 해봤다 Arrays.binarySearch 메서드 값은 일치하는 숫자가 있으면 해당 인덱스를 반환하고, 일치하는 숫자가 없으면 절대값으로 바꾸고 -1 해주면 들어..
알고리즘/백준 2022. 10. 22. 09:58
백준 12015 가장 긴 증가하는 부분 수열 2 Java [LIS]

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net N이 1000000까지니까 NlogN 안으로 풀어야한다 예제 A 10 20 10 30 20 50 D 1 2 1 3 2 4 예제는 중복되는 숫자가 있어서 규칙을 찾기가 힘들다 예제 2 A 11 20 10 30 19 50 D 1 2 1 3 2 4 거리배열을 만들어서 배열 가장 끝값보다 크면 배열에 추가해준다 배열보다 작으면 이진탐색으로 작은값 중에 가장 큰값 찾아서 그 다음 인덱스 값과 교체해준다 i..
알고리즘/백준 2022. 10. 22. 03:40
백준 1644 소수의 연속합 Java [에라토스테네스의 체]

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 소수를 구하는 방법은 2가지 있다 1. 숫자를 증가시켜가면서 소수로 나눠지는지 확인하기 2. 에라토스테네스의 체 사용하기 숫자가 충분히 크니까 에라토스테네스의 체를 사용하는게 시간복잡도 측면에서 이득 에라토스테네스의 체는 2부터 시작해서 2를 제외한 2의 배수를 다 소수가 아니라고 체크하고 3을 제외한 3의 배수를 다 소수가 아니라고 체크한다 숫자를 증가시켜가면서 체크안된 숫자(소수)의 배수를 소수가 아니라고 체크하는 과정을 반복한다 그리고 연속된 수의 합이 N이면 count 해준다 이 방법은 숫자를 하나씩 증가시켜..
알고리즘/백준 2022. 10. 22. 01:50
백준 1504 특정한 최단 경로 Java [다익스트라]

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라로 1 -> v1 -> v2 -> N 과 1 -> v2 -> v1 -> N 중 가능한 짧은 경로를 찾아 출력하면 된다 import java.io.*; import java.util.*; public class Main { static int N; static List[] nodes; static final int INF = 700_000_000..
알고리즘/백준 2022. 10. 20. 23:17
백준 1916 최소비용 구하기 Java [다익스트라]

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 알고리즘을 사용해서 풀면 된다 끝까지 돌 필요 없이 도착 도시에 최초로 방문할 때 break해준다 import java.io.*; import java.util.*; public class Main { static final int INF = 200_000_000; public static void main(String[] args) throws IOE..
알고리즘/백준 2022. 10. 20. 01:43
백준 11660 구간 합 구하기 5 Java [DP, 누적합]

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net x1 부터 x2까지 하나씩 다 더해서 구했을 때 (1,1)부터 (1024, 1024)까지 합을 구하는 것을 100000번 반복하면 시간복잡도가... 터진다 - 풀이 - 1 2 3 4 5 6 7 8 9 10 위와 같은 행이 있을 때 각 자리에 1부터 해당 자리까지 합을 구한다 1 3 6 10 15 21 28 36 45 55 4부터 10까지 합을 구하고 싶으..
알고리즘/백준 2022. 10. 19. 00:36
이전 Prev 1 ··· 3 4 5 6 7 8 Next 다음