이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다. DAG(Directed Acyclic Graph)와 Topological Ordering(위상정렬)DAG(Directed Acyclic Graph)- DAG는 방향 사이클(directed cycle)이 없는 방향그래프예 : 작업들의 우선순위 Topological Ordering(위상정렬)유향 그래프의 Vertex(꼭지점)들의 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해서 위상 정렬을 이용할 수 있다.정렬의 순서는 유향 그래프의 구조에 따라 여러개의 종류가 나올 수 있다.위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다...
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다. DFS(Depth-First Search, 깊이우선탐색)맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(Level)의 한 개의 자식노드를 첨가하여, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식노드의 첨가 과정을 반복해가는 방식이다. 장점 : - 단지 한 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.- 목표노드가 깊은 단계가 있을 경우 해를 빨리 구할 수 있다. 단점 : - 해가 없는 경로에 깊이 빠질 가능성이 있다. - 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의..
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다. Graph Traversal(그래프 순회)Traversal(순회) : 그래프의 모든 노드들을 방문하는 일 대표적 두 가지 방법 - BFS(Breath-First Search, 너비우선순회)- DFS(Depth-First Search, 깊이우선순회) BFS(Breath-First Search, 너비우선순회)맹목적 탐색방법의 하나로 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 탐색하는 방법이다.더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다. 장점 : - 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다. 단점 : - 경로가 매우 길 경우에는 탐색 가..
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다. Graph Algorithms(그래프 알고리즘)Graph(그래프) : 일련의 꼭지점들과 그 사이를 잇는 변들로 구성된 조합론적 구조이다. - (무방향) 그래프 G = (V, E)- V : Node(노드) 혹은 Vertax(정점)- E : 노드 쌍을 연결하는 Edge(에지) 혹은 Link(링크)- Object(개체)들 간의 이진 관계를 표현- n = |V|, m = |E|출처 : 위키백과 V = {1, 2, 3, 4, 5, 6}E = {{1, 2}, {1, 5}, {2, 3}, {2, 5}, {3, 4}, {4, 5}, {4, 6}}n = 6, m = 7 Directed Graph(방향 그래프)와 Weighted Graph..
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다. Hahsing(해싱)- Hash Table(해쉬 테이블)해쉬 테이블은 Dynamic set을 구현하는 효과적인 방법의 하나적절한 가정하에서 평균, 삽입, 삭제 시간 -> O(n)보통 최악의 경우 -> Θ(n)- Hash Function(해쉬 함수)해쉬 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.h를 사용하여 키 k를 T[h(k)]에 저장h : U -> {0, 1, 2, ... , m-1}여기서 m은 테이블의 크기, U는 모든 가능한 키들의 집합키 k가 h(k)로 해싱되었다고 말함 Hash Function(해쉬 함수)의 예- 모든 키들을 자연수라고 가정(어떤 데이터든지 자연수로 해석하는 것이 가..