코딩 테스트/백준
백준 2169 자바 - 로봇 조종하기 문제
www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 첫째 줄은 왼쪽 부터 오른쪽으로 dp를 셋팅하고 나머지는 좌우와 위 중 가장 큰값으로 dp를 만들면됨 다만 좌 & 위, 우 & 위로 구하고 그 중 큰값으로 dp를 셋팅하는 방식으로 해야합니다. 이유는 좌를 계산할때 우가 안되있기 때문에 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; i..
백준 10775 자바 - 공항 문제
www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 그리드를 기본으로 파인드유니온을 통해서 부모가 0 인경우 까지 구하는 방식 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; // 공항 문제 - 10775번 public class Airport { static int G, P; static int result =..
백준 11505 자바 - 구간 곱 구하기
www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 세그먼트를 이용해서 구간의 곱을 구하면 된다. 문제에서 신경쓸 부분으로는 1. 입력받은 값은 항상 1,000,000,007보다 낮으므로 항상 나머지가 된다. 2. 입력받은 값은 최대 1,000,000 이므로 곱을 누적하면 숫자가 커지므로 tree에 저장할때는 나머지값으로 셋팅한다. 3. 두수 곱의 나머지는 두수의 나머지의 곱과 같다(단 나누는 수보다..
백준 1194 자바 - 달이 차오른다, 가자. 문제
www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 이문제의 해결점은 방문 여부를 3차원배열로 만들고 소지한 키들을 비트마스크로 하여 방문한 지점에 가지고 있는 키목록으로 방문한 적이 있는지 없는지를 셋팅하는 것이다. import java.io.*; import java.util.*; // 달이 차오른다, 가자. 문제 - 1194번 class Dot { int x; int y; int key; int time; public Dot(..
백준 17143 자바 - 낚시왕 문제
www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 생각보다 푸는데 오래걸렸는데 그이유로 1. map을 int로 하고 상어의 크기로 상어의 유무만을 처리할려고함. 2. ArrayList의 인자 값을 remove를 save하게 하는 방식을 몰랐음 1. 이부분이 문제로 다가온 이유는 둘 이상의 상어가 동일한 지점으로 이동하는 경우에 크기가 큰 상어를 남기고 다른 상어를 삭제해야하는데, 이동을 하면서 map에 작은 상어가 먼저 처리되서 있을때 큰상..
백준 1655 자바 - 가운데를 말해요 문제
www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 우선순위 큐를 이용해서 heap을 만들어서 처리하는 방법 maxheap은 큰 값이 우선 minheap은 작은 값이 우선 입력 값을 maxheap에 1개 추가후 minheap에 추가하면서 두개의 길이를 지속적으로 맞춰줌. maxheap의 최대값이 minheap의 최소값보다 크다면 둘을 swap 한다. maxheap의 최대값이 중간값이 된다. 문제의 예시의경우 swap이 발생하지는 않음 1 입력 [..
백준 1766 자바 - 문제집 문제
www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 그래프이론, 위상정렬, 우선순위 큐 개념이 들어있는 문제로 문제 풀이방식은 다음과 같다. 1. 입력받은 문제들의 index를 graph로 만들고 2. 각 문제들의 선행되어야하는 문제의 수 즉 진입차수(inDegree)를 배열로 셋팅한다. 3. 우선순위 큐를 index값이 작은 것이 우선되도록 만들고 4. 진입차수가 0인 문제들을 해당 큐에 넣는다. 5. 큐를 돌면서 해당 문제의 i..
백준 14003 자바 - 가장 긴 증가하는 부분 수열 5 문제
앞서 풀었던 가장 긴 증가하는 부분 수열 2번에 수열 index를 같이 셋팅한 뒤 계산한다고 보면 된다. 가장 긴 증가하는 부분 수열 2번에 수열에서는 i 0 1 2 3 4 5 arr 1 5 6 2 3 4 listForSize 0 1 2 3 이렇게 까지만 구한뒤 listForSize의 값을 이용해서 길이를 구했다. 여기에 자신 증가하는 수열의 몇번째를 차지하고 있는지에 대한 리스트를 추가한다. 위에 예에 추가하면 아래와 같다. i 0 1 2 3 4 5 arr 1 5 6 2 3 4 listForSize 0 1 2 3 indexs 0 1 2 1 2 3 이부분에서 입력받은 수열 arr(A)를 뒤에서 부터 순회하면서 값을 체크한다. int index = listForSize.size() - 1; Stack st..