컴공과고씨

Trie(트라이) 트라이라는 것은 문자열 집합을 관리하는 트리이다. 하나의 간선은 하나의 알파벳을 나타내고, 트리를 내려가면서 만나는 간선의 알파벳을 모두 이어주면 원래의 문자열을 얻을 수 있다. *그림이 좀 잘못되었는데 문자열 집합 중 abd가 아니라 ad가 맞음. 여기서 T라는 것은 문자열의 끝을 표시하는 것으로 T까지 경로를 이어주면 원래 문자열이 나오게 되는것이다. 그래서 트라이에 들어있는 문자열은 abc, ad, e,eg, f 가 된다. 이러한 트라이는 문자열의 삽입/ 삭제/탐색의 시간복잡도는 O(문자열의 길이)로 해시와 같은 복잡도로 빠른 편에 속한다. 또한 트라이를 응용하여 해시로는 할 수 없는 것들을 할 수 있다. 에를 들면 접두사 찾기 등등. 또한 정렬의 효과를 낼 수도 있다. 구현한 코..

세그먼트 트리 세그먼트 트리는 이진 트리로 구성하면됨. 구간의 길이가 1인 구간은 리프 노드가 되고, 나머지 노드는 자식 노드를 합친 구간 합을 들고 있음. 배열의 길이가 N이라면 세그먼트 트리의 노드 개수는 2N - 1 개가 됨. 루트를 배열 1번 부터 시작 한다고 하면 필요한 배열의 길이는 2N이 된다. Init 처음 세그먼트 배열을 초기화 할 때는 N부터 시작해서 길이가 1인 구간을 N개 만큼 채워넣어준다. 그 후 N-1부터 자식노드의 두 개를 합쳐서 구간의 합을 구하면서 위로 올라가면 위과 같은 그림이 나오게 된다. Update 만약 중간에 배열의 값이 바뀐다면 노드의 값을 바꿔준 후 부모쪽으로 올라가며 다시 구간 합을 구해서 넣어주면 된다. [l,r) 구간 합 찾기 구간 합 찾는 과정은 구간의 ..

힙은 우선순위 큐를 위해 만들어진 자료구조임. 우선순위큐란 완전이진트리인데 부모가 가지는 값은 자식보다 무조건 큰 값을 가지고 있음.( 혹은 무조건 작은 값). 큰 값을 가지는 것을 최대 힙, 작은 값을 가지는 것을 최소 힙이라고 함. 그래서 루트에는 항상 제일 큰 값 혹은 제일 작은 값을 가지고 있는 것이 특징입니다. 기본적으로 구현 같은 경우 배열을 사용하거나 linked를 사용할 수 있습니다. 저는 배열을 사용하여 구현했습니다. 인덱스 루트 노드의 인덱스를 1로 시작하게 하면 (0번 노드는 버림) 부모 인덱스 = (자식 인덱스) / 2 왼쪽 자식 인덱스 = (부모 인덱스) * 2 오른쪽 자식 인덱스 = (부모 인덱스) * 2 이렇게 나타 낼 수 있겠죠. 위 그림에서 99는 인덱스 1, 50은 2, ..

트리 트리는 사이클이 없는 연결 그래프로 각 노드가 하나의 부모 노드와 간선으로 연결되어있는 구조이다. 많은 트리가 있는데 그중 binary search tree에 대해서 알아보자. 일단 트리에 구조를 보면 이런 식으로 되어있다. 자신보다 바로 위에 있는 노드를 부모 노드 parent node 라 하고 그 아래에 있는 노드를 child node라고 한다. 맨 위의 노드를 root node라 하고 이 곳부터 level 0 이고 그 밑에 줄이 level 1 이런식으로 내려간다. 지금 예는 level 2 트리인 것이다. leaf node는 노드가 없는 노드를 말합니다. ancestor(조상)은 부모 노드로만 이동해서 갈 수 있는 노드들이고 descendent(자손)은 자식 노드로만 이동해서 갈 수 있는 노드들..

Quick Sort는 배열을 더 작은 하위 배열로 분할하고 해당 하위 배열을 재귀적으로 정렬합니다. 즉, 분할 정복 알고리즘(divide-and-conquer)를 이용한 정렬이라고 볼 수 있습니다. 평균 및 최선의 시간 복잡도는 O(n log n)이고 최악의 시간 복잡도는 O(n^2)입니다. 효율적인 분할 및 무작위화 기술로 인해 버블 정렬 및 삽입 정렬과 같은 다른 정렬 알고리즘보다 빠른 경우가 많습니다. 또한 내부 알고리즘이므로 배열을 정렬하는 데 추가 메모리가 필요하지 않습니다. Quick sort 구현 1. 배열에서 "pivot" 요소를 선택합니다. 이 요소는 배열을 두 개의 하위 배열로 분할하는 데 사용됩니다. 하나는 피벗보다 작은 요소를 포함하고 다른 하나는 피벗보다 큰 요소를 포함합니다. e..

