개발자의 기록습관

인프런 - 부경대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융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크4-2. Binary Search TreeDynamic Set집합이다. 여러개의 데이터의 집합인데, 그것들의 내용이 고정되지 않고, 생성과 삭제를 반복하면서 유동적인 집합이다. 아래와 같은 특징을 가진다. Dynamic Set, Dictionary 또는 Search Structure라고 불린다.여러 개의 키(key)를 저장다음과 같은 연산들을 지원하는 자료구조INSERT - 새로운 키의 삽입SEARCH - 키 탐색DELETE - 키의 삭제예: 심볼 테이블일반적으로 구현할 때 배열 or 연결리스트를 사용한다.각 동작에 있어서 다음과 같은 ..

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크3-4. 힙 정렬(Heap Sort)Heap과 Heap sort최악의 경우 시간복잡도 O(nlogn)Sorts in place - 추가 배열 불필요mergesort도 최악의경우 O(nlogn)이었지만, 추가 배열이 필요했음.이진 힙(binary heap) 자료구조를 사용O(nlogn)의 시간복잡도를 가지면서, merge sort처럼 추가적인 배열이 필요하지 않기 때문에 좋은 정렬 알고리즘 중 하나다.Heap의 정의Heap은완전 이진 트리(complete binary tree)이면서Heap property를 만족해야 한다.동일한 데이터를 ..

Algorithm부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크1. 알고리즘의 분석알고리즘의 자원(resource) 사용량을 분석자원이란 실행시간, 메모리, 저장장치, 통신 등여기서 실행시간의 분석에 대해서 다룸 시간복잡도실행시간은 실행환경에 따라 달라짐하드웨어, 운영체제, 언어, 컴파일러 등실행시간을 측정하는 대신 연산의 실행 횟수를 카운트연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현데이터의 크기가 같더라고 실제 데이터에 따라서 달라짐최악의 경우 시간복잡도(worst-case analysis)평균 시간복잡도(average-case analysis) 점근적(Asympto..