본문 바로가기
728x90
반응형

코딩/백준-자바88

[자바] 백준 14500번: 테트로미노 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 회전, 대칭까지 생각하면 폴리오미노가 총 19가지가 생기는데 이 모든것을 일일이 적어서 하기에는 너무 힘들것같았다. 문제에서 가능한 폴리오미노가 5종류 있다고 해서 이 5종류를 어떻게 손봐야할까...생각하던 찰나 그냥 폴리오미노에 대한 조건을 가지고 백트래킹을 하면 될 것 같았다. 백트래킹으로 풀고 나서 확인해보니 값이 틀렸다. 왜 틀렸는지 visited를 출력해서 보니 "ㅗ"모양을 만들 수가 없.. 2023. 2. 10.
[자바] 백준 14499번: 주사위 굴리기 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 어떠한 규칙이 있나? 찾아보려다가 주사위를 굴릴 때마다 주사위의 동서남북위아래가 어떻게 변하는지를 다 적어봤다. 그냥 하나하나 다 구현해놓는게 빠를것 같아서 주사위 class를 하나 만들고, 주사위 객체를 만들어 동서남북위아래에 적힌 숫자를 관리하는것이 좋을것 같았다. import java.io.BufferedReader; impo.. 2023. 2. 9.
[자바] 백준 21661번: 다각형의 면적 https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 입력으로 꼭짓점의 좌표가 순서대로 들어오는데, 순서대로라는 점을 보아 신발끈 공식을 사용하면 될 것 같다. 신발끈 공식은 꼭짓점의 좌표를 순서대로 늘어놓고, 교차로 곱하고 빼면서 다각형의 넓이를 구하는 공식이다. 자세한 계산방법은 https://namu.wiki/w/%EC%8B%A0%EB%B0%9C%EB%81%88%20%EA%B3%B5%EC%8B%9D 신발끈 공식 - 나무위키 이 저작물은 CC BY-NC-SA 2.0 KR에.. 2023. 2. 8.
[자바] 백준 11758번: CCW https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 오랜만에 수학문제를 풀었다 P1이 원점이라고 했을 때 P1,P2,P3 중 두개 이상의 점이 같은 곳에 있는 경우, 또는 x=0이나 y=0 직선 위에 세 점이 있는 경우 => 방향성이 없다 P2가 오른쪽(1,4사분면)에 있을 때는... {P1과P2를 그어 직선을 하나 만든다. 직선상에 P3가 존재하는 경우 => 세 점이 나란하므로 .. 2023. 2. 7.
[자바] 백준 1915번: 가장 큰 정삼각형 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net dp로 푼 문제 입력받는 순서대로 dp를 채워나간다. 현재 칸의 값이 0이면 dp[현재칸][]에도 0을 넣는다. 현재 칸의 값이 1이면, 내 왼쪽, 내 윗쪽, 내 위에서 왼쪽 이 세 칸의 값을 봐야 한다. 세 칸의 값을 보고 세 값 중 최솟값을 가져와서, dp[현재칸][]=최솟값+1을 하면 된다. (왜 이렇게 동작하는지는 그림을 그려보면서 생각해보자) 우선 현재칸의 값이 0이면 이 칸을 포함한 정사각형은 만들수가 없으니 0, 현재칸의 값이 1이면.. 우선 나 혼자서는.. 2023. 2. 6.
[자바] 백준 1932번: 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 삼각형의 맨 꼭대기에서부터 출발해서, 가질 수 있는 최댓값을 각 자리마다 계산해주면 된다. 한 행 안에서 맨 왼쪽 요소는, 그 윗칸의 맨 왼쪽 요소로부터 올 수밖에 없고 한 행 안에서 맨 오른쪽 요소도 마찬가지로, 그 윗칸의 맨 오른쪽 요소로부터 올 수 밖에 없다. 그렇다면 나머지 중간 요소들은? 윗칸의 한 칸 왼쪽 요소, 윗칸의 현재 위치 요소 중 더 큰값으로부터 오면 최댓값을 만들 수 있다. 이렇게 최댓값을 자리별로 모두 구해놓은 다음, 마지막 행에서 최댓값을 찾아.. 2023. 2. 5.
[자바] 백준 11660번: 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 2차원 배열을 만들어서 0행,0열은 모두 0으로 채우고, 한 행씩 입력을 받는데 arr[i][j]=arr[i][j-1]+입력받은값 으로 배열을 채워서, 각 행은 오른쪽으로 가면서 누적합이 기록되게 하였다. 이제 x1,y1,x2,y2를 입력받고 for(int i=x1;i 2023. 2. 4.
[자바] 백준 11659번: 구간 합 구하기 4 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 구간합을 구하면 되는데, 숫자가 변하지 않기 때문에 누적합을 배열에 넣어놓고 배열[j]-배열[i-1] 값을 꺼내 출력하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public clas.. 2023. 2. 3.
[자바] 백준 11051번: 이항 계수2 https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항 계수 1과 같은 문제지만, 조건이 1 2023. 2. 2.
[자바] 백준 1644번: 소수의 연속합 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 소수는 에라토스테네스의 체 알고리즘을 이용해서 소수만 따로 arraylist에 모아 두고, 구해놓은 arraylist를 이용해서 투포인터 알고리즘을 쓰면 연속합의 개수를 쉽게 구할 수 있다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; public class P1644 { public static void main(String[] args) thr.. 2023. 2. 1.
[자바] 백준 1837번: 암호제작 https://www.acmicpc.net/problem/1837 1837번: 암호제작 원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로 www.acmicpc.net 10의 100승까지 되는 엄청 큰 숫자를 다뤄야 하기 때문에 BigInteger을 사용한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInteger; import java.util.StringTokenizer; public class P1.. 2023. 1. 31.
[자바] 백준 6588번: 골드바흐의 추측 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 에라토스테네스의 체 알고리즘으로 소수를 판별해놓고, 반복문으로 i를 2~100만까지 증가시키면서 i가 소수이고, n-i가 소수인 경우에 출력한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class P6588 { static boolean.. 2023. 1. 30.
[자바] 백준 11653: 소인수분해 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class P11653 { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.par.. 2023. 1. 30.
[자바] 1735번: 분수 합 https://www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net 분수의 분자,분모를 각각 따로 변수에 저장하고 두 분수를 합한 값도 분자,분모를 따로 변수에 저장 해 둔다. 그리고 반복문을 이용해서 분자,분모를 나누어 줄 것인데, for반복문을 이용, 2부터 시작해서 분자,분모가 모두 나누어 떨어지는 경우에는 나눌 수 있는 만큼 while문을 이용하여 모두 나누어주면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu.. 2023. 1. 30.
[자바] 백준 2252번: 줄 세우기 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상정렬 알고리즘을 사용하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;.. 2023. 1. 29.
[자바] 백준 1717번: 집합의 표현 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 이코테, 자료구조에서도 배웠었던 find-union 알고리즘이다. 오랜만에 짜보니 대충은 생각나도 제대로 구현하기가 좀 힘들었는데 이코테에서 배웠던 알고리즘이 조금 더 간단했던것 같아서 그때 배운 그대로 작성 해 봤다. 2022.08.08 - [파이썬 공부/이코테] - 8. 기타 그래프 이론: 서로소 집합 자료구조 union, find import java.. 2023. 1. 28.
[자바] 백준 2042번: 구간합 구하기(실패) https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 실패했다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class P2042 { public static void main(String[] arg.. 2023. 1. 28.
[자바] 백준 1991번: 트리 순회 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 트리를 입력받고, 전위순회, 중위순회, 후위순회 하면 된다. 입력이 한줄에 (노드) (왼쪽 자식) (오른쪽 자식) 으로 들어온다. 나는 노드를 Node클래스로 표현했고, 노드는 최대 26개밖에 되지 않기 때문에 Node배열을 만들어서 사용했다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputS.. 2023. 1. 27.
[자바] 백준 2748번: 피보나치 수2 https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net import java.util.Scanner; public class P2748 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long[] arr = new long[90]; arr[0] = 0; arr[1] = 1; arr[2.. 2023. 1. 26.
[자바] 백준 2805번: 나무 자르기 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 나무가 100만개까지 입력될 수 있기 때문에 O(n)선에서 끝내야겠다는 생각이 우선 들었다 우선 배열을 만들어서 나무들의 키를 입력받는다. 그리고 배열을 내림차순으로 정렬하고 순회를 시작한다. h=0부터, 첫번째 나무부터. 나무를 h높이에서 자른 다음 sum을 자른 만큼 증가시켜준다. 만약 sum이 m을 초과하는 경우(나무가 남는다) 절단기를 높여야 한다. .. 2023. 1. 25.
728x90
반응형

티스토리툴바