carsumin devlog 🍀

유클리드 호제법 (Euclidean Algorithm) 최대공약수, 최소공배수 (GCD, LCM)최대공약수 구한 뒤 두 수의 곱을 최대공약수로 나누면 최소공배수 구할 수 있음두 자연수의 곱 = 최대공약수 * 최소공배수∴ 최소공배수 = 두 자연수의 곱 / 최대공약수 만약 A, B라는 두 수가 있다면 최소공배수(LCM)는 아래와 같다LCM = A*B / GCD

https://www.acmicpc.net/problem/10815  이진탐색을 사용하지 않고 배열을 일일이 비교하면 시간초과가 뜬다.이진탐색(Binary Search)를 사용해서 풀어야 하는 문제 (https://marginata.tistory.com/150)풀이 1은 System.out.print() 를 이용하여 일일이 출력을 했고, 풀이 2는 StringBuilder를 사용하여 출력을 했다. 성능면에서 StringBuilder를 사용하는 것이 훨씬 더 빠르다. 풀이 1 import java.io.*;import java.util.*;public class Main{ static int[] arr; public static void main(String[] args) throws IOExc..

이진탐색 (Binary Search) 중앙값 (mid) 지정해서 비교하는 탐색이진탐색을 하려면 정렬이 된 상태에서 수행해야 함   이진탐색의 시간복잡도 O(logn)의 시간복잡도를 가지고 있다.선형탐색과 비교했을 때 데이터 수가 증가함에따라 기하급수적으로 증가하지 않음 (그래프 참고)

BFS (Breadth-First Search) 시작 노드에서 가장 가까운 노드부터 시작하여 모든 노드 광범위하게 탐색첫번째 floor부터 시작해서 해당 floor의 모든 노드 방문할 때까지 수평 이동한 번 거친 노드 순서 저장한 후 다시 꺼내는 FIFO 주로 Queue로 구현 DFS (Depth-First Search) 시작 노드와 직접 연관된 하위 노드의 끝까지 모두 탐색한 후 다음 하위 노드 탐색경로 하나의 모든 floor 탐색한 뒤 그 다음 경로의 모든 floor 탐색하는 순서주로 재귀호출이나 Stack 명시하는 방법으로 구현

https://www.acmicpc.net/problem/2908   문자열을 뒤집는 reverse() 를 알면 좀 더 쉽게 풀 수 있는 문제다른 사람 풀이를 보니 한번에 문자열을 입력받아 공백기준으로 분리해서 처리했는데 이게 훨씬 좋은 코드같다.나는 변수를 여러번 입력받고 각각 뒤집는 과정을 거쳐서 코드가 지저분해졌다.split으로 분리해서 배열로 처리하면 최댓값도 Max함수로 간단히 구할 수 있다. 내 풀이import java.util.*;class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); String a = sc.next(); String b = sc..

https://www.acmicpc.net/problem/10809   문자열이 처음 나타난 위치를 계산하는 게 헷갈림알파벳 (A-Z) 이 총 26개인 것을 알아야 풀 수 있는 문제알파벳 개수만큼 배열을 만들고, 입력값의 원소와 비교'처음 등장하는 위치' 라는 출력 조건이 있기 때문에, 모든 알파벳 배열을 -1로 초기화한다.예를 들어 c가 'a'라면 c-'a'는 0이므로 arr[0]은 'a'의 위치를 가리킨다.마찬가지로 c가 'b'라면 c-'a'는 1이므로 arr[1]은 'b'의 위치를 가리킨다.즉 , arr[c-'a']는 문자 c가 처음 등장한 위치를 가리킨다. 풀이import java.io.*;class Main{ public static void main(String[] args) throws..

https://www.acmicpc.net/problem/10811  배열 인덱스 주의할 것 (첫번째 바구니는 1, 두번째 바구니는 2... 배열은 0부터 시작)왼쪽으로부터 i번째부터 j번째 바구니까지 순서를 역순으로 만든다 -> i 내 풀이 import java.util.*;class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int[] arr = new int[N]; for(int i=0; i

https://www.acmicpc.net/problem/3052   배열과 HashSet으로 풀이할 수 있음배열로 입력받아서 이중for문을 돌려서 값이 같은 경우 cnt를 증가시키고, cnt가 0이면 값이 다르다고 볼 수 있기 때문에 diff를 카운트해서 서로 다른 나머지를 체크했다문제는 입력값이 10개뿐이였지만 입력개수가 많아지는 경우 효율성이 떨어지기 때문에 다른 풀이 방법을 찾아봐야겠다  내 풀이 import java.util.*;class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int[] arr = new int[10]; int diff = 0;..

https://www.acmicpc.net/problem/10813   앞서 풀었던 공넣기 문제를 응용한 문제라 어렵지 않게 풀 수 있다swap 알고리즘을 이용한 문제배열의 인덱스 주의해서 풀이 내 풀이 import java.util.*;class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); //가지고 있는 바구니 개수 int N = sc.nextInt(); int[] arr = new int[N]; //바꿀 횟수 int M = sc.nextInt(); for(int i=0; i

https://www.acmicpc.net/problem/10810  여러번 읽고 문제를 이해했다해결방법 자체는 쉬운데 문제를 이해하는 데 시간이 걸림이중 for문을 사용할 때 index 범위를 주의해야함예를 들어서 문제에서 말하는 2번 바구니부터 5번 바구니는 배열로 따지면 1번부터 4번일 것따라서 반복문을 실행할 때 -1을 해야함 내 풀이 import java.util.*;class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); //바구니를 N개 가지고 있음 int n = sc.nextInt(); int[] arr = new int[n]; ..