프로그래밍/알고리즘6 유클리드 호제법 유클리드 호제법 유클리드 호제법(Euclidean algorithm)은 두 수의 최대공약수(GCD)를 효율적으로 구하는 고대의 알고리즘입니다. 이 방법은 두 수를 계속해서 나눗셈과 나머지 연산을 반복함으로써 최대공약수를 찾는 방식입니다. *코딩테스트 준비용 알고리즘 학습을 위한 것이기 때문에 수학적 증명은 생략하겠씁니당 유클리드 호제법의 과정 다음과 같은 단계로 유클리드 호제법을 통해 최대 공약수를 구할 수 있습니다.1. 두 수 a, b를 MOD2. b와 나머지로 MOD3. 나머지가 0이 되는 순간의 b가 최대 공약수 최소공배수 lcm는 gcd를 이용하여 구하는 것이 일반적입니다. 아래에 반복문을 이용하여 최소공배수와 최대공약수를 구하는 함수를 작성하였습니다.import java.io.IOExc.. 2024. 10. 12. 비트마스크 알고리즘/ 집합 구현 BitMask(비트마스크) 비트마스크는 컴퓨터 과학에서 사용되는 개념으로, 비트 연산을 통해 정보를 효율적으로 처리하는 기술입니다. 비트마스크는 이진수로 표현된 비트의 상태를 이용하여 여러 가지 작업을 수행할 수 있습니다. 특정 비트 위치에 값을 설정하거나 비트를 확인하는 등의 작업이 가능합니다. 비트마스크는 주로 메모리와 연산을 효율적으로 다룰 때 사용되며, 특히 비트 연산자 AND, OR, XOR 등을 활용하여 다양한 연산을 수행합니다.비트마스크는 알고리즘 및 데이터 구조에서 자주 사용되며, 특히 상태나 특정 조건을 효율적으로 표현하고 처리하는 데에 활용됩니다. 비트 연산자 AND(&): 두 비트가 모두 1일 때만 결과가 1이 되는 연산. 특정 비트를 0으로 설정하거나 특정 비트를 확인할 때 사용ex.. 2024. 1. 28. 동적계획법/다이나믹 프로그래밍(Dynamic Programming) 동적 계획법: 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법 *이미 했던 계산은 재활용하여 사용하기 -Top-down 형식 재귀로 구현, 큰 문제를 작은 문제로 쪼개나가면서 해결(memoization 활용) 아래 코드는 피보나치를 구하는 함수를 top down 형식으로 구현한 것이다. int fib(int n){ if (n==1 || n==2) return 1; else if(f[n] > -1) //배열이 초기화 된 경우=이미 계산을 한 경우 return f[n]; else return f[n] = fib(n-2) + fib(n-1); } Top down 형식은 재귀 오버헤드가 발생할 수 있다. -Bottom up 형식 반복문으로 구현.. 2022. 11. 9. 순열과 조합 1)순열 import java.util.*; public class Main { public static void solution(char []item, char []bucket, int k) { if( k == 0 ) { //다 뽑았으면 출력 for(int i=0; i 2022. 10. 12. 멱집합(PowerSet) a가 들어가거나 안 들어가거나 b가 들어가거나 안 들어가거나 ... f가 들어가거나 안 들어가는 모든 경우의 수는 2^n이다.(n은 원소의 개수) pick이라는 boolean 배열을 두고 해당 인덱스에 원소를 뽑았을 경우 true, 안 뽑았을 경우를 false라고 두고 재귀적으로 구현했다. import java.util.*; public class Main { private static char data[] = {'a', 'b', 'c', 'd', 'e', 'f'}; private static boolean [] pick = new boolean[6]; private static int n = data.length; public static void main(String[] args){ powerSet(.. 2022. 10. 12. Counting Cells in Blob(Blob 셀 수 세기) 재귀를 이용하여 구현하였다. public class Main { //이차원 배열로 이미지 표현 static int arr[][] ={ {1,0,0,0,0,0,0,1}, {0,1,1,0,0,1,0,0}, {1,1,0,0,1,0,1,0}, {0,0,0,0,0,1,0,0}, {0,1,0,1,0,1,0,0}, {0,1,0,1,0,1,0,0}, {1,0,0,0,1,0,0,1}, {0,1,1,0,0,1,1,1}}; //상수로 컬러 표현 public static final int BackgroundColor = 0; public static final int ImageColor = 1; public static final int AlreadyCounted = 2; public static void main(Strin.. 2022. 10. 12. 이전 1 다음
