본문 바로가기
Computer Algorithm 1. 문제해결과 알고리즘 - 문제해결과정 - 알고리즘 분석 2. 데이터 추상화와 자료구조 - 데이터 추상화 - 자료구조 : tree, binary tree, stack, queue, heap, union-find, dictionary, ... 4. Sorting - 정렬 : insertion sort, quick sort, merge sort, heap sort, radix sort 6. Dynamic sets & Searching - array doubling & amortized analysis - BST - Red-Black tree 7. Graph and Graph Search - Graph - Graph traversal : pre-order, in-order, post-order - Graph.. 2020. 7. 26.
문자열 매칭 알고리즘 단순 문자열 매칭 KMP (Knuth-Morris-Pratt) 알고리즘 Boyer-Moore 알고리즘 kmp 단순 문자열 매칭 알고리즘 문자 하나씩 확인하는 알고리즘으로 가장 간단한 형태의 알고리즘 의사코드 전체 문자열의 첫번째 문자에서 시작하여 찾을 문자열의 첫번째 문자를 비교 매칭이 이루어지면 찾을 문자열의 다음 문자를 비교 매칭이 이루어지지 않으면 전체 문자열의 두번째 문자에서 다시 시작 위의 과정을 반복하여 문자열을 찾는다 시간 복잡도 : O(N*M) // N = 전체 문자열 길이, M = 찾을 문자열 길이 KMP (Knuth-Morris-Pratt) 알고리즘 접두사와 접미사의 개념을 활용하여 '반복되는 연산을 얼마나 줄일 수 있는지 판별'하고 매칭할 문자열을 빠르게 점프하는 기법 접두사 : 찾을.. 2020. 7. 19.
Greedy Algorithm Greedy Algorithm, 탐욕알고리즘 정의 : 당장 눈 앞에 보이는 최적의 상황만을 쫒는 알고리즘 특징 : 탐욕알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 출처: https://yongmin0000.tistory.com/70?category=847685 [yongmin] 2020. 7. 19.
Graph, DFS, BFS, Dijkstra Graph DFS BFS Dijkstra Graph 요약 정의 : 노드의 상하위 개념이 없고, 노드(혹은 버텍스)와 노드들을 잇는 엣지로 구성되어 있는 자료구조 용어 정점(vertex): 위치라는 개념. (node 라고도 부름) 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름) 인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름) 진출 차수(out-degree): 방향 그래픙에서 외부로.. 2020. 7. 19.
Tree, Traversal, Binary Search Tree Tree 정의 : '노드'와 '간선'으로 구성 된 자료구조로, 그래프의 한 종류이다. 용어 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다. 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다. 내부(internal) 노드: 단말 노드가 아닌 노드 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름) 형제(sibling): 같은 부모를 가지는 노드 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합 노드의 차수(degree): 하위 트리 .. 2020. 7. 19.
Hashing ' 용어 정의 해시함수 : 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수. 균일하게 매핑할수록 좋은 해시함수이다. 해시 : 해시 함수에 얻어지는 값 해시 테이블 : 해시 값을 인덱스로 하여 데이터를 저장하고 있는 자료구조 Hashing 정의 : 데이터를 담을 해시 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해시함수에 의해 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 과정 장점 : 데이터 접근 속도가 빠르다. 단점 : 충돌(collision)발생 - 서로 다른 입격 값에 대해 동일한 해시 테이블 주소를 반환하는 경우 해결법 chaining : 충돌되는 데이터들을 해당 주소에 링크드 리스트로 연결 open addressing : 충돌 발생시 해당 주소에 고정 폭 만큼을 더한.. 2020. 7. 19.

티스토리툴바