자료구조

4. DFA 알고리즘

Reference : - 건국대학교 컴퓨터공학과 자료구조 수업 / 김성렬 교수님 - https://inuplace.tistory.com/314 / 이누의 개발성장기 DFA 알고리즘 Naive 알고리즘에서 각 숫자에 대한 표기를 좀 더 하는 방식이다. 첫 글자와 일치하는 곳이 발견되면 그곳에 1을 표기하고, 그 이후로도 일치할 경우 1씩 더 증가시키면서 표기한다. 만약 표기하려는 수가 이미 표기된 수보다 작다면 표기할 수 없다. abcabcd에서 abcd를 찾는다면 abcabcd에는 1231234가 표기될 것이다. 찾으려는 글자의 길이 값이 표기된 갯수가 정답의 갯수가 될 것이다. 이에 대한 경우의 수를 표로 만들어 저장하고, 이를 활용한다. 다음은 abcabcd를 찾을 때 경우의 수 표이다. 위 숫자의 ..

2. Naive 알고리즘 (고지식한 탐색 알고리즘)

Reference: - 이것이 자료구조+알고리즘이다 with C언어 / 박상현 / 한빛미디어 - 건국대학교 컴퓨터공학과 자료구조 수업 / 김성렬 교수님 - https://inuplace.tistory.com/314 / 이누의 개발성장기 고지식한 탐색 알고리즘 (Naive Search or Brute Force Search Algorithm) : 본문의 앞에서부터 끝까지 차근차근 탐색하는 알고리즘 본문 : 'ABCABACDC' 패턴 : 'BA' => 이 알고리즘은 이름 그대로 요령 부리지 않고 우직하게 일하는 일꾼처럼 동작한다 본문 길이 : N 패턴 길이 : M 패턴을 찾기 위해 최악의 경우 N x M 번의 비교를 수행 => 굉장히... 느림 일치하는 경우 해당 경우의 끝나는 값에 1을 표기한다 1의 갯수..

2. 점근 표기법

점근(차츰 점, 가깔울 근) 표기법 => 알고리즘의 수행시간을 대략적으로 나타내는 방법 ex) 데이터를 정렬하는데 필요한 작업 횟수 : (n^2 + 5n ) vs ( 27n ) => 데이터의 크기가 커지면 커질수록 최고차 항을 제외한 나머지 항의 영향은 거의 없다 => 때문에 점금 표기법에서는 알고리즘의 성능을 최고차 항으로만 '대략적으로' 표시한다 대표적인 점근 표기법 3가지 O(Big O) 표기법 Ω (Big Omega) 표기법 Θ (Big Theta) 표기법 O(Big O) 표기법 최악의 경우 알고리즘 수행 시간 즉, 아무리 열악한 조건이라도 (입력이 아무리 크더라도) O 표기법으로 표현된 성능 수준에서 알고리즘이 종료된다는 의미 가장 많이 사용하는 알고리즘 성능 표기법 사용방법 대문자 O를 쓰고 ..

1. 알고리즘 성능 측정 기준과 수행 시간

알고리즘 성능 측정 기준 정확성 : 정확하게 동작하는가? => 알고리즘이 입력값에 대해 정해진 절차를 수행하여 결과적으로 정확한 출력을 제공하는가를 가리키는 기준 작업량 : 얼마나 적은 연산을 수행하는가? => 요구되는 기능을 수행하기 위해 알고리즘이 수행해야 하는 작업의 양이 얼마나 되는가를 가리키는 기준 ex) 버블 정렬에서 정렬을 수행하기 위해 비교 연산을 몇 번 수행하는가? 라는 질문에서 '비교횟수' 메모리 사용량 : 얼마나 적은 메모리를 사용하는가? => 말 그대로 해당 알고리즘이 작업을 수행할 때 사용해야 하는 메모리의 양 단순성 : 얼마나 단순한가? => 알고리즘을 짤 때는 보기쉽고 단순해야 한다 최적성 : 더 이상 개선할 여지가 없을 만큼 최적화가 되어있는가? => 최적화를 거친 알고리즘들..

자료구조란?

자료구조 (Data Structure) : 컴퓨터가 데이터를 효율적으로 다룰 수 있게 도와주는 데이터 보관 방법과 데이터에 관한 연산의 총체 ex) int 자료구조 : 32비트 메모리 공간 안에 수를 할당하되 첫 비트를 부호 표현에 사용하는 등의 '보관 방법'을 정의 자료구조는 단순 자료구조 (Primitive Structure)과 복합 자료구조 (Non-Primitive Structure) 로 나뉜다 단순 자료구조 int, long과 같은 프로그래밍 언어에서 통상적으로 제공하는 기본 데이터 형식 복합 자료구조 선형 자료구조 데이터 요소를 순차적으로 연결하는 자료구조 구현하기 쉽고 사용하기도 쉽다 비선형 자료구조 선형 자료구조와 달리 데이터 요소를 비순차적으로 연결하는 자료구조 한 데이터 요소에서 여러 ..

2. 이진 트리

2. 이진 트리의 소개 - 이진 트리의 정의 이진 트리 (binary tree) : 이진트리의 서브 트리들은 모두 이진트리여야 함 => 트리 중에서 가장 많이 쓰이는 트리 이진 트리의 정의 공집합이거나 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의 이진 트리와 일반 트리의 차이점 이진 트리의 모든 노드는 차수가 2이하, 즉 자식 노드의 개수가 2이하지만 일반 트리는 자식 노드의 개수에 제한이 x 일반 트리와는 달리 이진 트리는 노드를 하나도 갖지 않을 수도 있다 서브 트리간에 순서가 존재한다 (왼쪽 서브트리와 오른쪽 서브트리를 구별) - 이진 트리의 성질 n개의 노드를 가진 이진트리는 정확하게 n-1의 간선을 가짐 => 이진트리에서의 노드는 루트를 제외하면 정확하게 하나..

1. 트리

Reference : - C언어로 쉽게 풀어쓴 자료구조 [개정3판] / 천인국, 공용해, 하상호 / 생능출판사 - 건국대학교 컴퓨터공학과 자료구조 수업 / 김성렬 교수님 - https://velog.io/tags/datastructure 1. 트리의 개념 선형 자료 구조 : 리스트, 스택, 큐 계층적인 자료구조 = 비선형 자료구조 : 트리 트리란? : 구조가 트리처럼 생겨서 이름이 트리 ㅋㅋ ex) 결정 트리 : 인간의 의사 결정 구조를 표현한 한 가지 방법 - 트리의 용어들 노드 : 트리의 구성 요소 루트 노드 (root) : 가장 높은 곳에 있는 노드 서브 트리 (sub tree) : 나머지 노드 간선 (edge) : 루트와 서브트리를 연결하는 선 노드의 종류 : 부모 노드, 자식 노드, 형제 노드,..

2. 큐의 구현

선형 큐 (linear queue) 선형 큐 : 1차원 배열을 써서 큐를 구현하는 방법 1차원 배열을 정의하고 삽입, 삭제를 위한 변수인 front와 rear를 만든다 front는 큐의 첫 번째 요소를 가리키고 rear는 큐의 마지막 요소를 가리킨다 front와 rear의 초기값은 -1이다. 데이터가 증가되면 rear를 하나 증가하고 그 위치에 데이터가 저장된다. 삭제할 때도 front를 하나 증가하고 front가 가리키는 위치에 있는 데이터를 삭제한다 선형큐의 구현 ft. C언어 #include #include #define MAX_QUEUE_SIZE 5 typedef int element; typedef struct { // 큐 타입 int front; // 큐의 맨 앞 원소 위치 int rear; ..