https://hagisilecoding.tistory.com/140 [자료구조] 리스트(unsorted & sorted list) c++ [컴공과고씨] * 참고서적 c++ plus data structures * 전체코드는 https://github.com/goragoraki/Data-Structure 에서 볼 수 있습니다. 리스트는 배열과 같이 원소들을 저장하고 있는 것을 말합니다. 이 리스트를 두 개로 나눕니다 hagisilecoding.tistory.com 이 글을 보기 전에 위 링크를 먼저 보고 오시는게 좋습니다. 위 글 처럼 sorted 리스트의 가장 큰 문제점은 삽입과 삭제할 때 발생을 합니다. 예를 들면 1,2,3,4,6,7,8,9,10,11,12,13,14 라는 리스트가 있다고 할 때 5..

들어가기 앞서 Linked Queue 구현을 위한 더 쉬운 이해를 위해 스택에 관한 앞 글인 https://hagisilecoding.tistory.com/141 를 보고 오시는게 좋습니다. 큐는 스택과 반대입니다. 스택은 들어간 것이 먼저 나중에 나오지만 큐는 먼저 들어간 것이 먼저 빠져 나온다고 생각하면 됩니다. 그렇기에 구현 할 때도 조금 더 생각을 해주어야 합니다. 스택은 top 변수로 늘려주고 빼주고 하면 되지만 큐 같은 경우는 변수를 두 개 두고 앞쪽 dequeue할 변수 한 개 enqueue할 변수 한 개 총 두개를 컨트롤 해주어야합니다. 문제는 이렇게 하면 Dequeue를 했을 때 낭비되는 칸이 생기게 됩니다. 이런식으로 그래서 %연산을 이용해서 circular(순환) 하도록 만들어 주는 ..

Stack stack은 단어가 쌓다 뭐 이런 뜻이죠. 말 그래도 쌓는다 이렇게 이해하면 됩니다. 위 그림 처럼 동전을 쌓는다고 생각하고 원소를 하나씩 push (넣는다) 하면 밑에 부터 쌓이게 됩니다. pop을 하는 것은 원소를 빼는 것이고 stack은 위에서부터 하나씩 빼는 방식을 가지고 있습니다. 스택 클래스는 위 처럼 구성할 것이고 STL 스택을 써보신 분들은 아시겠지만 data type을 stack을 선언할 때 사용자가 정할 수 있습니다. 그것과 똑같이 만들기 위해 template class를 사용하여 data type을 사용자가 설정할 수 있도록 만들었습니다. 그래서 코드를 보시면 template 으로 선언된 것을 볼 수 있습니다. Stack을 구현하는 세 가지 방법이 있습니다. 하나는 배열을 ..

* 참고서적 c++ plus data structures * 전체코드는 https://github.com/goragoraki/Data-Structure 에서 볼 수 있습니다. 리스트는 배열과 같이 원소들을 저장하고 있는 것을 말합니다. 이 리스트를 두 개로 나눕니다. 1. 비정렬 리스트 2. 정렬 리스트. 책에서는 class를 사용하여 리스트에 대해 설명하고 있습니다. ItemType() 이 class 경우 두 리스트에서 이렇게 구성이 되어있습니다. 리스트에 원소를 넣을 때 우리는 ItemType() 객체를 넣어주는 것입니다. 우리는 Initialize()를 통해서 value에 값을 초기화 합니다. 즉, value 값이 실제 원소 값이 되는 것이죠. 그 생성한 ItemType() 객체를 리스트에 넣어주는..

리눅스에서의 file i/o에 대한 system call과 c를 이용해서 파일 입출력을 해보겠습니다. 일단 system call이란 application 즉, 사용자가 쉽게 프로그래밍할 수 있도록 만든 언어들 c++ 이런것 들은 하드웨어를 직접 access할 수 없습니다. hardware는 운영체제가 관리를 하기 때문에 하드웨어 접근이 필요할 때 운영체제에게 서비스를 요청할 때 system call을 사용하여 요청한다고 볼 수 있습니다. 리눅스에서의 file i/o에 관한 system call은 open, read, write, close lseek, fcntl, ioctl 이 있습니다. #include 를 하게되면 자동적으로 STDIN_FILENO (0) STDOUT_FILENO(1) STDERR_FI..