전체 글
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에 더해..
투 포인터
투포인터 알고리즘 동작 흐름 배열에서 두 지점을 가리키는 포인터를 만들어 배열을 검색하는 알고리즘이다. 투 포인터를 사용하는 주된 이유는 시간복잡도를 낮추기 위함이다. 투 포인터 알고리즘에서 포인터 2개를 배치하는 방식에 2가지 경우가 있다. 1) 두 포인터가 배열의 시작과 끝에서 마주보며 진행하는 경우 2) 두 포인터가 배열의 시작에서 같이 방향으로 진행하는 경우 1) 두 포인터가 배열의 시작과 끝에서 마주보며 진행하는 경우 N개의 원소를 가진 배열 arr에서 합이 M인 경우를 찾는다고 해보자. (N, M은 정수) 하나의 포인터는 배열의 첫번째 원소, 나머지 포인터는 배열의 마지막 원소를 가리킨다. 두 포인터는 서로 마주 보며 이동한다. 두 포인터가 만나거나, 가리키는 원소의 합이 M이 될 때까지 이동..
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..