JAVA - 백준 [BAEK JOON]
[백준] 2447번 : 별 찍기 - 10 - JAVA [자바]
[백준] 2447번 : 별 찍기 - 10 - JAVA [자바]
2020.05.16www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 � www.acmicpc.net 문제 알고리즘 [접근 방법] 필자가 이 문제를 푼 것은 좀 오래전이지만 근래 작성한 문제 중에 가장 설명하기 어려운 문제였다. 어떻게 설명해야하는지 고민을 좀 많이 했던지라.. 또한 규칙은 쉽게 보이지만 이를 구현하자니 필자도 꽤 고민했던 문제이기도 했다. (근데 정답률이 어떻게 50% 가까이 되는지 정말 신기하다.. 막상 질문하는 사람은 많은데..?) 여하튼 차근차근 한 번 풀어..
[백준] 10870번 : 피보나치 수 5 - JAVA [자바]
[백준] 10870번 : 피보나치 수 5 - JAVA [자바]
2020.05.13www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 �� www.acmicpc.net 문제 재귀에 대한 이해만 있다면 매우 간단한 문제다! 물론 재귀함수를 쓰지 않고 배열로도 가능하니 한 번 같이 보자. 알고리즘 [접근 방법] 이 문제의 경우에는 사실 문제설명에서 다 주었다. 피보나치 수 부터 설명을 하자면 첫번째 항이 0 부터 시작할 경우 첫번째 항은 0, 두번째 항은 1부터 시작하여, 다음 항은 직전 항과 직전 항의 직전 항의 합으로 이루어진 수열을..
[백준] 10872번 : 팩토리얼 - JAVA [자바]
[백준] 10872번 : 팩토리얼 - JAVA [자바]
2020.05.11www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 재귀에 대한 문제를 처음 접할 때 가장 먼저 접하는 문제중 하나가 아닐까 싶다. 매우 쉬운 문제이니 어렵지 않게 풀 수 있을 것이다. 알고리즘 [재귀] 재귀를 프로그래밍으로 처음 접하는 분들은 수학적으로는 익숙하더라도 코딩에서는 매우 생소할 수도 있다. 컴퓨터에서 재귀는 자신을 정의할 때 자기 자신을 재 참조하는 방법을 재귀라고 한다. 그림으로 보면 아주 간단하게 아래와 같다. 이런식으로 func 이라는 함수를 정의할 때, func 함수 안에 func 을 호출하고 그 호출 한 func 안에 func 을 참조하..
[백준] 9020번 : 골드바흐의 추측 - JAVA [자바]
[백준] 9020번 : 골드바흐의 추측 - JAVA [자바]
2020.05.05https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. www.acmicpc.net 문제 소수를 이용한 문제다. 문제는 그리 어렵지 않으니 한 번 보면 금방 이해될 것이다. ※ 주의할 점 2보다 큰 짝수가 주어질 때..
[백준] 1002번 : 터렛 - JAVA [자바]
[백준] 1002번 : 터렛 - JAVA [자바]
2020.05.04https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 문제 필자가 처음 문제를 볼 때 뭔 말인가 싶었다.. 그래도 이해만 한다면 매우매우 쉬운 문제이니 차근차근 풀어보자. 알고리즘 [풀이 방법] 일단 문제부터 이해해보자. 문제에서의 조규현과 백승환을 각각 A, B 라고 한다면 더 이해하기 쉽다. 좌표상에서 A터렛의 위치 (𝑥₁, 𝑦₁) 가 주어지고, B터렛의 위치 (𝑥₂, 𝑦₂) 가 주어진다. 그리고 마린(류재명)을 C라고 할 때, A 와 B가 자신의 위치로부터의 거리를 각각 계산한 것이다. 즉, A로..
[백준] 3053번 : 택시 기하학 - JAVA [자바]
[백준] 3053번 : 택시 기하학 - JAVA [자바]
2020.05.03https://www.acmicpc.net/problem/3053 3053번: 택시 기하학 문제 19세기 독일 수학자 헤르만 민코프스키는 비유클리드 기하학 중 택시 기하학을 고안했다. 택시 기하학에서 두 점 T1(x1,y1), T2(x2,y2) 사이의 거리는 다음과 같이 구할 수 있다. D(T1,T2) = |x1-x2| + | www.acmicpc.net 문제 맨해튼 거리(Manhattan distance) 에 대해 알지 못한다면 이게 뭔 말이지 싶을 것이다. (필자도 배웠던 기억이 있었으나 하도 오래전에 배운 내용이라 거의 까먹어서 다시 정의를 찾아보았다..) 참고로 택시 기하학은 맨해튼 거리의 다른 말이다. 그럼 택시 기하학을 한 번 알아보자. (매우 쉽다) 택시 기하학 (맨해튼 거리 , Manhat..
[백준] 4153번 : 직각삼각형 - JAVA [자바]
[백준] 4153번 : 직각삼각형 - JAVA [자바]
2020.05.02https://www.acmicpc.net/problem/4153 4153번: 직각삼각형 문제 과거 이집트인들은 각 변들의 길이가 3, 4, 5인 삼각형이 직각 삼각형인것을 알아냈다. 주어진 세변의 길이로 삼각형이 직각인지 아닌지 구분하시오. 입력 입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다. 출력 각 입력에 대해 직각 삼각형이 맞다면 "right", 아니라면 "wrong"을 출력한다. 예제 입력 1 복사 6 8 www.acmicpc.net 문제 매우 간단한 문제다! ※ 주의할 점 직각삼각형 조건을 구할 때 어느 변이 대각선인지는 알 수 없다. 그러므로 3개의 조건 중 맞는 ..
[백준] 3009번 : 네 번째 점 - JAVA [자바]
[백준] 3009번 : 네 번째 점 - JAVA [자바]
2020.05.01https://www.acmicpc.net/problem/3009 3009번: 네 번째 점 문제 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. 입력 세 점의 좌표가 한 줄에 하나씩 주어진다. 좌표는 1보다 크거나 같고, 1000보다 작거나 같은 정수이다. 출력 직사각형의 네 번째 점의 좌표를 출력한다. 예제 입력 1 복사 30 20 10 10 10 20 예제 출력 1 복사 30 10... www.acmicpc.net 문제 매우 간단한 문제다! ※ 주의할 점 각 점의 좌표는 3개가 주어진다 3가지 방법을 이용하여 풀이한다. 기본 알고리즘은 배열을 이용하여 풀 것이다. 다만 입력을 달리하여 풀어보려 한다. 입력은 Scanner 와 Buffere..
[백준] 1085번 : 직사각형에서 탈출 - JAVA [자바]
[백준] 1085번 : 직사각형에서 탈출 - JAVA [자바]
2020.04.28https://www.acmicpc.net/problem/1085 1085번: 직사각형에서 탈출 첫째 줄에 x y w h가 주어진다. w와 h는 1,000보다 작거나 같은 자연수이고, x는 1보다 크거나 같고, w-1보다 작거나 같은 자연수이고, y는 1보다 크거나 같고, h-1보다 작거나 같은 자연수이다. www.acmicpc.net 문제 매우 간단한 문제다! 2가지 방법을 이용하여 풀이한다. 이 문제는 알고리즘을 따로 설명하지 않아도 될 정도로 매우 쉬운 문제다. 다만 입력방법만 달리하여 Scanner 와 BufferedReader 을 통한 방법으로 보여줄 것이다. 알고리즘은 간략하게만 설명하겠다. 알고리즘 주어지는 변수는 총 4개다. 한수의 위치를 나타내는 x, y 그리고 직사각형 오른쪽 위 꼭짓점..
[백준] 4948번 : 베르트랑 공준 - JAVA [자바]
[백준] 4948번 : 베르트랑 공준 - JAVA [자바]
2020.04.24https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) n이 주어졌을 때, n보다 크고, 2n보 www.acmicpc.net 문제 입력이 주어질 때 N ~ 2N 사이에 몇 개의 소수가 있는지 구하는 문제다. 그리 어려운 문제가 아니니 같이 풀어보도록 하자...