개발자꿀꿀이

문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 풀이 정확하게 이분탐색 또는 N분탐색 문제 유형을 이해하는 건 어렵다. 이문제도 풀이를 보기 전까진 왜 이분탐색으로 풀어야하는지 감을 못잡았다. 해설을 찾아보니 이문제는 공유기를 두는 집에 집중하는..

문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15..

문제 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다..

문제 ( n ) 의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오. ( m ) 풀이 팩토리얼의 0의개수를 구하는 문제의 풀이를 참고하여 풀었다. 백준 1676 (팩토리얼 0의 개수) 백준 1676 (팩토리얼 0의 개수) 문제 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 풀이 문제의 N 의 범위가 ( 0 ≤ N ≤ 500 ) 이기 때문에 Integer 과 Long 의 범위를 넘어 오버플로 conpulake.tistory.com 위 문제에서는 2가 부족하지 않아서 5의 개수만 구해도 됐지만 조합의 경우에서는 2가 부족한 경우가 있었다. 그래서 2와 5의 개수를 각각 구한뒤 더 적은 것의 개수가 뒤에서 부터 0의 개수다. import java.io.Bu..

문제 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 풀이 문제의 N 의 범위가 ( 0 ≤ N ≤ 500 ) 이기 때문에 Integer 과 Long 의 범위를 넘어 오버플로가 발생하게 된다. 다른방법을 찾았다. 5! = 120 = 12 x 10 10! = 3628800 = 36288 x 10 x 10 15! = 1307674368000 = 1307674368 x 10 x 10 x 10 20! = 2432902008176640000 = 243290200817664 x 10 x 10 x 10 x 10 25! = 15511210043330985984000000 = 15511210043330985984 x 10 x 10 x 10 x 10 x 10 x 10 이렇게..

문제 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. 풀이 소인수는 소수를 찾아서 나눠줘야한다는 생각 때문에 소수가 맞는지를 판단하고 나눠 주는 방식을 하니 시간초과라는 결과가 나왔다. 하지만 2부터 증가하면서 나눠주면 이미 소수 위주의 숫자만 걸릴 수 밖에 없다. 그래서 2부터 증가하면서 N 이 1 이 될때까지 나눠주는 방식으로 풀었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static StringBuilder sb = new StringBuilder(); public static void main(String[] args) ..

문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오. 풀이 인터넷 풀이를 보면 10만까지의 숫자들 중 미리 소수를 찾고 푸는 방식이 많았다. 단순하게 생각했다. 3보다 큰 자연수들 중에서 짝수 소수는 존재하지 않는다. 해당 수가 소수가 맞다면 N..

문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 풀이 문제 자체는 소수를 찾는 다는 문제라 쉽지만.. 알고리즘을 기록해두기 위해 풀었다. 소수를 찾는 방법은 세가지다. 반복문을 통해 2 부터 (N-1) 까지 약수가 없으면 소수 반복문을 통해 2 부터 (N/2) 까지 약수가 없으면 소수 반복문을 통해 2 부터 N 제곱근까지 약수가 없으면 소수 이 중에서 3번의 방식이 시간복잡도가 가장 짧아서 3번으로 문제를 풀었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queu..

문제 -2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001 등이다. 10진법의 수를 입력 받아서 -2진수를 출력하는 프로그램을 작성하시오. 풀이 직접 손으로 풀어보니 마지막 나머지가 1이 될때 끝나는 것을 보았다. 10진법을 2진법을 바꾸는 상황에서 보통의 자연수 진법에서는 0이 되면 끝나게 재귀코드를 짰던것에서 1에서도 재귀함수를 끝내는 조건을 두게 하여 풀었다. import java.io.BufferedReader; import jav..

문제 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다. 풀이 입력 된 숫자의 최대 공약수를 유클리드 알고리즘을 통해 찾는다. [ GCD(3, 6) = 2 ] 찾아진 최대공약수 만큼의 1을 입력시켜준다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; public c..