전체 글 (92) 썸네일형 리스트형 [Algoritm 기초] 최소 신장 트리(Minimum Spanning Tree) 최소 신장 트리(Minimum Spanning Tree , MST) - 그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법 크루스칼 (Kruskal) - 간선 중 최소 값을 가진 간선부터 연결 - 사이클 발생 시 다른 간선 선택 - 주로 간선 수가 적을 때 사용 알고리즘 복잡도 : O(ElogE) 경로 최적화를 이용하지 않는 경우 O(ElogV), 경로 최적화를 이용하는 경우 O(Elog∗V) 프림(Prim) - 임의의 노드에서 시작 - 연결된 노드들의 간선 중 낮은 가중치를 갖는 간선 선택 - 간선의 개수가 많을 때 쿠르스칼 보다 유리 알고리즘 복잡도 : O(ElogV) 바이너리 힙을 이용하는 경우 O(E+VlogV) import java.util.Arrays; //최소 신장 트리 - 크루스칼 pu.. [Algorithm 기초] 백트랙킹 (Backtracking) 백트랙킹 (Backtracking) - 모든 경우의 수를 탐색하며 최적해를 구하는 과정에서 유망하지 않은 쪽은 더이상 구하지 않는 방법 - 돌다리 두드려보고 가는 느낌 용어 유망 (Promising) : 해가 될 가능성이 있는 경우 유망하다고 함 가지치기 (Pruning) : 해가 될 가능성이 없는 경우 해당 노드를 제외하는 것 백트랙킹 (Backtracking) : 유망하지 않은 쪽으로 가지 않고 되돌아 오는것 알고리즘 복잡도 : O(N^M) //알고리즘 백트랙킹 //N-Queen 문제 (N x N 체스판에서 퀸 N개를 서로 공격할 수 없도록 배치하는 경우의 수) public class backTracking { static int n = 4; static int[] board = new int[n];.. [Data Structure 기초] 트라이 Trie (트라이) - 문자열을 저장하고 빠르게 탐색하기 위한 트리 형태의 자료구조 - 정렬된 자료구조 - 문자열 저장을 위한 메모리가 필요하지만 탐색이 빠름 - 음의 간선이 포함되어 있어도 사용 가능하나 음수 사이클이 있으면 정상 동작 하지 않음 알고리즘 복잡도 : O (N) // 비선형 자료구조 - 트라이 (Trie) import java.util.HashMap; class Node { HashMap child; // 단어 끝인지 체크 용 boolean isTerminal; public Node() { this.child = new HashMap(); this.isTerminal = false; } } class Trie { Node root; public Trie() { this.root = new.. 이전 1 2 3 4 5 6 7 ··· 31 다음
