개발자의 기록습관

인프런 - 부경대IT융합응용공학과 궘오흠 교수님의 '영리한 프로그래밍을 위한 알고리즘 강좌 '(링크)와 '쉽게 배우는 알고리즘 관계 중심의 사고법 - 문병로' 참조7-3. Graph 03 - DFS(Depth-First Search, 깊이우선탐색)이진트리의 순회 방법인 inorder, preorder, postorder 순회방법이 DFS의 이진트리 버전에 해당한다.lever order는 BFS의 이진트리 순회 버전이다.깊이우선탐색(DFS)출발점 s에서 시작한다.현재 노드를 visited로 mark하고 인접한 노드들 중 unvisited 노드가 존재하면 그 노드로 간다.2번을 계속 반복한다.노드 8에 도달했을 때처럼 인접한 노드들중 invisited 노드가 존재하지 않는다면, unvisited인 이웃 노드..

인프런 - 부경대IT융합응용공학과 궘오흠 교수님의 '영리한 프로그래밍을 위한 알고리즘 강좌 '(링크)와 '쉽게 배우는 알고리즘 관계 중심의 사고법 - 문병로' 참조7-2. Graph 02 - BFS(Breadth-First Search, 너비우선탐색)그래프 순회순회(traversal)그래프의 모든 노드들을 방문하는 일대표적 두 가지 방법BFS (Breadth-First Search, 너비우선순회)DFS (Depth-First Search, 깊이우선순회)너비우선탐색(BFS)BFS 알고리즘은 다음 순서로 노드들을 방문L0 = {s}, 여기서 s는 출발 노드L1 = L0의 모든 이웃 노드들L2 = L1의 이웃들 중 L0에 속하지 않는 노드들...Li = Li-1의 이웃들 중 Li-2에 속하지 않는 노드들한마디..

인프런 - 부경대IT융합응용공학과 궘오흠 교수님의 '영리한 프로그래밍을 위한 알고리즘 강좌 '(링크)와 '쉽게 배우는 알고리즘 관계 중심의 사고법 - 문병로' 참조7-1. Graph Algorithm 01 - 개념과 표현Graph(무방향) 그래프 G = (V, E)V : 노드 혹은 정점(vertex)E : 노드쌍을 연결하는 Edge 혹은 LinkObject들 간의 이진관계를 표현n = |V|, m = |E|방향 그래프와 가중치 그래프방향그래프(Directed Graph) G = (V, E)Edge (u, v)는 u로부터 v로의 방향을 가짐가중치 그래프Edge마다 가중치(weight)가 존재그래프의 표현인접행렬(adjacency matrix)인접리스트(adjacency list)정점 집합을 표현하는 하나의..

인프런 - 부경대IT융합응용공학과 궘오흠 교수님의 '영리한 프로그래밍을 위한 알고리즘 강좌 '(링크)와 '쉽게 배우는 알고리즘 관계 중심의 사고법 - 문병로' 참조6-1. Hashing 01 - 개요Hash Table탐색과 삽입, 삭제를 지원하는 자료구조를 dynamic set이라고 부른다.4장에서는 검색트리를 가지고 dynamic set을 구현했고, 또다른 한가지 구현 방법이 Hashing을 이용하는 것이다.해시 테이블은 dynamic set을 구현하는 효과적인 방법의 하나이다."적절한 가정"하에서 평균 탐색, 삽입, 삭제시간 O(1)보통 최악의 경우 O(n)해시 함수(hash function) h를 사용하여 키 k를 T[h(k)]에 저장h : U -> {0, 1, 2, … , m-1}여기서 m은 테이..

인프런 - 부경대IT융합응용공학과 궘오흠 교수님의 '영리한 프로그래밍을 위한 알고리즘 강좌 '(링크)와 '쉽게 배우는 알고리즘 관계 중심의 사고법 - 문병로' 참조5-3. Red-Black Tree 03 - DELETE, FIXUPDELETE보통의 BST에서처럼 DELETE한다.실제로 삭제된 노드 y가 red였으면 종료y가 black이었을 경우 RB-DELETE-FIXUP을 호출한다.pesudo code01 : 삭제할 노드 z의 왼쪽, 오른쪽 자식이 NULL이 아니라면 즉, 자식이 없다면02 : y에 z를 저장하고03 : 자식이 있다면, z의 Successor를 찾아서 y에 저장한다. BST에서 Successor찾는 과정과 동일04 : 01-03과정을 거치면 y는 자식이 하나이거나 없다. Successo..

인프런 - 부경대IT융합응용공학과 궘오흠 교수님의 '영리한 프로그래밍을 위한 알고리즘 강좌 '(링크)와 '쉽게 배우는 알고리즘 관계 중심의 사고법 - 문병로' 참조5-2. Red-Black Tree 02 - INSERT, FIXUPINSERT보통의 BST에서처럼 노드를 INSERT한다.새로운 노드 z를 red노드로 한다.RB-INSERT-FIXUP을 호출한다.1 : 또다른 포인터 y를 사용해서 y가 x의 한칸 뒤를 쫓아 내려오록 해야 새로운 노드를 insert할 자리를 관리할 수 있다. 레드블랙트리에서 특수하게 NIL 노드를 사용하지만, 실제로 구현할때는 null이 된다.3 - 7 : 새로운 노드 z가 들어갈 자리를 찾고,8 : z의 parent를 y로 설정해준다.9 - 10 : 예외적인 경우 y가 nu..