게으름뱅이의 앞구르기

라빈 카프 문자열 매칭(Rabin–Karp algorithm) ASCII 코드 기반의 해시 함수를 이용하여 특정한 문자열에 대한 해시 값을 구함 연속적인 문자열이 이어지는 상황이므로 해시 함수의 동작에 있어서 연산속도가 O(1) 라빈카프 문자열 매칭 알고리즘에서 해시함수는 각 문자의 ASCII 코드 값에 2의 제곱 수를 차례대로 곱하여 더한 값을 구함. 일반적으로 서로 다른 문자열의 경우 해시값이 다르게 나옴. 그러나 해시기반이기 때문에 충돌 처리 필요 다음 해시 값 = 2 * (현재 해시값 - 가장 앞에 있는 문자의 수치) + 새 문자의 수치 참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수

트리구조로 구간 합 구하기 세그먼트 트리는 구현하는 과정이 복잡하고 어려움 → 인덱스 트리는 구현이 매우 간단하며 O(logN)의 시간 복잡도를 가짐 인덱스 트리는 세그먼트 트리에 비해 메모리 효율성이 높음 특정 숫자의 마지막 비트를 구함(A & -A) 각 인덱스의 마지막 비트를 내가 저장하고 있는 값들의 개수로 계산 마지막 비트만큼 구간을 앞으로 이동하며 합을 구함 참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수

세그먼트 트리로 구간합* 구하기 선형적으로 구간합을 구하면 O(N)의 시간 복잡도를 가지므로 비효율적임 트리구조를 이용하여 구간합을 구하여 O(logN)의 시간복잡도로 구간합을 구함 *구간합 : 여러개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터 합을 구하는 것 완전 이진 트리에 데이터 삽입 구간 합 트리 생성(특정 범위 인덱스의 값을 저장함) 필요한 구간에 포함된 트리 노드의 값들로 구간합을 계산함 참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수

가중치가 있는 연결된 무방향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성 트리를 찾는 알고리즘 각 간선에 대한 정보를 우선순위 큐에 담아 처리하는 방식으로 구현 프림 알고리즘 작동 순서 그래프에서 정점하나를 선택하여 트리 T에 포함시킴 T에 포함된 노드와 T에 포함되지 않은 노드 사이의 간선 중에서 가장 가중가 작은 간선을 찾음 해당 간선에 연결된 T에 포함되지 않은 노드를 트리 T에 포함시킴 모든 노드가 포함될 때까지 반복 각 간선에 대한 정보를 우선 순위 큐에 담아 처리하는 방식으로 구현 참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수

해시(Hash)란? 데이터를 최대한 빠른 속도로 관리하도록 도와주는 자료구조 해시를 사용하면 메모리 공간이 많이 소모되지만 매우 빠른 속도로 데이터를 처리할 수 있음 빠르게 데이터에 접근할 수 있어 데이터베이스 등에 활용 특정한 값을 찾고자 할 때 키(Key)로 접근할 수 있음 일반적으로 해시 함수는 모듈로 연산 등의 수학적연산으로 이루어져 있어 O(1)만에 값에 접근할 수 있음 해싱 알고리즘은 나눗셈법이 가장 많이 활용됨 입력값을 테이블의 크기로 나눈 나머지를 키로 이용하는 방식 테이블 크기는 소수(Prime Number)로 설정하는 것이 효율성이 높음 해시의 충돌 해시 함수의 입력값으로는 어떤 값이나 들어갈 수 있지만, 해시 함수를 거쳐 생성되는 키의 경우의 수는 한정적이라 키 중복이 발생할 수 있음..

이진 탐색 트리 이진 탐색 트리의 조건 각 노드에 값이 있다. 값들은 전순서가 있다. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다. 노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어져 있다. 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다 ※ 성능을 최대치로 끌어내기 위해서는 완전 이진트리에 가까워질 수 있도록 설계해야함 이진 탐색 트리 삽입 삽입을 하기 전, 검색을 수행한다. 트리를 검색한 후 키와 일치하는 노드가 없으면 마지막 노드에서 키와 노드의 크기를 비교하여서 왼쪽이나 오른쪽에 새로운 노드를 삽입한다. 이진 탐색 트리 삭제 삭제하려는 노드의 자식 수에 따라 자식노드가 없는 노드(리프 노드) 삭제 : 해당 노드를 단순히..

깊이 우선 탐색(Depth First Search) 맹목적 탐색방법의 하나로 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식 탐색시작 노드를 스택에 삽입하고 방문처리함 스택의 최상단 노드에게 방문하지 않은 인접노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리함 / 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄 2를 더이상 수행할 수 없을 때까지 반복 스택 자료구조에 기초함 빠르게 모든 경우의 수를 탐색하고자 할 때 쉽게 사용..

그래프(Graph) 사물을 정점(Vertex)와 간선(Edge)로 나타내기 위한 도구 이론적으로 그래프는 리스트와 행렬 구조 중의 하나로 구별 가능하지만 실제 적용에 있어서 최적의 자료구조는 이 두 구조의 조합된 형태를 띤 형태임 인접 행렬(Adjacency Matrix) : 2차원 배열을 사용 인접 리스트(Adjacency List) : 리트스를 사용 무방향 그래프 : 모든 간선이 방향성을 가지지 않는 그래프 비가중치 그래프 : 모든 간선에 가중치가 없는 그래프. 연결되어 있는 상황을 인접 행렬로 출력할 수 있음 방향 그래프 : 모든 간선이 방향을 가짐 가중치 그래프 : 모든 간선에 가중치가 있음 그래프 개념과 구현 인접 행렬은 모든 정점들의 연결 여부를 저장하여 O(V2)의 공간을 요구하므로 공간 효..