알고리즘/백준 문제 및 정답
문제 번호 15894번 : 수학은 체육과목 입니다 - JAVA [자바]
문제 번호 15894번 : 수학은 체육과목 입니다 - JAVA [자바]
2023.04.13https://www.acmicpc.net/problem/15894 15894번: 수학은 체육과목 입니다 성원이는 수학을 정말 못 하는 고등학생이다. 수학을 못하는 대신 근성과 팔 힘이 뛰어난 성원이는 수학 시험에서 수학 지식을 사용하지 않고 근성과 체력을 사용해 문제를 푼다. 지난 시험에서 www.acmicpc.net 문제 설명 기하를 빙자한 등차수열 문제입니다. 문제 풀이 이런 문제는 일단 수를 구하다 보면 규칙이 있을 수밖에 없습니다. N=1 -> 4 N=2 -> 8 N=3 -> 12 N=4 -> 16 규칙이 보입니다. 수식은 4+4(N-1)가 되겠습니다. 식을 구했다면 구현은 너무 쉽습니다. import java.util.Scanner; public class Number_15894 { publi..
문제 번호 3009번 : 네 번째 점 - JAVA [자바]
문제 번호 3009번 : 네 번째 점 - JAVA [자바]
2023.04.13https://www.acmicpc.net/problem/3009 3009번: 네 번째 점 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. www.acmicpc.net 문제 설명 사각형의 꼭짓점을 좌표로 보고 3개의 꼭짓점의 위치를 알려주고 나머지 한 꼭짓점의 위치를 출력하는 문제입니다. 문제 풀이 사각형을 좌표로 본다면 특징이 있습니다. 그 특징은 X축의 같은 값이 총 2개 Y축의 같은 값이 2개씩이라는 것입니다. 위에 그림을 보시면 그 사각형 모두 x축 값이 2개 y축 값이 2개로 쌍을 이루어 사각형이 좌표 위에 존재하고 있습니다. (2,2), (2,4), (5,2), (5,4) -> x 값 : 2,5 / y 값 : 2,4 (1,1), (..
문제 번호 1085번 : 직사각형에서 탈출 - JAVA [자바]
문제 번호 1085번 : 직사각형에서 탈출 - JAVA [자바]
2023.04.13https://www.acmicpc.net/problem/1085 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램 www.acmicpc.net 문제 설명 사각형 안에 있는 좌표에서 사각형의 변까지 최단 거리를 구하는 문제입니다. 문제 풀이 문제만 잘 이해하셨다면 직관적으로 어떻게 풀어야 하는지 알 수 있습니다. 사각형이 있다고 가정하면 변으로 가는 방법이 총 4가지가 있습니다. 위쪽 변, 아래쪽 변(Y축), 왼쪽변(X축), 오른쪽 변 이 4가지 길 중에 최단 거리를 찾으면 해결할 수 있는 문제입니다. import ja..
문제 번호 27323번 : 직사각형 - JAVA [자바]
문제 번호 27323번 : 직사각형 - JAVA [자바]
2023.04.11https://www.acmicpc.net/problem/27323 27323번: 직사각형 정수 A, B 가 주어진다. 세로 길이가 A cm, 가로 길이가 B cm 인 아래와 같은 직사각형의 넓이를 cm2 단위로 구하시오. www.acmicpc.net 문제 설명 a,b 값을 받아서 곱을 출력하는 문제입니다. 문제 풀이 사각형의 넓이는 구하는 공식은 a*b입니다. 공식을 안다면 쉽게 문제를 해결하실 수 있습니다. import java.util.Scanner; public class Number_27323 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int a = sc.nextInt(); int b = sc.n..
문제 번호 9506번 : 약수들의 합 - JAVA [자바]
문제 번호 9506번 : 약수들의 합 - JAVA [자바]
2023.04.10https://www.acmicpc.net/problem/9506 9506번: 약수들의 합 어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다. 예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다. n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라. www.acmicpc.net 문제 설명 약수를 모두 찾고 그 수의 합과 수를 비교하는 문제입니다. 문제 풀이 약수는 반복문으로 모두 나눠서 확인하고 해당 수와 비교하면 쉽게 풀 수 있는 문제입니다. 풀다 보면 자연스럽게 정답으로 갈 수 있으실 겁니다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner..
문제 번호 2501번 : 약수 구하기 - JAVA [자바]
문제 번호 2501번 : 약수 구하기 - JAVA [자바]
2023.04.09https://www.acmicpc.net/problem/2501 2501번: 약수 구하기 첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다. www.acmicpc.net 문제 설명 약수를 모두 찾고 연하는 순서의 약수를 출력하는 문제입니다. 문제 풀이 약수는 반복문으로 모두 나눠서 확인하고 count는 조건문을 이용해 문제를 풀었습니다.너무 간단한 문제임으로 주석만 보셔도 이해할 수 있을 것입니다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num = s..
문제 번호 5086번 : 배수와 약수 - JAVA [자바]
문제 번호 5086번 : 배수와 약수 - JAVA [자바]
2023.04.09https://www.acmicpc.net/problem/5086 5086번: 배수와 약수 각 테스트 케이스마다 첫 번째 숫자가 두 번째 숫자의 약수라면 factor를, 배수라면 multiple을, 둘 다 아니라면 neither를 출력한다. www.acmicpc.net 문제 설명 해당 값이 배수인지 약수인지 구별하여 출력하는 문제입니다. 문제 풀이 너무나 쉬운 문제입니다. 크게 설명하지는 않겠습니다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true){ int first = sc.nextInt(); int secon..
문제 번호 27433번 : 칸토어 집합 - JAVA [자바](파일의 끝에서 입력을 멈춘다.)
문제 번호 27433번 : 칸토어 집합 - JAVA [자바](파일의 끝에서 입력을 멈춘다.)
2023.03.31https://www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 문제 설명 재귀를 이용하여 '-'라는 문자열을 해당 규칙에 맞게 출력하는 문제입니다. 총 3의 n승의 문자가 출력되고 3을 기준으로 나눠 중간 문자열은 빈값으로 출력해야 합니다. 문제 풀이 백준 단계별 문제가 계속 변하면서 더 어려운 문제를 먼저 풀었습니다. https://kkungchan.tistory.com/303 문제 번호 2447번 : 별 찍기 - JAVA [자바] https://www.a..
문제 번호 27433번 : 팩토리얼 2 - JAVA [자바]
문제 번호 27433번 : 팩토리얼 2 - JAVA [자바]
2023.03.30https://www.acmicpc.net/problem/27433 27433번: 팩토리얼 2 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 설명 재귀를 이용하여 팩토리얼을 구현하는 문제입니다. 문제 풀이 사실 재귀를 이용해 팩토리얼을 구현하는 것은 어렵지 않습니다. 하지만 이 문제에는 함정이 있습니다. n이 0부터 20까지 라는 것입니다. 얼핏 보면 숫자가 작아보이지만 팩토리얼로 계산하면 굉장히 큰 숫자가 됩니다. 그래서 자료형을 int가 아닌 long으로 해주어야 합니다. import java.util.Scanner; public class Number_27433 { public static void main(String[] ..
문제 번호 11729번 : 하노이 탑 이동 순서 - JAVA [자바]
문제 번호 11729번 : 하노이 탑 이동 순서 - JAVA [자바]
2023.03.30https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제 설명 하노이 탑을 이동하는 순서를 재귀를 사용하여 출력하는 문제입니다. 문제 풀이 재귀는 정말 어려운거 같습니다. 하노이 탑은 유명한 재귀 문제임으로 알아두도록 합시다. 이 문제의 핵심은 위에 가장 아래 탑을 옮기기 위해 어떤 행동을 해야 하는 지를 생각하는 것입니다. 위와 같은 하노이탑이 있다고 가정해 보겠습니다. 3번 탑을 옮기기 위해서는 어떤 행위를 해야하나요? 물론 1번을..
문제 번호 2447번 : 별 찍기 - JAVA [자바]
문제 번호 2447번 : 별 찍기 - JAVA [자바]
2023.03.29https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 문제 설명 별 찍기 문제입니다. 숫자를 받고 해당 개수의 해당하는 가로세로의 별 찍기를 재귀로 구현합니다. 문제 풀이 저한테 이번 문제는 정말 어렵게 다가왔습니다. 정답률은 정말 높은데 저는 이 문제 때문에 며칠을 태웠는지 모르겠습니다. 문제도 거의 답보고 외운 수준이라 제가 풀었다고 말하기도 조금 민망합니다. 하지만 다음에 같은 문제를 만났을 때 어떤 식으로 접근해야 ..
문제 번호 18870번 : 좌표 압축 - JAVA [자바]
문제 번호 18870번 : 좌표 압축 - JAVA [자바]
2023.03.09https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제 설명 좌표 압축 문제입니다. 문제만 봐서는 사실 정확하게 어떤 값을 출력하는 건지 알기가 쉽지 않습니다. 간단히 설명하면 각 원소의 순위를 매기는 것이라고 생각하면 됩니다. 첫 번째 예제를 보면 -10이 제일 작은 값임으로 0을 가지고 -9가 두 번째로 작은 값임으로 1을 가집니다. 4는 2개가 동시에 3을 가지게 됩니다. 이렇게 순위를 매기..