개발자의 기록습관

인프런 - 부경대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-2. Hashing 02좋은 해시 함수란?현실에서는 키들이 랜덤하지 않음만약 키들의 통계적 분포에 대해 알고 있다면 이를 이용해서 해시 함수를 고안하는 것이 가능하겠지만 현실적으로 어려움키들이 어떤 특정한 (가시적인) 패턴을 가지더라도 해시함수값이 불규칙적이 되도록 하는게 바람직하다.해시함수값이 키의 특정 부분에 의해서만 결정되지 않아야 함해시 함수Division 기법h(k) = k mod m예: m = 20 and k = 91 ==> h(k) = 11장점: 한번의 mod연산으로 계산, 따라서 빠름단점: 어떤 m값에 대해서는 해시 함수값이 ..

인프런 - 부경대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..