백준

백준 1934번 자바

1. 문제 https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 2. 유클리드 호제법? 역시 자세한 설명은 네이버가 잘해준다. https://terms.naver.com/entry.naver?docId=2073670&cid=47324&categoryId=47324 유클리드 호제법 [ 1. 교과서 속 주개념] [ 1) 유클리드 호제법] 두 정수 a, b의 최대공약수를 G(a, b)라고 하자. 정수 a, b, q r (b ≠ 0)에 ..

백준 11689번 자바

1. 문제 https://www.acmicpc.net/problem/11689 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 접근 방식 오일러의 피를 활용해 푸는 문제다. 해당 개념에 대한 설명은 역시 네이버가 잘해준다. https://terms.naver.com/entry.naver?docId=5668098&cid=60205&categoryId=60205 오일러의 피 함수 8월 14일의 수학 오일러의 피(\displaystyle \varphi) 함수는 \displaystyle n보다 작은 자연수 중에서 \displaystyle n과 서로소인 수의 개..

백준 1016번 자바 ☆

1. 문제 https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 2. 접근 방식 어떤수 X는 1보다 큰 제곱수로 나눠지지 않는다 => 소수의 제곱으로도 안나눠지면 제곱 ㄴㄴ수다. 이유는 아래에 다시 설명 하겠다. 먼저 에라토스테네스의 체로 소수를 구해준다. 해당 인덱스의 소수를 제곱해주고 제곱수를 min과 나눠준다. 이때 수가 나누어 떨어진다면 그대로 다음 반복문으로 이동하고 나누어 떨어지지 않는다면 divVal의 값을 +1해준다. ..

백준 1747번 자바

문제 https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 1. 접근 방식 먼저 소수는 에라토스테네스의 체를 이용해 구해주고 팰린드롬수를 어떻게 찾느냐에서 방법이 크게 두가지로 갈린다. 첫번째는 많은 블로그에서 기술한 문자 비교방식이다.(투포인터를 활용해 시작과 끝값을 하나씩 비교해준다) 두번째는 내가 사용한 방식인데 10으로 나눈 나머지를 StringBuilder를 활용해 거꾸로 더해주는 방식이다. 수의 범위가..

백준 1541번 자바

문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 1. 접근 방식 문제 이해에 많이 헤맸다. 부호 '-' 부터 다음 '-'부호가 나오기 전까지 괄호를 치면 괄호안의 값들은 셈이 된 상태에서 음수로 변경 되기 때문에 가장 작은 값이 나올 수 있다. 그렇기 때문에 배열의 마지막부터 '-'를 탐색하면서 해당 값들을 빼주면 최소값이 나온다. 다만 마지막부터 탐색하기 때문에 앞쪽에 '+' 기호만 존재할 경우가 생기기 때문에 해당 값만 더해주면 ..

백준 1931번 자바☆

문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 1. 접근 방식 역시 그리디 관련 문제는 처음 접근이 가장 중요한것 같다.. 처음 접근을 회의 시작시간을 정렬하는 방법으로 했는데 결국 점점 산으로가 포기했다. 정답은 회의 종료시간 순으로 정렬을 시키고 종료시간이 같을 경우 시작시간 순으로 정렬을 해야한다. 해당 접근만 주의하면 크게 어렵지 않은 문제다. 2. 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.uti..