공부공간

https://www.acmicpc.net/problem/1846 1846번: 장기 N개의 줄에 걸쳐, 게임판에서 각 줄의 몇 번째 칸에 차를 배치했는지를 나타내는 칸의 번호를 순서대로 출력한다. 조건을 만족시키는 배치가 둘 이상이면 아무 것이나 출력한다. 배치가 불가능�� www.acmicpc.net 잘 보면 규칙이 나온다.. package algorithm; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class 장기 { public static void main(String[] args) throws..

https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 블록을 평평하게 할때에, 내가가진 가방에서 블록을 꺼내와서 채울것인지? 현재 블록을 깎고, 내가방에 한개의 블록을 넣을것인지? 를 판단하여 전체 평평화작업에 드는 최소시간을 구하는 문제이다.. 먼저 평평화작업에 대상이되는 높이는 입력으로 주어진 값의 최솟값-최댓값 사이가 될수 밖에 없다. 따라서 최소-최대값 사이의 모든 값을 반복문을 돌면서, 해당 값보다 크면 깎고, 작으면 더해주는 식으로 구현..

https://www.acmicpc.net/problem/2887 2887번: 행성 터널 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. � www.acmicpc.net 3차원 공간에서 모든 지점의 최소스패닝트리를 구하는 문제이다. 최악의 경우 N이 10만개일 때, 자신을 제외한 99999개를 구해야한다. 10만*10만의 연산을 통하여 간선길이를 정렬하면 메모리초과와 시간초과가나기때문에, 정렬을 통하여 m번째 노드는 m-1 , m+1번째만 계산을 통한다. ...m-2, m+2 ...은 정렬이 되어있기 때문에 최소가 보장되지 않는다. 이를 X ,Y, Z 에대해서 한..

https://www.acmicpc.net/problem/6497 6497번: 전력난 문제 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈�� www.acmicpc.net 모든 가로등의 합에서 최소의 가로등의 비용으로 모든 노드를 연결해야하기때문에 MST문제와 동치이다. 크루스칼 알고리즘으로 해결하였다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Comparator; import java.util.PriorityQueue; import java.util.StringTok..

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 최소 컴포넌트의 크기가 2개가 되야 하므로, 초기 N개의 컴포넌트에서 Kruskal 알고리즘으로 성공적으로 Union되었을시, 컴포넌트의 개수를 감소시킨다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Comparator; import java.util.Pri..

https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이 www.acmicpc.net 두명의 이름이 들어왔을때 이전 친구 그룹에 속하는지와 속하지 않으면 새로운친구 그룹을 만들면서 진행하는 문제이다 F=10만이기때문에 적절한 최적화를해주면 통과할 수 있다.. 1 ) 두사람이 모두 HashMap에 없는경우 2 ) 한쪽만 HashMap에 있는 경우 3 ) 둘다 있는경우 세가지로 나누어서 생각해보자.. 1 ) 경우는 친구 그룹의 크기가 2가 항상 보장된다. 2 ) 경우는 친구 그룹이 결정된 그..

https://www.acmicpc.net/problem/2230 2230번: 수 고르기 첫째 줄에 두 정수 N, M(0≤M≤2,000,000,000)이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000을 만족한다. www.acmicpc.net 정렬 후, 투포인터를 이용해 원소의 차이를구해준다. 투포인터가 가리키는 차이가 M 을넘은경우 이후의 ii값증가는 볼필요가 없다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public c..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 3X2 이차원배열과 (0번째는 최댓값계산 , 1번째는 최솟값 계산) 3X1 일차원 배열로 이전에서 올수있는 값중 최대 , 최소를 저장해놓고 다음 STEP을 진행한다. package 풀문제2; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class 내려가기 { publi..