코딩테스트140

• 

  [Java] 백준 2538 : 영역 구하기 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 주어진 배열을 왼쪽 위 상단이 0,0이 되도록 바꾸어 주었다. 안 바꿔주고 그냥 계산해서 해도 정답은 나오지만 그냥 내가 문제를 파악하기 편하도록 바꿨다. static void fillArr(int sx,int sy,int ex,int ey) { //좌표변환 (sx,sy,ex,ey)-> (M-sy,sx,M-ey,ex) int startY=sx; int startX=M-sy; i.. 코딩테스트/백준 2023. 2. 16.

• [Java] 백준 11286 : 절대값 힙 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 가장 작은 값을 출력하는 게 아니라 절댓값이 작은 수를 출력하는 문제이다. 그렇게 하기 위해서는 큐에 값을 담을 때 값을 비교해서 담도록 하면 된다. PriorityQueue pq= new PriorityQueue((o1,o2)->{ int abs1 =Math.abs(o1); int abs2 =Math.abs(o2); return abs1==abs2? Integer.compa.. 코딩테스트/백준 2023. 2. 16.

• 

  [Java] 백준 11403 : 경로 찾기 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 플로이드–워셜 문제이다. 모든 최단 경로를 구하는 알고리즘으로, 3번 중첩된 for문을 사용하기만 하면 된다. 3번 중첩시킬 때 유의할 점은 for문에서 가운데 노드가 가장 바깥에 있어야 한다. * 배열 출력할 때 공백 있게 출력해야 한다. **이중 for문으로 바로바로 출력하는 것보다 StringBuilder를 사용해서 출력하는 게 더 효율적이다. import java.io.*; public class Main { static int N.. 코딩테스트/백준 2023. 2. 15.

• 

  [Java] 백준 1074 : Z https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 2의 N제곱 사이즈의 배열에서 (r,c)을 몇번째로 방문했는지 묻는 문제이다. 1. (r,c)의 위치를 구분했다. z모양으로 움직이는 순서대로 왼쪽 위/ 오른쪽 위/왼쪽 아래/ 오른쪽아래 어디에 있는지 찾는다. 2. 해당하는 위치에서 가장 앞에 있는 위치의 순서값을 cnt에 합한다. 여기서 가장 앞에 위치한 것은 각 0, 4,8,12를 의미한다. 3. 이 방법을 반복해서 작동하도록 재귀하.. 코딩테스트/백준 2023. 2. 15.

• [Java] 백준 1629 : 곱셈 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘 가장 대표적인 예는 병합정렬(Merge Sort)이다. import java.util.*; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); long A = sc.nextInt(); long B = sc.nextInt(); long C = sc.ne.. 코딩테스트/백준 2023. 2. 13.

• [Java] 백준 11057 : 오르막 수 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 1 2 10 9 8 7 6 5 4 3 2 1 3 55 표에서 세로는 자릿수(N)를 의미한다. 가로는 우리가 이용할 수 있는 숫자(i)이다. 채워진 값은 i를 가지고 N자리수를 만들었을 때의 개수이다. 예를 들면 N=1 이면, 0,1,2,3,4,5,6,7,8,9를 만들 수 있다. N=2 이면,.. 코딩테스트/백준 2023. 2. 10.

• [Java] 백준 7526 : 나이트의 이동 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net import java.util.*; public class Main { static class Point{ int x,y; Point(int x,int y){ this.x=x; this.y=y; } }//class Point static int[][] arr; static boolean[][] visit; static int T,N; //나이트가 움직일 수 있는 방향 static int[] dx =.. 코딩테스트/백준 2023. 2. 10.

• 

  [Java] 백준 1992 : 쿼드트리 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 쿼드를 압축하는 방법은 간단하다. 가지고 있는 모든 수가 같을 때, 같은 수로 압축을 하면 된다. 예를 들어, 이렇게 주어졌을 때, 위 배열을 하나의 덩어리로 보았을 때 모든 수가 같지 않다. 그래서 압축을 할 수 없다. 압축을 하지 못하면 사이즈를 행, 열을 반으로 나누어 살펴본다. 이렇게 4개로 나누었을 때 각각을 하나의 덩어리로 보면 같은 수로만 이루어진 부분이 있다. 이는 압축.. 코딩테스트/백준 2023. 2. 9.

• [Java] 백준 9465 : 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net card []에 가격을 넣어준다. 0번째 카드가 0 인 것은 나중에 최댓값 찾을 때를 위해 비워 둔 것이다. 0 50 10 100 20 40 0 30 50 70 10 60 이때 dp[][]에 각 해당하는 자리의 스티커를 떼어냈을 때의 최댓값을 더해 대입하면 된다. 해당 자리의 윗칸 스티커를 떼려면 직전에 아래칸 스티커를 떼었거나, 직전 아래칸 스티커는 떼지 않고 전전 아래칸 스티커를 떼.. 코딩테스트/백준 2023. 2. 9.

• [Java] 백준 2468 : 안전영역 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net - 비가 오지 않았을 때는 안전영역이 1이다. (하나의 덩어리로 보기 때문에) - 높이가 1인 경우부터 최고 높이까지 비에 잠겼을 경우 안전지대를 찾고 그 최대 값을 구한다. import java.util.*; public class Main { static int N; static int [][] map; static boolean [][] check; static int[] dx = {1, 0, -1.. 코딩테스트/백준 2023. 2. 8.

• [Java] 백준 11052 : 카드 구매하기 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net - 카드 i개가 들어 있는 카드팩 각 가격 price[] - 카드 N개를 구매하기 위한 최대금액 dp[] 아래처럼 진행이 되는데 여기서 규칙을 찾으면 된다. dp[0]=0, 1) 카드 한 장을 살 때 필요한 금액 dp[1]=price[1] =dp[0] + price[1] 2) 카드 두장을 살 때 필요한 금액 dp[2]=price[2] =dp[0] + price[2] dp[2]=price[1]*2 = dp.. 코딩테스트/백준 2023. 2. 8.

• [Java] 백준 1991 : 트리 순회 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net import java.io.*; public class Main { static class Node{ char value; Node left; Node right; Node(char value, Node left, Node right){ this.value = value; this.left = left; this.right = right; } }//class Node static int.. 코딩테스트/백준 2023. 2. 7.