본문 바로가기

Develop/Algorithm29

*** 조합(Combination) 조합은 n 개의 숫자 중에서 r 개의 수를 순서 없이 뽑는 경우를 의미한다. - https://ko.wikipedia.org/wiki/%EC%A1%B0%ED%95%A9 조합은 기호로 다음과 같이 나타낼 수 있다. ** 조합은 하나의 원소를 선택할 경우 + 하나의 원소를 선택하지 않을 경우 * n개 중에 m개를 뽑는 경우의 수를 구하는 신기한 풀이 (이해 필요) * class Test { public long solution(int N, int M) { M = Math.min(N - M, M); if (M == 0) return 1; long answer = solution(N - 1, M - 1); answer *= N; answer /= M; return answer; } } // 순열과 조합의 공식을.. 2022. 11. 25.
약수 개수 알고리즘 기본 구현 코드 public int countDivisors(int n) { int count = 0; for (int i = 1; i 2022. 11. 18.
유클리드 호제법을 이용한 최소공배수, 최대공약수 최대공약수 // 방법 1 public int getGCD(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a; } // 방법 2 public int getGCD(int a, int b) { if (b == 0) return a; return getGCD(b, a % b); } 최소공배수 public int getLCM(int a, int b) { return (a * b) / getGCD(a, b); } 2022. 11. 5.
이진 탐색(Binary Search) 이진 탐색은 순차 탐색보다 대부분의 경우에서 더 빠른 효율을 낼 수 있다. (찾으려는 값이 작으면, 순차 탐색이 더 적게 걸릴 수도 있다.) 순차 탐색은 보통 반복문을 이용하기 때문에, 시간복잡도 Big-O 기준 O(N)이다. 이진 탐색은 재귀를 통해 범위를 점점 좁혀나가는 방법으로, O(logN)이다. 다음 그림을 통해 이진 탐색에 대해 쉽게 파악할 수 있다. 다음은 이진 탐색을 구현하는 문제를 풀이한 코드들이다. 배열에서 num 값의 인덱스를 추출하는 문제이다. 1. while문 이용 import java.util.Arrays; import java.util.Scanner; class Main { private int solution(int target, int[] arr) { int answer =.. 2022. 11. 1.
동적계획법 - 2 x n 타일 문제 동적 계획법 풀이는 제일 먼저 점화식을 찾아라. ex) dp[n] = dp[n-1] + dp[n-2] 점화식을 찾는 방법은 수기로 직접 제일 작은 입력값을 넣어보면서, 특정 패턴 및 이전 값과 기존 값의 상관 관계를 파악하면 쉽게 찾을 수 있다. 2 x n 타일 문제 풀이 순서 1. 빈 리스트 만들기 (입력값에 따른) int[] dp = new int[num + 1]; 2. 초기값을 설정 dp[1] = 1; dp[2] = 2; 3. 점화식 기반으로 계산값 적용하기 for (int i = 3; i 동적계획법을 구현하는 기법에는 Top-down, Bottom-up 기법이 있다. 값을 캐시(Cache)에 메모(저장) 해놓고, 다시 그 값을 계산할 필요가 없이 풀이하는 것을 메모이제이션(Memoization)이.. 2022. 10. 31.
treeBFS - 깊이 우선 탐색 알고리즘 import java.util.*; public class Solution { public ArrayList bfs(tree node) { Queue queue = new LinkedList(); ArrayList values = new ArrayList(); queue.add(node); while(queue.size() > 0) { tree curNode = queue.poll(); values.add(curNode.getValue()); if(curNode.getChildrenNode() != null) { queue.addAll(curNode.getChildrenNode()); } } return values; } public static class tree { private String valu.. 2022. 10. 26.
treeDFS - 깊이 우선 탐색 알고리즘 import java.util.*; public class Solution { public ArrayList dfs(tree node) { ArrayList values = new ArrayList(); values.add(node.getValue()); if(node.getChildrenNode() != null) { for(int i = 0; i < node.getChildrenNode().size(); i++) { ArrayList curList = dfs(node.getChildrenNode().get(i)); values.addAll(curList); } } return values; } public static class tree { private String value; private Arr.. 2022. 10. 25.
개선된 거듭제곱 알고리즘 (해결 코드는 맨 아래 있으므로, 맨 아래를 참고) 평소 두 인자 a, b를 받고 a의 b제곱을 구하라 하면 간단하게 Math.pow() 메서드를 이용하거나, 다음과 같이 구현했을 것이다. class Solution { public long power(int base, int exponent) { if (exponent == 0) return 1; if (exponent == 1) return base; for (int i = 1; i < exponent; i++) { base *= base; } return base; } } 이 코드의 경우, 시간 복잡도는 Big-O 기준 O(n)이다. 좀 더 효율적으로 코드를 짜본다면, O(logN)까지 줄일 수 있다고 한다. 바로 분할 정복과 모듈러 곱셈 역원(Mo.. 2022. 10. 24.
소수 알고리즘 - 제곱근 & 에라토스테네스의 체 이용 소수는 1과 자기 자신으로만 나누어는 수이다. 예로 100을 들어보자. 100은 1, 2, 4, 5, 10, 20, 25, 50, 100 으로 나누어질 수 있다. 100의 제곱근 10을 기준으로 대칭이 되는 것을 확인할 수 있다. 1 * 100 / 2 * 50 / 4 * 25 / 5 * 20 여기서, 1은 모든 수의 약수이므로 제외하고, 제곱근 이전의 수들은 제곱근 이후의 수들과 대칭되므로 나눠지는 수들을 모두 체크할 필요없이, 제곱근 이전의 수들로만 체크해보면 된다. 결론은, 2부터 제곱근까지 나누어봤을 때, 나눌 수 있는 수가 단 1개도 존재하지 않으면 그 수는 소수이다. 예시로, 인자로 들어간 수가 소수인지 판별하는 메서드를 구현해보았다. 이렇게 제곱근을 이용하면, 모든 수를 둘러보지 않아도 되는 .. 2022. 10. 23.

티스토리툴바