본문 바로가기

컴/알고리즘

 (9)
Java - 순열, 조합 public class Main { public static void main(String[] args) { int n = 10, r = 5; int[] ret = new int[r]; System.out.println(n + "C" + r); combi(ret, n, r, 0, 0); System.out.println("\n"+n + "P" + r); boolean[] visited = new boolean[n]; ret = new int[r]; perm(ret, visited, 0, n, r); } //nCr static void combi(int[] ret, int n, int r, int index, int target) { if (r == 0) { for (int i : ret) { System..
LIS 길이 구하기 LIS : Longest Increasing Subsequence, 최대 증가 부분수열 1. 완전탐색 int LIS(vector arr) { if (arr.empty()) return 0; int ret = 1; for (int i = 0; i < arr.size(); i++) { vector next; for (int j = i + 1; j < arr.size(); j++) { if (arr[i] < arr[j]) { next.push_back(arr[j]); } } ret = max(ret, 1 + LIS(next)); } return ret; } 시간복잡도 O(2^N) 2. DP int cache[MAX]; int find(int start, vector arr) { if (cache[start] ..
위상정렬 유향 그래프의 꼭짓점들(vectex)을 변의 방향을 거스르지 않도록 나열하는 것 ex) 순서가 있는 작업들을 수행할 때 순서 결정하기 1. DFS 스택에 들어가는 순서 : 7 -> 5 -> 2 -> 6 -> 3 -> 4 -> 1 위상정렬 순서 : 1 -> 4 -> 3 -> 6 -> 2 -> 5 -> 7 (여러 경우의 수 발생할 수 있다) 2. indegree 이용하기 (indegree : 한 정점에서 자신에게 들어오는 방향인 간선의 수) 1번 정점의 indegree 개수 = 0 2번 정점의 indegree 개수 = 1 3번 정점의 indegree 개수 = 2 4번 정점의 indegree 개수 = 3 5번 정점의 indegree 개수 = 0 indegree 개수가 0인 정점을 큐에 추가 큐의 front를 ..
트라이(Trie) why? 정수나 실수형 변수는 크기가 정해져 있으므로 비교에 상수 시간이 걸리지만, 문자열 변수를 비교하는 데는 문자열의 길이에 비례하는 시간이 걸린다 이러한 문제를 해결하기 위해 고안된 문자열 특화 자료구조의 대표적인 예가 트라이. 트라이 (Trie) 출처 : 위키피디아 class TrieNode { //자식 노드 맵 private Map childNodes = new HashMap(); //마지막 글자 여부 private boolean isLastChar; Map getChildNodes() { return this.childNodes; } boolean isLastChar() { return this.isLastChar; } void setLastChar(boolean isLastChar) { th..
Heap 힙이란, 특정한 규칙을 만족하도록 구성된 이진 트리이다. 힙의 대소관계 규칙 부모 노드가 항상 자식 노드보다 크거나 같다 (자식 노드 index = 부모 노드 index / 2 (+1)) 즉, 가장 큰 원소는 항상 힙의 루트에 있다. 힙의 모양 규칙 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 한다 이러한 특성 덕분에 힙은 최대 원소를 빠르게 찾을 수 있다 6개의 정수를 저장하는 힙의 예 16 삽입 삭제 * 대소관계 규칙을 반대로 적용하면 최소 원소를 빠르게 찾을 수 있다 연산을 편하게 하기 위해서 0번에는 최소 혹은 최대값을 넣어주고 1번부터 값을 채운다 public abstract class Heap { fin..
순열 (java) - ex) 0 ~ 9로 구성된 정수 list를 가지고, 만들 수 있는 모든 숫자 구하기 (list에 중복된 숫자가 있으므로 결과에도 중복이 발생할 수 있다) public class Main { public static void main(String[] arg) { List number = Arrays.asList(1, 2, 3, 3, 2, 1); for (int i = 1; i
C++ - next_permutation #include void nextPermutaionTest(vector data) { sort(data.begin(), data.end()); do { ///// 데이터 처리 /////// } while (next_permutation(data.begin(), data.end())); } 이런 식으로 쓰면 된다 (iterator 대신 배열 주소 넣어도 됨)
분할 정복 (병합정렬, 퀵정렬) 분할 정복 (Divide & Conquer) 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산 => 빠르게 작업을 처리할 수 있다 divide : 문제를 더 작은 문제로 분할하는 과정 merge : 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 base case : 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 example : 1 + 2 + ... + n int sum(int n) { // 기저 사례 if (n == 1) return 1; if (n % 2 == 1) return sum(n-1) + n; // 홀수일 경우 처리 방법 return 2*sum(n/2) + (n..

티스토리툴바