본문 바로가기

분류 전체보기

 (191)
구간 합 구하기( BOJ 2042 ) (1) 문제 2042. 구간 합 구하기 : www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net (2) 문제 이해하기 (3) 문제 해결하기 (4) 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 ..
구간 합 구하기 4( BOJ 11659 ) (1) 문제 11659. 구간 합 구하기 4 : https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net (2) 문제 이해하기 (3) 문제 해결하기 (4) 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include #include #define NMAX 100010 using namespace std..
Fenwick Tree( BIT ) 펜윅 트리 개요 펜윅트리 갱신 1 2 3 4 5 6 7 void update(int pos, int val) { while(pos 1 2 3 4 5 6 7 8 9 10 11 12 void update(int x, int y, int val) { int pos; // 2D Fenwick Tree while(x0) { ret += BIT[pos]; pos -= (pos & -pos); } } cs 1 2 3 4 5 6 7 8 9 10 11 12 13 14 int search(int x, int y) { int pos, ret; // 2D Fenwick Tree ret = 0; while(x>0) { pos = y; while(pos>0) { ret += ..
구간 합 구하기 3( BOJ 11658 ) 문제 11658. 구간 합 구하기 3 : https://www.acmicpc.net/problem/11658 11658번: 구간 합 구하기 3 첫째 줄에 표의 크기 N과 수행해야 하는 연산의 수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 www.acmicpc.net 문제 이해하기 2차원 표에서 구간의 합을 구해야 합니다. 합을 구하는 문제이기 때문에 펜윅트리를 사용할 수 있습니다. 하지만 1차원 배열을 활용한 펜윅트리로는 제한된 시간 안에 해결할 수 없습니다. 데이터가 2차원 표이기 때문에 제한시간 내 해결하기 위해서는 2차원 펜윅트리(2D 펜윅트리)를 만들어야 합니다. 문제 해..
굉장한 학생( BOJ 2336 ) 문제 2336. 굉장한 학생 : https://www.acmicpc.net/problem/2336 2336번: 굉장한 학생 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 세 개의 줄에는 각 시험에서 1등인 학생부터 N등인 학생이 순서대로 주어진다. 학생의 번호는 1부터 N까지 매겨져 있다. www.acmicpc.net 문제 파악하기 나보다 모든 시험을 잘 본 학생이 없는 경우, 굉장한 학생이 됩니다. N이 500,000이기 때문에 단순 for문으로는 힘듭니다. 이 경우, 세그먼트 트리를 차근차근 채워넣으면 문제를 해결할 수 있습니다. 문제 해결하기 우선 첫번째 시험 결과 순서대로 세그먼트 트리에 값을 저장합니다. 세그먼트 트리에 저장하는 위치는 두번째 시험을 기준으로 합니다. 두번째 시험..
체인점( BOJ 2472 ) 문제 2472. 체인점 : https://www.acmicpc.net/problem/2472 2472번: 체인점 첫째 줄에는 매장 후보지의 개수를 나타내는 정수 N이 입력된다(1≤N≤100,000). 매장 후보지들은 1부터 N까지의 번호로 구분된다. 둘째 줄에는 아파트 단지의 위치를 나타내는 세 개의 정수 A, B, C www.acmicpc.net 문제 파악하기 아파트는 A, B, C로 총 3개의 노드가 주어집니다. 후보지 p에서 A, B, C까지의 거리가 후보지 q에서 A, B, C까지의 거리보다 모두 먼 경우, 후보지 p에는 매장을 설치하지 않습니다. 후보지에 매장을 설치할 수 있는지 여부를 알기 위해서는 후보지마다 A, B, C까지의 거리를 구해야 합니다. 거리는 음수가 나오지 않기에 가장 빠른 다..
Fine Dining( BOJ 16763 ) 문제 16763. Fine Dining : https://www.acmicpc.net/problem/16763 16763번: Fine Dining In this example, the cow in pasture 3 should stop for a meal, since her route would only increase by 6 (from 2 to 8), and this increase is at most the yumminess 7 of the haybale. The cow in pasture 2 should obviously eat the hay in pasture 2, since this ca www.acmicpc.net 문제 파악하기 (n-1)마리의 소들은 각각 1 ~ (N-1)번 초원에 있으며 ..
Cowpatibility( BOJ 16764 ) 문제 16764. Cowpatibility : https://www.acmicpc.net/problem/16764 16764번: Cowpatibility Here, cow 4 is not compatible with any of cows 1, 2, or 3, and cows 1 and 3 are also not compatible. www.acmicpc.net 문제 파악하기 친구가 될 수 없는 소들의 쌍을 찾는 문제입니다. 아이스크림의 맛은 총 5개 입력되며, 단순히 중첩 반복문을 사용하기에는 N의 값이 너무 큽니다. 단순히 아이스크림 맛을 카운트하기에는 중복되는 소들을 계산할 수 없습니다. 이 문제는 map 자료형을 사용해야 합니다. 문제 해결하기 #1 map은 탐색에 필요한 키값과 해당 키값에 할당된..

티스토리툴바