GONI

고지식한 검색 본문(Text) : 탐색 대상이 되는 문자열 패턴(Pattern) : 검색어(검색해야할 문자열) 이동(Shift) : 본문에서의 탐색 위치를 옮기는 것 고지식하거나 미련하거나 본문이 'ABCABACDC'라고 하고, 패턴은 'BA'라고 할 때 간단하게 생각해본다면 대부분 순차 검색을 통해 첫 번째 글자를 먼저 같은지를 검색하고 같은 것을 찾았을 때 뒤에 있는 2번째 글자를 검색할 것이다. 이 알고리즘은 마치 요령부지 않고 그저 우직하게 일하는 일꾼처럼 동작할 것이다. 이러한 알고리즘을 가리켜 고지식한 검색(Native Search), 또는 무식한 검색(Brute Force Search)라고 한다. 본문의 길이를 N, 패턴의 길이를 M이라고 했을 때, 본문 속에 존재하는 패턴을 찾기 위해 최악..

그래프를 소개합니다 오일러의 도구 "다리를 한 번씩만 건너 쾨니히스베르크의 모든 지역을 순회할 수 있을까?" 라는 문제를 해결하기 위해 오일러는 그래프를 고안해내고, 이를 도구로 이용하여 불가능함을 밝혀냈다. 오일러는 위의 그림을 좀 더 단순하게 만들어 각 육지를 정점(vertex)으로, 각 육지를 잇는 다리를 간선(edge)으로 표시했다. 이렇게 하면 쾨니히스베르크의 네 육지와 7개의 다리를 4개의 정점과 7개의 간선으로 나타낼 수 있다. 쾨니히스베르크의 다리 문제는 한붓그리기 문제가 됐다. 쾨니히스베르크의 그래프에서 정점 A,B,C,D 네 개는 모두가 홀수개의 선으로 연결되어 있기 때문에 한붓그리기가 불가능하고 따라서 7개의 다리를 한 번씩만 건너서 쾨니히스베르크의 모든 육지를 밟은 것을 불가능하다...

해시에 대하여 해시는 다양한 목적으로 사용될 수 있지만, 주로 다음과 같은 용도로 사용된다. 해시 테이블 : 해시테이블은 데이터의 해시 값을 테이블 내의 주소로 이용하는 궁극의 탐색 알고리즘이다. 빠르다고 정평이 나있는 이진 탐색보다도 빠르다. 암호화 : 해시는 입력받은 데이터를 완전히 새로운 모습의 데이터로 만든다. 해시를 통해 변환된 데이터는 원본의 모습을 알아볼 수 없을 정도로 완전히 달라진다. 이 특성 때문에 해시는 암호화 영역에서 아주 주요하게 사용되고 있다. SHA(Secure Hash Algorithm)알고리즘이 그 대표적인 예이다. 데이터 축약 : 해시는 길이가 서로 다른 입력 데이터에 대해 일정한 길이의 출력을 만들 수 있다. 이 특성을 이용하면 커다란 데이터를 '해시'하면 짧은 길이로 ..

