공부공간

www.acmicpc.net/problem/10282 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 www.acmicpc.net 해킹당하는 컴퓨터의 개수와 시간을 구하기위해 다익스트라 알고리즘을 사용한다. 컴퓨터의 개수는 다익스트라알고리즘을 돌면서 만나는 노드의 개수이고, 시간은 다익스트라로 구한 최단경로중 길이가 가장 큰 것이다. 반례로, 아무컴퓨터와 연결되어있지 않은경우, 1대만 감염되어야 한다. 시간은 0초 import java.io.BufferedReader; import java.io.Input..

www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net N이 10만이기때문에 일반적인 모든구간을 탐색하는 N^2풀이시 시간초과를 만나게된다. 복잡도를 줄이기위해 어떤 직사각형을 생각해보면 그 높이는 입력으로 들어온 것들중 한개일 것이다. 너비는 적당한 구간일 것이고, 따라서 높이를 N개 탐색하는데, 구간에 대해서 최솟값을 반환해주는 함수가있다면, 높이를 최소부터 최대까지 탐색할수 있을것이다. 그러면 구간 점 ..

www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 모 기업 코딩테스트에서 출제되었던 문제이다. 배열의 앞,뒤로 탐색하면서 나보다 큰 벽을 만났을때, 그 중간 벽들과의 차이를 더해준다. 시간복잡도 O(2*500)으로 처리가능하다 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class 빗물 { publi..

www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 www.acmicpc.net 트리의 지름을 구하는 알고리즘(?)은 특정점 ( 아무점 ) 에서 가장 먼 하나의 노드를 선택하고 그 노드에서 가장 먼점을 선택하면 된다. ( 증명은 생략 ) 최장거리계산을 위해, 다익스트라 알고리즘을 사용하여서 각 노드까지의 최단거리 중 큰값을 찾고, 그 노드부터 다시 최단거리중 최장거리를 찾는다. import java.io.BufferedReader; import java.io.InputStream..

www.acmicpc.net/problem/1783717837번: 새로운 게임 2재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하�www.acmicpc.net3 가지를 나누어서 생각해보면, 움직이는 다음 좌표가 흰색인경우잠깐 TEMP 리스트에 담고 진행한다. 빨간색인경우 TEMP 리스트를 뒤집고 진행한다. 파랑색인경우, 또 3가지로 나뉜다.파랑 -> 흰 이면 현재값만 방향을 바꾸어주고 흰색처리파랑 -> 빨 이면 현재값만 방향을 바꾸어주고 빨강색처리파->파이면 이동하지 않는다. 매턴중간에 4개가 쌓였는지 체크하기위해 좌표를 가지고다닌다.import java.io.Buf..

www.acmicpc.net/problem/8983 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net 사냥꾼의 사정거리를 계산할 때에, 동물에서 가장가짜운 사대의 왼쪽 오른쪽만 보면된다. 전체탐색 x 이분탐색으로 사대의 위치를 찾고, 정확히 찾는다면 L값이 Y값보다 같거나 큰지의 여부를 파악하고, 찾지못했다면, 양옆의 사대의 X값의 차이 + y 값이 L사정거리보다 같거나 작으면 범위안에 있는 것이다. import java.io.BufferedReader;..

www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 0부터 ~ 최대 Capacity 까지의 수를 이분탐색으로 구하고, 구한 숫자로 유량을 보낼 수 있는지? 확인하는 이분탐색 + bfs 문제 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; impor..

www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 라인과 카카오를 조져서 알고리즘을 다시해야한다. 정렬할때에 우선순위큐를 사용해서 NlogN에 정렬해서 배열을 만든다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; import ..