유블로그

그래프에서 최소 비용 문제 모든 정점 연결 간선들 가중치 합이 최소가 되는 트리 두 정점 사이 최소 비용 경로 찾기 신장 트리 : n개 정점 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리(Minimum Spanning Tree) : 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리 : 서로소 집합 사용 간선을 하나씩 선택해서 MST 를 찾는 알고리즘 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬(최대신장트리는 내림차순) 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴 - 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택(union 연산 실패 상황) n-1 개의 간선이 선택될 때까지 2를 반복 ..

그래프는 아이템들과 이들 사이의 연결 관계 표현 그래프는 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조 |V| : 정점의 개수, |E| : 그래프에 포함된 간선의 개수 |V|개의 정점을 가지는 그래프는 최대 |V| ( |V| - 1 ) / 2 간선 가능 -> 무향 그래프에 해당 무향 그래프 (양방향) 유향 그래프 가중치 그래프 사이클 없는 방향 그래프 완전 그래프 : 모든 노드가 연결되어 있는 그래프 부분 그래프 트리는 싸이클이 없는 무향 연결 그래프이다. 두 노드 사이에는 유일한 경로 존재 각 노드는 최대 하나의 부모 노드가 존재할 수 있다. 각 노드는 자식 노트가 없거나 하나 이상이 존재할 수 있다. 인접(Adjacency) 두 개의 ..

- 선형구조 : 자료 간의 관계가 1:1 관계, 스택과 큐가 선형구조에 해당됨. 비선형구조의 예는 트리. - 스택 후입선출(LIFO, Last-In-First-Out) : 마지막에 삽입한 자료를 가장 먼저 꺼냄 연산 : push(삽입), pop(삭제), isEmpty(비어있는지), peek(top 원소값 보기) 맨 위 원소 top이라고 함 Java 는 java.util.Stack 사용 - 후위 표기법 : 연산자가 뒤에 있는 수식 표기법 ex) (6+((5*(2-8))/2)) -> 6528-*2/+ - 큐 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조 큐의 뒤에서는 삽입만, 큐의 앞에서는 삭제만 선입선출(FIFO, First-In-First-Out) : 먼저 삽입된 원소가 먼저 삭제됨 저장된 원..

완전 검색 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법이다. Brute-Force 혹은 generate-and-test 기법이라고도 불린다. 모든 경우의 수를 테스트한 후 최종 해법 도출한다. 경우의 수가 상대적으로 작을 떄 유용하다. 상대적으로 빠른 시간안에 알고리즘 설계를 할 수 있다. 전형적으로 순열, 조합, 부분집합 과 같은 조합적 문제들과 연관된다.