반응형 백준알고리즘68 [백준] 11660번 - 구간 합 구하기5(△) https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 1. 구간합을 구하기 위해서 가로 기준으로 더해 나가는 합산 테이블 하나, 세로 기준으로 더해나간 합산 테이블 하나해서 총 2개를 준비한다. 2. 2차원 배열의 구간합 배열을 어떤 식으로 구성하느냐가 이 문제를 푸는 열쇠이다. * 점화식 D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j] 3. DP테이블(구.. 2022. 12. 26. [백준] 11659번 - 구간 합 구하기 4(Java)(○) https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 1. 구간합 구하는 공식을 사용하면 된다. 2. 입력합수에서 수를 입력 받을 때마다 누적합을 구해서 구간합 배열을 미리 만들자. * 합 배열 공식 S[i] = S[i-1] + A[i] * 구간 합 공식 A[i] ~ A[j] 사이의 합을 구하려면 S[j] - S[i-1] import java.io.BufferedReader; import java.io.InputStreamRe.. 2022. 12. 26. [백준] 2018번 - 수들의 합 5(Java)(◎) https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 1. 투포인터 알고리즘을 사용한다. 2. 1 ~ N까지의 정수를 늘어놓고 처음부터 한 수를 고정한다음, 그 다음 수부터 하나씩 더해나간다. 3. sum == N이면 count++ 한다음 그 다음수를 고정하고 다시 하나씩 더해 나간다. import java.io.BufferedReader; import java.io.InputStreamReader; import.. 2022. 12. 23. [백준] 1525번 - 퍼즐 (Java)(△) https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 1. 숫자가 이동하는 것이 아니라 0번이 이동하는 것으로 바꿔서 생각하자. 2. 0의 좌표를 이동하면 그 위치의 숫자를 원래 0의 위치로 옮긴다. 3. 메인함수에서 0의 위치를 찾아서 DFS()를 호출한다. 4. DFS 함수 구성 (int count, int x, int y) - count : 0의 이동 횟수 - x, y : 0이 이동한 위치 - 종료조건 : 0이 (2, 2)의 위치로 이동 - 퍼즐의 유효성 검사를 수행하는 함수를 실행 - 재귀호출은 0을 하나 이동 시키고 .. 2022. 12. 20. [백준] 6603번 - 로또 (Java) 1. 줄의 첫 숫자가 N이고, 뒤부터 로또에 사용될 정수들이 배열이 입력된다. 2. 중복방문을 허용하지 않는다. (방문배열 사용) 3. 순서가 바꾸어도 동일 조합으로 인정한다. (i=start부터 시작) 4. 종료조건은 level == N이다. import java.util.Scanner; import java.util.Arrays; import java.lang.StringBuilder; import java.util.HashSet; public class Main { static int N, S; static int sum = 0, count = 0; static int A[]; static int Ans[]; static boolean visited[]; void DFS(int start, int .. 2022. 12. 11. [백준] 1182번 - 부분수열의 합 (Java) https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 1. 종료조건은 tree level이 N까지 진행될 때이다. 2. 합이 S가 되면 count +1을 한다. - 합이 S가 되더라도 탐색은 계속 진행한다. 3. 모든 탐색이 끝나면 count를 출력한다. 4. 부분집합을 구하는 것이기 때문에 지금 수(A[i])를 더하거나 더하지 않는 수, 2가지 경우의 수로 나뉜다. - 현재 수(A[level])를 더하고 다음 l.. 2022. 12. 11. [백준] 15666번 - N과 M(12) (Java) https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 중복방문 허용함. (방문배열 사용X) 2. 순서다른 조합 허용안함. (i = start부터 시작) 3. 중복 조합 허용안함. (HashSet으로 포함 확인 후 제거) import java.util.Scanner; import java.util.Arrays; import java.lang.StringBuilder; import java.util.HashSet; public class Mai.. 2022. 12. 10. [백준] 15665번 - N과 M(11) (Java) https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 중복방문 허용함 (방문배열 사용X) 2. 순서다른 조합 허용함 (i = 0 부터 시작) 3. 중복 조합 허용안함 (HashSet으로 체크 후 제거) import java.util.Scanner; import java.util.Arrays; import java.lang.StringBuilder; import java.util.HashSet; public class Main { static.. 2022. 12. 10. [백준] 15664번 - N과 M(10) (Java) https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 입력받은 정수배열만 사용해야 함. 2. 중복수열 허용안함 (방문배열 사용함) 3. 순서 바뀌면 다른 조합으로 인정안함(i = start 부터 시작) 4. 입력 배열 중 같은 숫자가 있으면 중복 방문은 아니지만 같은 조합이므로 한번만 출력해야 함. - HashSet을 사용해서 중복 문자열이 있으면 머지하지 않고 스킵하도록 구현함. import java.util.Scanner; import .. 2022. 12. 10. 이전 1 2 3 4 5 6 ··· 8 다음 반응형
