Algorithm (PS)/백준18 [백준 5568] 구간 합 구하기 4 (Java) [누적합] 문제 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 알고리즘 누적합 풀이 1. 1~N 각각 자기 자신까지의 합을 구한다 2. from~to까지의 누적합을 구한다. (aSum[to] - aSum[from-1] 코드 package com.company; import java.io.*; import java.util.StringTokenizer; public class Test_Accumulate_Sum { public st.. 2023. 8. 8. [백준 5568] 카드 놓기 (순열+Hash) 문제 https://www.acmicpc.net/problem/5568 5568번: 카드 놓기 예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net 알고리즘 Hash + 순열 풀이 1. 순열을 통해 카드를 선택할 수 있는 모든 경우의 수를 파악 2. 선택했던 카드를 또 선택하지 못하게 visit[] 배열을 통해 중복 체크 3. K개를 뽑았다면 Hash를 통해 만든 카드 경우의수를 체크 코드 package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayL.. 2023. 8. 8. [백준] 11404 플로이드 (Java) [FloydWashal] 문제 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 알고리즘 플로이드 와샬 풀이 전형적인 플로이드 와샬 알고리즘이다. "시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다." 조건이 있기 때문에, input 값 입력시 dist[from][to] = Math.min(dist[from][to], w); 처리를 해준다. 이것만 주의하면 되며, 플로이드 와샬을 통해 문제를 풀면 된다. 코드 package com.company; import.. 2023. 7. 28. [백준] 2252. 줄세우기(Java) [위상정렬] 문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 알고리즘 위상정렬 풀이 1. 진입 차수가 0인 정점을 큐에 삽입한다. 2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다. 3. 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입한다. 4. 큐가 빌 때 까지 2~3번 반복. 코드 package com.company; import java.io.*; import java.util.*; publi.. 2023. 7. 25. [백준] 1922 (Java) [MST 알고리즘] 문제 https://www.acmicpc.net/problem/1922 알고리즘 크루스칼 알고리즘 풀이 가중치가 짧은 순으로 정렬을 해주고 UnionFind를 통해 그래프를 연결해준다. 그 과정에서 가중치를 더하며 정답을 구한다. 코드 package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.StringTokenizer; public class Test_Cruskal { static in.. 2023. 7. 25. [백준] 1717 집합의 표현(Java) [Union-Find] 문제 https://www.acmicpc.net/problem/1717 알고리즘 Union-Find 풀이 대표적인 union-find 문제이다. parent를 얻어오는 함수, parent를 합치는 함수, parent가 동일한지 확인하는 함수를 구현한 후 입력 받는 flag에 따라 parent를 합치거나 출력한다. 코드 package com.company; import java.io.*; import java.util.StringTokenizer; public class Test_UnionFind { static int N, M; static int[] parent; public static void main(String args[]) throws IOException { BufferedReader bf .. 2023. 7. 24. 이전 1 2 3 다음