우선순위 큐 먼저 들어간 요소가 먼저 나오는(First-In First Out)자료구조를 일컫어 '큐(Queue)'라고 한다. 우선순위 큐(Priority Queue)도 보통의 큐처럼 동작하지만 '우선순위' 속성을 갖는 데이터를 다룬다는 것이 다르다. 우선순위 큐의 삽입 연산 우선순위 큐의 삽입(Enqueue)은 요소의 우선순위 오름차순으로 연결된다. 새로운 요소가 삽입될 때 우선순위를 비교하여 새로운 요소가 들어가야할 자리에 삽입된다. 우선순위 큐의 제거 연산 우선순위 큐의 제거(Dequeue) 연산은 전단만 제거하면 된다. 우선순위 큐의 구현 다음에 나오는 힙을 배우고 구현 힙 여기서 말하는 힙은 프로그래밍에서 말하는 자유저장소(Free Store)가 아니라, 힙 순서 속성(Heap Order Pro..

데이터를 찾아서 컴퓨터에서의 탐색이란 '데이터'를 찾는다라는 의미 각각의 자료구조(배열,링크드리스트,트리 등등)에서 탐색의 방법이 다를 수 있다 순차 탐색 순차 탐색(Sequential Search)은 데이터 집합의 처음부터 끝까지 차례대로 모든 요소를 비교해서 데이터를 찾는 탐색 알고리즘이다. 정렬되어 있지 않은 데이터 집합에서 원하는 데이터를 찾을 수 있는 유일한 방법이고 구현이 간단해 버그를 만들 가능성이 적다는 장점이 있다. 자기 구성 순차 탐색 자주 사용되는 항목을 데이터 집합의 앞쪽에 배치함으로써 순차 탐색의 검색 효율을 끌어올리는 방법이다. 자주 사용되는 항목을 어떻게 선별하는가에 따라 세 가지 방법으로 나뉜다. 전진 이동법(Move To Front) 전진 이동법은 어느 항목이 한 번 탐색되..

계모가 3만명의 학생 정보를 주며 17,213등이 누구냐고 알아보라고 함, 텍스트 에디터와 C컴파일러 쓸 수 있게 해줌, 동점자는 없다고함(착하다...) 오늘 못 알아오면 맴매 맞는다고함(못됐다...) 콩쥐의 해결책: 정렬 알고리즘 정렬의 목적 : 찾으려고 하는 것을 쉽게 찾고자 하는데 있음(탐색을 쉽게 하려고) 버블 정렬 버블 정렬을 소개합니다 버블 정렬은 알고리즘이 데이터를 정렬하는 과정이 마치 물 속 깊으느 곳에서 일어난 거품이 수면을 향해 올라오는 모습과 같다고 해서 붙여진 이름 버블 정렬(Bubble Sort)은 데이터 집합을 순회하면서 집합 내의 이웃 요소들끼리의 교환을 통해 정렬을 수행 6뽀글뽀글 위로 올라오고 뒤로 가면서 완료됨, 6을 제외하고 나머지에 대해 위의 내용을 반복 버블 정렬은 ..

트리기초 다지기 트리를 소개합니다 트리(Tree)는 이름에서 알 수 있는 것처럼, 나무를 닮은 자료구조이다 컴퓨터 과학에서도 트리는 굉장히 활용도가 높다. 운영체제의 파일 시스템이 트리 구조로 이루어져 있고, HTML이나 XML 문서를 다룰 때 사용하는 DOM(Document Object Model)도 트리 구조로 이루어져 있다. 검색 엔진이나 데이터 베이스도 트리 자료구조에 기반해서 구현된다. 트리를 열어봅시다 트리는 뿌리(Root), 가지(Branch), 잎(Leaf) 세 가지 요소로 이루어짐 뿌리, 가지 잎 모두 실제로는 노드이다. 이들은 트리 내의 위치에 따라 명칭만 달라짐. 루트는 트리의 가장 위에 있는 노드를 가리키고, 가지는 루트와 잎 사이에 있는 모든 노드를 일컫는 말이다. 잎 노드는 끝에..

큐 먼저 들어간 데이터가 먼저 나옴, FIFO(First In First Out), 선입선출(先入先出) 큐의 주요 기능: 삽입과 제거 큐의 가장 앞 요소를 전단(Front), 마지막 요소를 후단(Rear)라고 부름 큐는 삽입(Enqueue)은 후단, 제거(Dequeue)는 전단에서 수행 끝은 새로운 시작이다: 순환 큐 순환 큐를 소개합니다. 위의 그림과 같은 방법으로 큐를 만든다면 제거(Dequeue)가 될 때마다 나머지 요소를 앞으로 이동해야하는 비용이 필요하다 그래서 전단을 가리키는 변수를 도입하여 배열의 요소를 변경하는 대신 변경된 전단의 위치만 관리할 수 있다. 요소들의 이동에 대한 부하는 해결할 수 있지만 요소를 제거하고나서 전단의 앞의 요소를 사용하지 못하여 용량이 줄어드는 문제가 생긴다 그래..

스택 주차장의 추억 '가장 먼저 들어간 데이터가 가장 마지막에 나오는 구조' 스택은 뭔가를 쌓아놓은 '더미'를 뜻함 LIFO(Last In, First Out) 요소의 삽입과 삭제가 자료구조의 한쪽 끝에서만 이루어지는 것이 특징 스택의 주요 기능 : 삽입과 제거 스택의 주요 기능은 '삽입(push)'와 '제거(pop)' 배열로 구현하는 스택 스택과 스택의 노드 표현하기 노드 typedef int ElementType; typedef struct tagNode { ElementType data; } NODE; 스택 구조체 typedef struct tagArrayStack { int capacity; // 용량 int top; // 최상위 노드의 위치 NODE* node; // 노드 배열 } ArraySt..

링크드 리스트 배열 유감 배열처럼 데이터 집합을 보관하는 기능을 가지면서도 한편으로는 배열과는 달리 유연하게 크기를 바꿀 수 있는 자료구조 리스트는 스택과 큐, 그리고 트리와 같은 자료구조를 이해할 수 있는 기반이 된다는 점에서 중요 링크드 리스트를 소개합니다 링크드 리스트 : 노드를 연결해서 만드는 리스트 노드 : 데이터를 보관하는 필드 + 다음 연결 고리 역할을 하는 포인터 로 구성됨 헤드(머리)와 테일(꼬리)을 가지고 있음 데이터가 늘어날 때마다 테일에 붙이면 됨 C 언어로 표현하는 링크드 리스트의 노드 typedef struct Node { int Data; // 데이터 필드 struct Node* NextNode ; // 다음 노드를 가리키는 포인터 } NODE ; 링크드 리스트의 주요 연산 노..