최대공약수, 최소공배수를 JAVA로 구해보자(유클리드 호제법, BigInteger)

들어가기 전에 코딩테스트 문제를 풀다보면 종종 최대공약수 혹은 최대공배수를 구할 때가 있다. 가장 대표적인 문제가 아래에 있는 최소공배수문제이다. https://www.acmicpc.net/problem/13241 13241번: 최소공배수 정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다. 예: 10은 5의 배수이다 (5*2 = 10) 10은 10의 배수이다(10*1 = 10) 6은 1의 배수이다(1*6 = 6) 20은 1, 2, 4,5,10,20의 배수이다. 다 www.acmicpc.net 이럴때 어떤 알고리즘을 사용해야하는지, 그리고 간단하게 해결할 수는 없는지 알아보도록 하자. 개념을 알아보자 약수란?? 약수란 어느 한 숫자를 0을 제외한 다른 숫자로 나누었을 ..

• format_list_bulleted JAVA
• · 2024. 2. 11.
• textsms

LinkedList vs ArrayDeque 효율성 비교(with Deque)

아니 LinkedList로는 안풀리는데 ArrayDeque로는 풀린다고?? 오늘는 쉬면서 알고리즘 문제를 풀고싶어서 간단해보이는 실버 3문제인 풍선 터뜨리기 문제를 풀어보았다. https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 간단히 요약하자면 위의 문제는 Deque를 사용하면 되는 구현 문제였다. 그래서 Deque를 사용해서 문제를 해결하고자 했고 제출한 코드 다음과 같다. import java.io.BufferedReader..

• format_list_bulleted JAVA
• · 2024. 2. 10.
• textsms

[백준 - 1092][Gold 5] - 배 (JAVA)

문제 지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다. 각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 ..

• format_list_bulleted 알고리즘 문제 풀이/해설
• · 2024. 2. 9.
• textsms

[백준 - 5052][Gold 4] - 전화번호 목록 (JAVA)

문제 링크 https://www.acmicpc.net/problem/5052 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 입력 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번..

• format_list_bulleted 알고리즘 문제 풀이/해설
• · 2024. 2. 8.
• textsms

[백준 14226][Gold 4] - 이모티콘 (JAVA)

문제 링크 https://www.acmicpc.net/problem/14226 문제 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 화면에 있는 이모티콘 중 하나를 삭제한다. 모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없..

• format_list_bulleted 알고리즘 문제 풀이/해설
• · 2024. 2. 7.
• textsms

[백준 1700][Gold 1] - 멀티탭 스케줄링(JAVA)

문제 링크 https://www.acmicpc.net/problem/1700 문제 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다. 예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면, 키보드 헤어드라이기 핸드폰 충전기 디지털 카메라 충전기 키보드 헤어드라이기 키..

• format_list_bulleted 알고리즘 문제 풀이/해설
• · 2024. 2. 5.
• textsms