본문 바로가기
반응형

전체 글1305

[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.
세그먼트 트리(Segment Tree) 세그먼트 트리 구간에 대한 정보를 저장하기 위한 트리 자료구조 O(N logN) N == 8일 때 Segment Tree 특정 구간의 최적화된 답을 구하는 문제인 경우 빠른 시간안에 답을 얻을 수 있음 (ex. 구간의 합, 최대값, 최소값, 곱) N == 5일 때 Segment Tree - 완전 이진트리 형태 (Root Node의 인덱스가 1번인경우 보다 쉽게 자식노드에 접근 가능) : 재귀적인 구조로 구현을 많이 합니다. - 전체 구간이 [0, N-1]일 때, 단말 노드는 구간 길이 1인 구간을 갖습니다. → 배열 = [a, b, c, d, e]가 있을 때 단말노드(Leaf Node)에 배치된다고 보면 됩니다. * 트리에서 실제 노드번호는 N의 크기에 따라 좌우되기 때문에 단말노드 번호를 쉽게 알 수 .. 2021. 2. 20.
[BOJ] 백준 13458 시험감독 삼성 SW 코딩 테스트 준비(A형) 삼성 SW 기출 모음 출처: https://www.acmicpc.net/problem/13458 문제에서 제시하는 class의 구성원은 다음과 같다. 응시자 수 A명이 주어졌을 때, 총 감독관 1명과 여러명의 부감독관이 서로 겹치지 않게 수험생을 관리해야 최소 인원으로 구성된 감독관으로 진행될 수 있다. 이때, 총 감독관이 1명이 무조건 있고, 부감독관이 몇 명이 되는지 구해야 한다. Input 3 3 4 5 2 2 Output 7 [0] 수험생 3명 - 총감독관 1명이 2명 mark / 부감독관 1명이 1명 mark [1] 수험생 4명 - 총감독관 1명이 2명 mark / 부감독관 1명이 2명 mark [2] 수험생 5명 - 총감독관 1명이 2명 mark / 부감독관.. 2021. 2. 20.
[BOJ] 백준 2531 회전초밥 출처: https://www.acmicpc.net/problem/2531 Input 8 30 4 30 7 9 7 30 2 7 9 25 Output 5 - 슬라이딩 윈도우 기법을 이용해서 먹은 초밥 k를 갱신합니다. ex) [7 9 7 30 2 7 9 25] 초밥이 존재하고, 4개씩 먹을 때, 처음 [7 9 7 30] 상태에서 7 out / 2 in → [9 7 30 2] → 9 out / 7 in → [7 30 2 7] - 먹은 초밥의 종류는 check[3000 + 10]으로 처리합니다. 먹은 초밥 = [1 1 2 2] → check[1] = 2, check[2] = 2 → check = [0 2 2 ...] 이때, check[i] > 0인 경우 초밥의 종류(cnt)에 세어집니다. - 쿠폰은 적힌 숫자의.. 2021. 2. 20.
반응형

티스토리툴바