프로그래밍/자료구조+알고리즘 with C언어13 chapter10 문자열탐색 10.1 문자열 탐색 알고리즘의 개요Ctrl+F : 탐색단축키본문 : 탐색 대상 문자열패턴 : 탐색어이동 : 탐색 위치 옮기기10.2 고지식한 탐색 알고리즘본문 길이가 n이고 패턴 길이가 k이면 인덱스 0~n-k까지 패턴단위로 한 칸 한 칸 옮겨서 탐색 해보는 것최악의 경우 NxM번의 비교 수행10.3 카프-라빈 알고리즘알고리즘의 핵심 : 해싱 10.3.1 카프-라빈 알고리즘의 동작 방식문자열 탐색을 위해 해시 함수를 이용한다. 패턴의 해시값과 본문 내의 하위 문자열의 해시값을 비교하는 방식연산 비용은 더 커보이는데 천재적인 영감은? 해시함수의 비용을 획기적으로 줄이는 방법 패턴의 길이 m = 4 본문 = S[0…3]인 해시값 H = S[0]x2^3 + S[1]x2^2 + S[2]x2^1 + S[3]x2.. 2023. 6. 9. chapter09 알고리즘 그래프(1) 버스노선 시공 일정 네비게이션의 경로탐색 -> 최소신장트리, 최단경로탐색으로 해결 9.1 그래프의 개요 9.1.1 그래프의 탄생 쾨니히스베르크 도시를 가로지르는 다리들을 한번만 건너서 순회하는 방법을 찾다가 고안 되었다 해결법은 한붓그리기 : 홀수개의 선으로 연결된 점이 없거나 두개인 도형에서만 가능하다. 9.1.2 그래프의 정의 V : 정점의 집합 E : 간선의 집합 G: 그래프 =(V,E) 길이 : 정점과 정점 사이에 있는 간선의 수 인접(또는 이웃관계) : 간선으로 연결된 두 정점 경로는 길이를 가지는데, 길이는 정점과 정점 사이의 간선의 수이다. 사이클(Cycle) : 어느 경로가 정점 하나를 두 번 이상 거치도록 되어있을 때 (트리에서는 볼 수 없다) 방향성 그래프 : 간선에 방향성이 있을 대 .. 2023. 5. 17. chapter12 알고리즘 분할 정복, 병합정렬 12.1 분할 정복 기법 12.1.2 분할 정복 알고리즘의 개념 사탕의 큰 덩어리를 작은 조각으로 나누어 먹으면 더 넓은 표면을 입안에서 녹일 수 있다. 분할정복도 마찬가지로 문제를 더 이상 나눌 수 없을 때까지 나누고, 이렇게 나뉜 문제들을 각각 풀어 결국 전체 문제의 답을 얻는 기법. 5장의 퀵 정렬. 대강의 설계 요령 분할(divide) : 문제가 분할 가능한 경우 2개 이상의 하위 문제로 나눈다. 정복(conquer) : 하위 문제가 여전히 분할 가능한 상태라면 하위 집합에 대해 단계 1을 수행. 그렇지 않다면 하위 문제를 해결 결합(combine) : 단계2를 통해 구한 답을 취합 문제를 잘게 나누는 것이 가장 중요하다. 문제를 제대로 나누기만 한다면 정복(해결)하는 일은 아주 쉽다. 분할정복 .. 2023. 4. 17. chapter08 알고리즘 해시테이블 8.1 해시 테이블의 개요극한의 탐색 성능을 가진 자료구조 8.1.1 해시뜻 : 잘게 자른 고기를 양파나 감자와 같은 다른 재료와 함께 튀겨 한덩어리로 만든 요리. ㅋㅋ,,, 아무튼 데이터를 입력받아 완전히 다른 모습의 데이터로 바꾸는 작업. 해시테이블 : 데이터의 해시값을 테이블 내 주소로 이용하는 궁극의 탐색ㅇ ㅏㄹ고리즘. 빠르다고 정평이 나 있는 이진탐색도 명함을 내밀지 못함암호화 : 해싱은 원본 데이터를 다른 모습으로 바꿔놓는다. 해싱은 같은 데이터에 대해 같은 결과를 출력하지만 다른 데이터에 대해서는 다른 결과를 출력한다. 말하자면 해시는 데이터의 지문 역할을 할 수 있다. 이런 특징 때문에 해시는 디지털 서명이나 블록체인에 많이 사용된다. MD5, SHA 알고리즘이 대표적인 예데이터 축약 : .. 2023. 4. 17. chapter07 자료구조(알고리즘) 우선순위 큐, 힙 7.1 우선순위 큐 우선순위에 따라 출력 순서를 결정하는 큐 삽입과 제거 연산을 지원하는 ADT 보통 큐와의 차이는 ‘삽입과 제거 연산이 어떻게 동작하는가?’에 있다. 7.1.1 우선순위 큐의 삽입/제거 연산 노드 삽입 연산 첫 노드와 순차적으로 우선순위를 비교하면 되는데, 순차탐색을 해야하나? 해결할 방법 : 트리 처럼 하면 될듯. (내 생각,,, 아그래서 힙인가보다…ㅁㅊ) 노드 제거 연산 제거 연산은 간단하다. 전단만 제거해서 반환하면 끝. 큐니까! 7.1.2 우선순위 큐의 구현 힙을 사용한다~~ 7.2 힙 힙 : 힙 순서 속성을 만족하는 완전 이진 트리. 최고 깊이를 제외한 모든 깊이의 노드가 완전히 채워져 있는 이진트리. 힙 순서 속성 : 트리 내의 모든 노드가 부모 노드보다 커야 한다. (이진탐.. 2023. 4. 15. chapter13 자료구조 큐 3.1 큐 ADT FIFO 선입선출 3.1.2 큐의 핵심 기능 : 삽입과 제거 연산 전단 : 큐의 가장 앞 요소 후단 : 큐의 가장 마지막 요소 삽입은 후단, 제거는 전단에서 수행된다. 3.2 순환 큐 전단과 후단을 가리키는 변수를 만든다. 삽입이 일어날 때 마다 후단의 위치 +1. 삽입이 이루어질 때 후단이 가리키는 위치에 데이터를 바로 입력. 배열의 시작과 끝을 연결하면 메모리 용량을 잘 사용할 수 있다. 전단과 후단 사이에 공백 메모리를 둬서 큐가 공백상태일 때는 전단과 후단이 같은 곳을 가리키고, 큐가 포화상태일 때는 후단이 전단보다 1 작은 값을 가지도록 하여 상태를 구분한다. 3.2.2 순환 큐의 기본 연산 순환 큐의 노드 구조체 선언 typedef int ElementType; typedef.. 2023. 4. 14. 이전 1 2 3 다음