공부공간

https://www.acmicpc.net/problem/2268 2268번: 수들의 합 첫째 줄에는 N(1≤N≤1,000,000), M(1≤M≤1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는지를 �� www.acmicpc.net 세그먼트트리의 기본꼴인 연속합을 구하는 문제이다. 세그먼트트리는 O(NM)의 시간복잡도를 O(LogN)으로 줄여주는 자료구조이다. 기본예제를 충분히 연습하고 Fenwick 트리로 넘어가야겠다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; ..

https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net https://algorithmstudy-mju.tistory.com/128 BOJ - 2357 ) 최솟값과 최댓값 https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운..

https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 구간쿼리대 점갱신에 대표적인 예로, 구간에서 최댓값 최솟값 누적합.. 등등을 물어보는 쿼리에 대해 LogN에 처리하기위해 전처리를 해준다. 사실 딱히 설명할게없다.. 세그먼트트리 응용과 구간쿼리 구간갱신을 위한 Lazy Propagation을 공부해야겠다. import java.io.BufferedReader; import java.io.InputStreamR..

https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합� www.acmicpc.net 주말에 할게 없어서 세그먼트 트리를 복습하며 문제를 풀었다.. ( 사실할게많은데 안하는것뿐 ) 세그먼트 트리는 Divide and Conquer를 기반으로 자료를 관리하는 자료구조이다. 적절한 Query에 대해서, 그노드가 해당되었는지의 여부를 한판하고 재귀함수를통해 처리해준다. import java.io.BufferedReader; import java.io.In..

https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진�� www.acmicpc.net 그래프에 간선이 0과 1밖에 없는 경우 특정 시점에서 특정값을 구할때 0-1 BFS를 사용한다. 즉 몇번의 BFS를 통하여 모양이 만들어지는지? 약간말이 이상한데. 위 문제에서는 몇개의 C를 거치면 map의 위치로 갈 수 있는지? 와 치즈가 녹는 시간은 동치이다. 0,0은 치즈가 없음이 보장되어있기에 이쪽에서 bfs를 시작해서 c를 만나면 덱에 뒤쪽에, c를만나지 않으면 덱의 앞쪽에 넣어서 만난 c의개..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 당연히 푼문제인줄 알았었는데 C++로 풀었던문제여서 자바로 다시풀었다. 전체 먹을수있는 상어 후보(?)의 관리는 우선순위큐에관리하여 logN에 찾자. 한스텝마다, 우선순위큐에 먹을수있는 상어들을 뽑고, 그 상어까지의 최단거리 (BFS) 를통하여 처리한후, 그 상어가 있던 자리를 기준으로 다시 힙을 정렬한다. 이 과정을 더이상 먹을수 있는 상어가 없을때까지 진행한다. import java..

https://www.acmicpc.net/problem/1806 1806번: 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길 www.acmicpc.net 역시 이어서 투포인터 유형1번문제이다. https://algorithmstudy-mju.tistory.com/120 BOJ - 2003 )..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 www.acmicpc.net 투포인터를 이용해 연속한 소수의 합으로 목표숫자를 만들수 있는지? 없는지 확인하는 문제이다. 만들어야하는 숫자를 N이라고 할때에, N..