Algorithm/백준 알고리즘
-
[JAVA] 1748번: 수 이어 쓰기1Algorithm/백준 알고리즘 2021. 7. 20. 11:39
문제 설명 1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다. 이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오. 1234567891011121314151617181920212223... 입력 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. 출력 첫째 줄에 새로운 수의 자릿수를 출력한다. 풀이 1. length변수를 선언하여 i가 length와 일치할 경우 length * 10을 해준다. => 2자릿수, 3자릿수.. 2. 자릿수가 증가함에 따라 자릿수당 해당 숫자가 위치해야함으로 cnt를 1증가 시켜준다. 3. 해당 자리만큼 temp에 cnt를 더해준다. 코드 /* - 1부터 N까지의 수를 이어서 쓰면 다음과 같이 ..
-
[JAVA] 3085번: 사탕 게임Algorithm/백준 알고리즘 2021. 7. 19. 13:49
문제 설명 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다. 다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록..
-
[JAVA] 2309번: 일곱 난쟁이Algorithm/백준 알고리즘 2021. 7. 19. 10:32
문제 설명 왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다. 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오. 입력 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. 출력 일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를..
-
[JAVA] 1929번: 소수 구하기Algorithm/백준 알고리즘 2021. 7. 18. 20:31
문제 설명 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 에라토스테네스의 체 k=2부터 루트N이하까지 반복하여 자연수들 중 k를 제외한 k의 배수들을 제외시킨다. k=2일 경우, 2를 제외한 2의 배수를 모두 지워준다. k=3일 경우, 3을 제외한 3의 배수를 모두 지워준다. k=4일 경우, 이미 k=2에서 제외되었기 때문에 넘어간다. k=5일 경우, 5를 제외한 5의 배수를 모두 지워준다. 위와같은 방식을 반복하여 k=루트N까지 반복하는 방법이다. 코드 import ..
-
[JAVA] 17427번: 약수의 합2Algorithm/백준 알고리즘 2021. 7. 18. 18:24
문제 설명 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다. 자연수 N이 주어졌을 때, g(N)을 구해보자. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 첫째 줄에 g(N)를 출력한다. 풀이 1. N의 최댓값이 1,000,000이므로 1부터 n까지 약수를 구한 후 합을 구하면 시간초과가 날 것이다. 2. 1부터 n까지의 약수를 적어보고 약수들의 갯수를 보면 규칙을 ..
-
[JAVA] 1935번: 후위 표기식2Algorithm/백준 알고리즘 2021. 7. 12. 17:42
문제 설명 후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오. 입력 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. (3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C ...이 주어진다, 그리고 피연산자에 대응 하는 값은 정수이다) 출력 계산 결과를 소숫점 둘째 자리까지 출력한다. 코드 /* 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는..
-
[JAVA] 1929번: 소수구하기Algorithm/백준 알고리즘 2021. 7. 12. 15:01
문제 설명 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 풀이 1. 숫자의 √N까지 확인하는 방법을 사용하여 문제를 해결한다. 2. √N의 값은 N의 약수를 나열한 값들 중 중간에 위치한다. 따라서 2에서 부터 √N까지의 값을 검색한 이후의 값은 확인할 필요가 없다. 3. 시간복잡도는 O(√N)이 된다. 편리하게 계산하기위하여 값에 제곱을 곱하여 계산하였다. 코드 /* 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. */ import j..
-
[JAVA] 1934번: 최소공배수Algorithm/백준 알고리즘 2021. 7. 12. 12:50
문제 설명 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다. 두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000) 출력 첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다. 풀이 1. 최대공약수와 최소공배수문제를 참고해주세요. 코드 /* 두 자연수 A와 B에 대해서, A의..