[백준(baekjoon) 1184] 귀농 문제 백준 1184 N x N 크기의 땅은 각 단위 정사각형 (i, j)당 의 수익을 가진다. 이 땅을 변에 평행한 직사각형 땅 두개로 나누고자 한다. 단, 두 땅은 반드시 한 꼭지점에서만 만나고, 총 땅의 수익이 같아야 한다. 조건에 맞게 나눌 수 있는 방법의 수를 출력하라. N = -1,000 해결 알고리즘 배열을 활용한 구현 문제이다. DP를 활용해 풀었다. 방법 생각을 더 깊게할수록 복잡해지는 문제 같다. 다시 처음으로 돌아와서 아래처럼 풀었는데, N의 범위가 작아서 시간초과가 나지 않았다. 중복코드를 줄이기 위해 배열을 활용해 방향키 설정(?)을 해주었다. 1.직사각형이 공유하는 꼭지점이 반드시 하나이다. 즉, 전체 정사각형 땅에서 공유 꼭지점이 될 수 ..

[백준(baekjoon) 6588] 소수 구하기 문제 백준 6588 ‘4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.’ 하나 이상의 테스트 케이스 T가 주어질 때(0이 나오면 끝), 다음과 같은 규칙으로 출력하라 답이 존재 : T = a + b출력 (답이 여러개일 경우 b - a가 가장 큰 것) 답이 없음 : Goldbach's conjecture is wrong.출력 예시 8 = 3 + 5 20 = 3 + 17 42 = 5 + 37 해결 알고리즘 소수를 만드는 방식은 에라토스테네스의 체를 이용하였다. 자세한 방법은 에라토스테네스의 체로 소수 구하기 참고! 방법 T = a + b를 만족하는 홀수 소수 a, b는 많을 것이다. 따라서, 가장 큰 b - a를 찾기 위해 조건을 만족하는 가장 ..

[백준(baekjoon) 1929] 소수 구하기 문제 백준 1929 M 이상 N 이하인 소수를 모두 출력하시오. (1≤M≤N≤1,000,000) 해결 알고리즘 두가지 방식으로 풀었다. 1. 소수로 나누기 소수인지 확인하기 위해 자신보다 작은 소수들로 모두 나누어 확인하는 방법 n개의 수에 자신보다 작은 소수들의 개수k만큼 모두 확인하여야 한다. 곱해서 n이 되는 수 중 가장 큰 수인 이하로만 검사하면 된다. 2. 에라토스테네스의 체 소수의 배수들 지워나가는 방법 O(n log log n) 시간복잡도를 가진다. 자세한 내용 방법 소수 여부를 저장해 둘 [N + 1]크기의 배열을 생성한다. 가장 작은 소수 2부터 시작하여 수들을 차례대로 확인한다. 지워지지 않은 경우 해당 수는 소수이다. 소수의 배수들을 모..

문제 백준 1373 입력되는 2진수를 8진수로 바꾸어라. 2진수의 길이는 1,000,000을 넘지 않는다. 해결 3개씩 묶어 8진수로 바꾸어주면 된다. (2진수 -> 10진수로 바꾸는 방법과 동일) 뒤에서 부터 묶기 때문에 앞에 부족한 부분을 어떻게 하느냐가 문제 나는 input을 char []으로 받아 index가 범위를 벗어날 때 아무처리도 하지 않았다. 주의 쉬운 문제지만 많이 틀렸다. 그 이유는 범위 문제 처음 문제를 잘못 이해해서 1,000,000이하의 수가 들어온다는 줄 알았다. 하지만 1,000,000자리이므로…. 숫자로 받으면 안된다. 범위를 훨씬 넘기기 때문 output역시 long을 넘어간다. 따라서 문자열로 처리해야한다. 시간 문제 위의 문제를 파악하고 간단히 String으로 처리했지..

문제 백준 9613 최대공약수(GCD) 의 합을 구하시오. 원리 유클리드 호제법, GCM, LCD 설명 포스트 참고! 구현 java 1.import java.util.*; 2. 3.public class Main { 4. public static void main(String[] args) { 5. Scanner sc = new Scanner(System.in); 6. int t = sc.nextInt(); 7. for (int k = 0; k < t; k++) { 8. int n = sc.nextInt(); 9. int[] inputs = new int[n]; 10. for (int i = 0; i < n; i++) inputs[i] = sc.nextInt(); 11. 12. long sum = 0; ..

[백준(baekjoon) 1780] 대회 or 인턴 문제 백준 1780 N x N 크기의 행렬은 -1, 0, 1의 값을 가진다. 다음과 같은 규칙으로 종이를 자른 후, -1, 0, 1로만 채워진 종이의 개수를 차례대로 출력하시오. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 해결 알고리즘 전형적인 분할 방식 문제이다. 방법 큰 종이를 9개의 작은 종이로 나누는 과정을 반복한다. 시작점, n을 매개변수로 받아 구하고자 하는 종이의 크기 및 값들에 접근할 수 있다. 3 * 3 for문을 돌린다. 작은 종이의 크기는 n / 3이 될 것이다. 종이의 크기 n == 1까..