본문 바로가기
반응형

분류 전체보기1348

[BOJ] 백준 10211 Maximum Subarray 출처: https://www.acmicpc.net/problem/10211 Input 2 5 1 2 3 4 5 5 2 1 -2 3 -5 Output 15 4 연속된 부분 합 (연속합) 내용 참고 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = Integer.parseInt(sc.next()); while(T-- > 0) { int N = Integer.parseInt(sc.next());; int[] arr = new int[N]; for(int i=0; i 2021. 2. 20.
연속된 부분 합(연속합) - 1 (완전 탐색) ※ 구간합을 구하는 효율적인 방법 연속된 부분 합(연속합) - 1 (완전 탐색) 연속된 부분 합(연속합) - 2 (Prefix Sum) 연속된 부분 합(연속합) - 3 (DP) [구간합] Sum of sub-matrix (2D Array) 완전 탐색 Q) 아래와 같이 배열이 주어질 때 특정 연속 구간의 합 중 최대값을 구하시오. if) 구간의 길이가 5 일 때, 구간의 최대합은? 길이 6을 가지는 시작 지점(start) ~ 끝 지점(end)까지 합을 매번 더해서 구할 수 있습니다. (Sliding Window 혹은 Inchworm Algorithm) 직관적이지만 시간복잡도가 좋다고 할 수는 없습니다. [O(N3) 코드] int ans = 0; int N, A[LM]; void findPartialSum(.. 2021. 2. 20.
[BOJ] 백준 1914 하노이 탑 출처: https://www.acmicpc.net/problem/1914 Input 3 Output 7 1 3 1 2 3 2 1 3 2 1 2 3 1 3 Sample Output을 분석하면 어떻게 옮겨지는지 알 수 있습니다. 이를 재귀적으로 해결할 수 있습니다. 1. 제일 큰 원반을 제외한 N-1개의 원반들을 A 기둥에서 B 기둥으로 이동시킵니다. 2. 제일 큰 원반 한개를 A 기둥에서 C 기둥으로 이동시킵니다. 3. 1번에서 옮겨진 원반들을 B기둥에서 C 기둥으로 이동시킵니다. : 시작점과 도착점이 있고, 도달하기 위한 중간점을 이용해야만 합니다. 문제조건상 N > 20인 경우는 원반들이 옮겨지는 횟수만 구하면 되는데 결국 (2N - 1)을 출력하면 됩니다. ← 수학적으로 증명 하지만 2100은 lon.. 2021. 2. 20.
[BOJ] 백준 1159 농구 경기 출처: https://www.acmicpc.net/problem/1159 Input 18 babic keksic boric bukic sarmic balic kruzic hrenovkic beslic boksic krafnic pecivic klavirkovic kukumaric sunkic kolacic kovacic prijestolonasljednikovi Output bk 만약 선수 3명의 이름이 아래와 같을 때, cnt[name[0] - 97]++; 처리 → babic, keksic, boric cnt['b' - 97] = 2 cnt['k' - 97] = 1 → cnt[] ≥ 5 인 경우 출전가능한 첫 글자에 해당됩니다. #include int N, cnt[26], idx, i; char nam.. 2021. 2. 20.
[BOJ] 백준 1004 어린 왕자 출처: https://www.acmicpc.net/problem/1004 Input 2 -5 1 12 1 7 1 1 8 -3 -1 1 2 2 2 5 5 1 -4 5 1 12 1 1 12 1 2 -5 1 5 1 1 0 0 2 Output 3 0 문제조건에서 원의 경계가 맞닿거나 교차하는 경우는 주어지지 않습니다. 두 점의 상태는 아래의 경우로 나눌 수 있습니다. ① 두 개 모두 원 안에 있는 경우 → +0 : 원의 교차 없이 두 점을 이을 수 있습니다. ② 두 개 모두 원 밖에 있는 경우 → +0 : 원의 바깝 부분을 돌아가서 교차 없이 두 점을 이을 수 있습니다. ③ 둘 중 한 개만 원 안에 있는 경우 → +1 : 하나의 원을 교차할 수 밖에 없습니다. [빨간색 점을 기준] ▶ d1 < r1 이므로, 원.. 2021. 2. 20.
[BOJ] 백준 2042 구간 합 구하기 출처: https://www.acmicpc.net/problem/2042 Input Output 구간합을 처리하는 코드는 아래와 같이 구현할 수 있습니다. 하지만 배열 원소값을 변경과 구간 합을 구하는 것이 여러번 일어나기 때문에 이에 대한 효율적인 처리가 필요합니다. 세그먼트 트리(Segment Tree) #include #include #include typedef long long ll; using namespace std; int N, M, K; vector arr, tree; vector cmdList; void input() { int i, a, b, c; cin >> N >> M >> K; for (i = 0; i > a; arr.push_back(a); } f.. 2021. 2. 20.
[BOJ] 백준 10989 수 정렬하기 3 출처: https://www.acmicpc.net/problem/10989 Input 10 5 2 3 1 4 2 3 5 1 7 Output 1 1 2 2 3 3 4 5 5 7 N이 크기 때문에 제한시간을 만족시키기 어렵다. 정렬기법을 사용하지 않고 배열 원소 index 이용 중복되어 입력될 수 있으므로 원소값은 중복 개수 할당. ex) arr[5] = 3 / arr[8] = 2 라면 출력결과는 다음과 같다. ▶ 5 5 5 8 8 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { publi.. 2021. 2. 20.
[BOJ] 백준 10868 최솟값 출처: https://www.acmicpc.net/problem/10868 Input 10 4 75 30 100 38 50 51 52 20 81 5 1 10 3 5 6 9 8 10 Output 5 38 20 5 배열의 특정 구간이 자주 변경되므로 세그먼트 트리(Segment Tree)를 이용합니다. 단말 노드를 제외한 세그먼트 트리에서는 자식 노드들의 최솟값들이 저장됩니다. 인덱스 범위를 벗어나는 경우에는 INF(큰 수)를 반환하게 합니다. (특정 범위에서 최솟값을 query하기 때문에 INF를 반환해도 상관 없습니다.) #include #include #include #define INF 2e9 #define endl "\n" using namespace std; inline int min(int A,.. 2021. 2. 20.
[BOJ] 백준 2357 최솟값과 최댓값 출처: https://www.acmicpc.net/problem/2357 Input 10 4 75 30 100 38 50 51 52 20 81 5 1 10 3 5 6 9 8 10 Output 5 100 38 100 20 81 5 81 배열의 특정 구간이 자주 변경되므로 세그먼트 트리(Segment Tree)를 이용합니다. #include #include #define LM 100000 #define INF 2e9 using namespace std; int N, M, a, b; int maxTree[4 * LM], minTree[4 * LM]; int maxUpdate(int pos, int val, int node, int start, int end) { if (pos < start || end < p.. 2021. 2. 20.
[BOJ] 백준 11505 구간 곱 구하기 출처: https://www.acmicpc.net/problem/11505 Input 5 2 2 1 2 3 4 5 1 3 6 2 2 5 1 5 2 2 3 5 Output 240 48 배열의 특정 구간이 자주 변경되므로 세그먼트 트리(Segment Tree)를 이용합니다. 곱셈의 특성상 구간의 곱을 가지고 있으면 무수히 커질 수 있기 때문에 문제에서 모듈러연산을 요구합니다. 최종 결과에만 모듈러연산을 해준다면 노드가 가지고 있는 값이 Overflow 될 수 있으므로 노드가 가진 값을 갱신할 때도 % 연산 처리 합니다. #include #include #include #define MOD 1000000007 #define LM 1000000 typedef long long ll; using namespace.. 2021. 2. 20.
반응형

티스토리툴바