본문 바로가기

전체 글

(645)

백준 : 12844 https://www.acmicpc.net/problem/12844 12844번: XOR 첫 번째 줄에 수열의 크기 n(0 < n ≤ 500,000)이 주어진다. 수열의 원소가 0번부터 n - 1 번까지 차례대로 주어진다. 수열의 원소는 100,000보다 작거나 같은 자연수 또는 0이다. 세 번째 줄에 여러분이 수행할 쿼리의 개수 m(0 < m ≤ 500,000)이 주어진다. 그 다음 m 개의 줄에는 t, a, b, c가 주어진다. t가 1이면 첫 번째 종류의 쿼리를 수행해야 하고, t가 2이면 두 번째 종류의 쿼리를 수행해야 한다. (0 ≤ www.acmicpc.net 세그먼트 트리 늦은 전파문제. XOR연산은 A ^ B = C 라고한다면 A ^ B ^ B = A^(0) = A 가 된다. 이걸이용해서 ..

백준 : 1395 (JAVA) https://www.acmicpc.net/problem/1395 1395번: 스위치 문제 준규네 집에는 총 N개의 스위치가 있고 이를 편하게 1번부터 N번까지 차례대로 번호를 매겼다. 그리고 준규의 취미는 이 스위치들을 켜고 끄는 것이다. 준규가 하는 스위치를 갖고 노는 일은 크게 두 가지이다. 하나는 A번부터 B번 사이의 스위치 상태를 반전시키는 것이고 다른 하나는 C번부터 D번 사이의 스위치 중 켜져 있는 상태의 스위치의 개수를 세는 것이다. 하지만 준규가 싫증을 느껴 우리가 이 귀찮은 일을 떠맡게 되었고 프로그래밍을 통해 일을 처리 www.acmicpc.net 늦은 전파 세그먼트트리 문제. 세그먼트트리를 구현하고 새로운값 갱신시에는 늦은전파를 활용한다. 문제에서 스위치 이기때문에 laze[n] 홀..

백준 : 109999 (JAVA) https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 회수이고, K는 구간의 합을 구하는 회수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c 또는 a, b, c, d가 주어지는데, a가 1인 경우 b번째 수부터 c번째 수에 d를 더하고, a가 2 www.acmicpc.net 게으른 전파 알고리즘 기존 세그먼트 트리에서 구간의 업데이트를 해주엇을때 모든 노드를 방문하면서 업데이트하는것이아니라 대표..

백준 : 2042 ( 세그먼트 트리) https://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번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b번째 수부터 c번째 수까지의 www.acmicpc.net 세그먼트 트리의 초기화 변경 부분합을 구현하는 기초적인 문제. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1..

세그먼트 트리 기존 구간합을 구하기위해선 범위 안에 있는 모든 배열을 탐색해서 구해야하고 그 때마다 배열을 탐색해야한다. 하지만 세그먼트트리는 다이나믹프로그래밍의 일종으로 작은 단위부터 더해가서 각각 구간들의 합을 저장한다. 구간합은 Binary Tree 와 재귀를 사용해서 만들수가 있다. 구간합을 구하는 Tree 의 크기는 2^k >= N (n은 배열의 수) 를 만족하는 가장 작은 k값을 구하고 2^k *2 한것이 Tree의 크기가 된다. 생각하기싫은 N*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 public class Segment { static int..

백준 : 1517 https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다. www.acmicpc.net 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 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 package day..

백준 : 2617 https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 아 래와 같은 일을 하려 한다. 우리에게 주어진 것은 양팔 저울이다. 한 쌍의 구슬을 골라서 양팔 저울의 양쪽에 하나씩 올려 보면 어느 쪽이 무거운 가를 알 수 있다. 이렇게 M개의 쌍을 골라서 각각 양팔 저울에 올려서 어느 것이 무거운 가를 모 www.acmicpc.net DFS 문제가 하도안풀리길래 질문 게시글을 보았다. 테스트 케이스중에 u v 가 같은 순환형 케이스가 존재한다는 것이다. 1이 1보다 ..

백준 : 2251 https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다. 이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. www.acmicpc.net BFS문제 문제의 제한값을 보면 A B C B, A->C B->A,B->C C->A,C->B 로 물을 붇는 경우의 수 밖에없다 . 이러한 각각..

이전 1 ··· 68 69 70 71 72 73 74 ··· 81 다음

티스토리툴바