justgo_developer

DAG는 방향 사이클이 없는 방향 그래프.ex)작업들의 우선순위 위상정렬(topological ordering)-DAG에서 노드들의 순서화 v1,v2 ....vn, 단, 모든 에지(vi,vj)에 대해서 i

1. 출발점 s에서 시작한다.2. 현재 노드를 visited로 mark하고 인접한 노드들 중 unvisited 노드가 존재하면 그 노드로 간다.3. 2번을 계속 반복한다. 4. 만약 unvisited인 이웃노드가 존재하지 않는 동간 계속해서 직전 노드로 되돌아간다.5. 다시 2번을 반복한다.6. 시작노드 s로 돌아오고 더 이상 갈 곳이 없으면 종료한다. DFS(G, v)visited[v]

정렬 selection sort(선택 정렬)1.가장큰값을찾는다.2.맨끝의 자리와 바꾼다.3.똑같은일은 나머지 데이터와 반복한다.시간복잡도 O(n^2) for last

순환 Recursion자기자신을 호출무한루프에 빠진다적절한 구조를 갖추고 있다면 항상 무한루프에 빠지는 것은 아님.적절한 구조란?->base case:적어도 하나의 리커전으로 빠지지 않고 종료되는 경우가 존재해야한다.->recursive case:recursion을 반복하다보면 결국 base case로 수렴해야한다.ex) 피보나치,팩토리얼,최대공약수,X^n 수학함수뿐 아니라 다른 많은 문제들을 recursion으로 해결할 수 있다. ex)문자열의 길이 계산public static int length(String str){if(str.equals(""))return 0;elsereturn 1+length(str.substring(1)); }ex)문자열의 프린트public static void printCh..

그래프 순회 -순회(traversal) :그래프의 모든 노드들을 방문하는 일-두가지방법1. BFS(Breath-First Search, 너비우선순회)2. DFS(Depth-First Search, 깊이우선순회) 너비우선순회(BFS) ■ 큐를 이용한 너비우선순회 1. check the start node(체크는 이미 방문된 노드라는 표시)2. insert the start node into the queue 3. while the queue is not empty doremove a node v from queue;for each unchecked neighbour w of v docheck and insert w into the queue;반복한다.노드 방문 순서 : 1,2,3,4,5,7,8,6 ■ BF..

■ (무방향) 그래프(Graph)G=(V,E)- V : 노드(node) 혹은 정점(vertex)- E : 노드쌍을 연결하는 에지(edge) 혹은 링크(link)- 개체(object)들 간의 이진관계를 표현- n=|V|, m=|E| ■ 방향그래프(Directed Graph) G=(V,E)-에지(u,v)는 u로부터 v로의 방향을 가짐 ■ 가중치(weighted) 그래프- 에지마다 가중치(weight)가 지정 ■ 그래프의 표현- 인접행렬(adjacency matrix) - 인접리스트(adjacency list) : 정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 연결리스트m(edge 개수) if 방향그래프라면- 인접행렬은 비대칭- 인접 리스트는 m개의 노드를 가짐 ** 가중치 그래프의 인접행렬..

레드블랙트리(Red-Black Tree)- 이진탐색트리의 일종- 균형잡힌 트리 : 높이가 O(logn)- SEARCH,INSERT,DELETE를 수정함으로써 균형을 잡히도록 만듬 -각 노드는 하나의키(key),왼쪽자식(left),오른쪽자식(right),그리고 부모노드(p)의 주소를 저장- 자식노드가 존재하지 않을 경우 NIL 노드라고 부르는 특수한 노드가 있다고 가정- 따라서 모든 리프노드는 NIL노드- 루트의 부모도 NIL노드라고 가정- 노드들은 내부노드와 NIL노드로 분류 다음 조건을 만족하는 이진탐색트리 :1. 각 노드는 red 혹은 black이고,2. 루트노드는 black이고 3. 모든 리프노드(즉 NIL노드)는 black이다.4. red노드의 자식노드들은 전부 black이고(즉, red노듣 연속..

이진검색트리(Binary Search Tree)-Dynamic set을 트리의 형태로 구현 정의-이진트리이면서 각 노드에 하나의 키를 저장- 각 노드 v에 대해서 그 노드의 왼쪽 부트리(subtree)에 있는 키들은 key[v]보다 작거나 같고, 오른쪽 부트리에 있는 값은 크거나 같다.**Binary Search Tree하고 heap은 다르다. 최소값 찾기: 왼쪽 자식이 없어야 하고 어떤 노드의 오른쪽 서브트리이면 안된다. TREE-MINIMUM(x)while left[x]≠NILdo x

검색트리(Search Tree) 트리(Tree)란?-계층적인 구조를 표현(조직도,디렉토리와 서브디렉토리 구조, 가계도) 트리는 노드(node)들과 노드들을 연결하는 링크(link)들로 구성됨. 부모(parent)-자식(child) 관계 형제관계 :부 모가 동일한 노드들 리프(leaf) 노드 : 자식이 없는 노드들 내부(internal)노드 : 리프노드가 아닌것 조상-자손관계 : 부모-자식 관계를 확장한 것 부트리(subtree)레벨(level)트리의 높이는 : 서로다른 노드의 갯수 트리의 기본적인 성질-노드의 n개일때 링크의 갯수는 n-1이다.-트리에서 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두노드간의 경로도 유일하다. 이진트리(binary tree)-이진트리에서 각 노드는 최대 2개의..