PS
BOJ 1850 최대공약수 [Java]
BOJ 1850 최대공약수 - 문제 링크 https://www.acmicpc.net/problem/1850 - 문제 해설 처음에는 굉장히 막막하였다. 문제 예제들의 최대공약수를 생각해보면서 접근 방법이 떠올랐다. 문제 예제들에 유클리드 호제법을 이용해보면 된다. 111과 1111의 경우 1111=111x10 + 1, 111=111x1 + 0 이다. 그러므로 최대공약수는 1이다. 111과 111111의 경우 111111=111x1001 + 0 이다. 그러므로 최대공약수는 111이다. 1로 이루어진 수들끼리의 최대공약수는 모두 1로 이루어져있다는 사실을 추론할 수 있다. 입력 받는 데이터 A, B는 두 자연수 M, N을 이루는 1의 갯수이고, 그러므로 두 자연수 A, B의 최대공약수를 구하면 그것이 M, N..
![BOJ 2609 최대공약수와 최소공배수 [Java]](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdna%2FbgeZBz%2Fbtrax8Hcq2Z%2FAAAAAAAAAAAAAAAAAAAAAPl6MiLGMtzmG0ZD70CnoaNKEptBcV8GtFQNqlofQfRK%2Fimg.png%3Fcredential%3DyqXZFxpELC7KVnFOS48ylbz2pIh7yKj8%26expires%3D1756652399%26allow_ip%3D%26allow_referer%3D%26signature%3DQ7uG3rFgEysAxUj3zb2ygYk1ji0%253D)
BOJ 2609 최대공약수와 최소공배수 [Java]
BOJ 2609 최대공약수와 최소공배수 - 문제 링크 https://www.acmicpc.net/problem/2609 - 문제 해설 최대공약수와 최소공배수를 구하는 문제이다. 유클리드 호제법을 이용하면 풀 수 있다. 유클리드 호제법이 무엇인지 알아보자. 최대공약수를 구하는 알고리즘인데, 두 자연수 m, n (m > n)이 있다고 하자. 이 때, m을 n으로 나눈 나머지를 r이라고 하면, m과 m의 최대공약수가 n과 r의 최대공약수와 같다는 것이 유클리드 호제법이다. 이 성질을 이용하면 n을 r로 나눈 나머지 r'을 구하고, 다시 r을 r'로 나눈 나머지 r''을 구하고, 다시 r'을 r''로 나눈 나머지를 구하는 과정을 계속 반복해서 나머지가 0이 되었..
BOJ 2003 수들의 합 2 [Java]
BOJ 2003 수들의 합2 - 문제 링크 https://www.acmicpc.net/problem/2003 - 문제 해설 전형적인 투포인터 알고리즘을 이용할 수 있는 문제이다. 2중 for문을 이용하면 시간 복잡도가 O(N^2)으로 제한 시간을 맞출 수 없지만, 투 포인터를 이용하면 O(N)으로 시간이 충분하다. 시작점을 가리키는 포인터를 start, 끝 점을 가리키는 포인터를 end, 포인터가 가리키는 두 원소의 합을 sum, 찾고자 하는 경우의 갯수를 cnt라고 하자. 1) 두 원소의 합이 M이면 구하고자 하는 경우를 찾았으니 cnt를 1 더해준다. start가 가리키는 원소의 값을 sum에서 빼주고 start를 1 더해준다. end를 1 더해주고 더해진 end가 가리키는 원소의 값을 sum에 더해..
BOJ 1158 요세푸스 문제 [Java]
BOJ 1158 요세푸스 문제 - 문제 링크 https://www.acmicpc.net/problem/1158 - 문제 해설 ArrayList를 이용하여 풀었다. 제거할 사람의 인덱스가 k만큼 계속 더해진다. 인덱스의 시작이 0이고 처음 제거할 사람의 인덱스는 k-1이므로 인덱스 초기값을 -1로 설정했다. k씩 더하다가 인덱스가 리스트의 마지막 인덱스를 넘어가면 다시 처음 인덱스 값으로 돌아가서 작동해야한다. 이 과정 처리를 나머지(mod) 연산을 이용하여 해결하였다. - 코드 보기 package 큐; import java.io.*; import java.util.*; public class BOJ_1158 { static int n, k; public static void main(String[] ar..
BOJ 1406 에디터 [Java]
BOJ 1406 에디터 - 문제 링크 https://www.acmicpc.net/problem/1406 - 문제 해설 java 내의 LinkedList를 이용하여 풀었다. ListIterator는 Iterator와는 다르게 양방향으로 원소에 접근이 가능하기에 ListIterator를 이용하였다. 18-19줄에서 커서를 맨 뒤로 보내는 작업을 먼저 해주고, 그 후 각 명령이 들어오면 그에 맞게 동작하도록 구현하였다. ListIterator 내부에 현재 보고 있는 위치를 가리키는 cursor가 있어서 메소드를 활용하면 쉽게 해결할 수 있는 문제였다. 문제에서 사용한 메소드들만 정리해보겠다. - hasNext() : iterator가 리스트를 순방향으로 순회할 때 다음 원소가 있으면 true를 없으면 fals..