C언어/자료구조 (38) 썸네일형 리스트형 8-1장 선형 리스트 1. 선형 리스트 정의하기 선형 리스트 (linear list) - 리스트 : 데이터를 순서대로 나열한 자료구조 - 가장 단순한 구조를 가진 리스트 - 노드(node) : 리스트의 각 요소 - 각각의 노드는 데이터와 다음 노드를 가리키는 포인터를 가짐 - 머리 노드(head node) : 처음에 있는 노드 - 꼬리 노드 (tail node) : 끝에 있는 노드 2. 배열로 선형 리스트 만들기 1) 다음 노드 꺼내기 - 1만큼 큰 인덱스를 갖는 요소에 접근 2) 노드의 삽입과 삭제 -삽입 요소의 다음 요소를 하나씩 뒤로 옮겨야 함 - 삭제하는 경우에도 모든 요소를 뒤로 밀거나 앞으로 당겨야 함 - 배열로 구현한 선형리스트의 문제점 쌓이는 데이터의 크기를 미리 알아야함 데이터의 삽입, 삭제에 따라 데이터를 .. 7-4장 보이어-무어법 1. 보이어-무어법 살펴보기 - 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 결정 - Good Suffix method : 접미사와 같은 문자열이 패턴 문자열 내에 존재하는지 검사 -Bad Character method : 본문의 문자열과 패턴이 불일치하는 문자 (나쁜 문자)를 발견하면 패턴의 나쁜 문자와 텍스트의 나쁜 문자를 일치 시킴 ex) 텍스트 "ABCXDEZCABACABAC"에서 패턴 "ABAC"를 검색하는 경우 - 1) 텍스트와 패턴의 첫 번째 문자를 위, 아래로 겹치고 패턴의 마지막 문자 'C'를 검사 - 텍스트의 'X'는 패턴에 없음 - 텍스트 안에서 패턴에 들어 있지 않은 문자를 찾으면 해당 위치까지의 문자는 건.. 7 -3장 KMP법 1. KMP법 알아보기 - 중간 검사 결과를 효율적으로 사용하는 알고리즘 - 검사했던 위치 결과를 버리지 않고 이를 효율적으로 활용하는 알고리즘 - 텍스트와 패턴의 겹치는 부분을 찾아내어 검사를 다시 시작할 위치를 구해서 패턴을 최소의 횟수로 옮겨 알고리즘의 효율을 높임 ex) 텍스트 "ZABCABXACCADEF"에서 패턴 "ABCABD"를 검색하는 경우 - 텍스트, 패턴의 첫 문자부터 순서대로 검사 - 'Z'는 패턴에 없는 문자이므로 불일치 판단 - 패턴을 1칸 뒤로 이동 - 패턴의 마지막 문자는 'D'여서 텍스트의 'X'와 불일치 - 텍스트의 AB와 패턴의 AB가 일치한다는 점 이용 -> 이 부분은 이미 검사를 마친부분이므로 텍스트 'X' 다음 문자부터 패턴의 'CABD'가 일치하는지만 검사 - 'A.. 7-2장 브루트 - 포스법 1. 문자열 검색 정의하기 문자열 검색 (string searching) - 어떤 문자열 안에 다른 문자열이 들어 있는지 조사하고 들어있다면 그 위치를 찾아내는 것 패턴(pattern) - 검색할 문자열 텍스트(text) - 문자열 원본 2. 브루트-포스법으로 검색하기 - 다른 문자를 만나면 패턴에서 문자를 검사했던 위치 결과를 버리고 다음 텍스트의 위치로 1칸 이동한 다음 다시 패턴의 첫 번째 문자부터 검사하는 알고리즘 ex) "ABABCDEFGHA"에서 패턴 "ABC"를 브루트- 포스법을 사용하여 검색 - 텍스트의 첫 문자 'A'부터 시작하는 3개의 문자와 "ABC"가 일치하는지 검사 - 'A'와 'B'는 일치하고 'C'는 다름 - 패턴을 1칸 뒤로 옮김 - 텍스트의 2번째 문자부터 3개의 문자가 일.. 7-1장 문자열의 기본 1. 문자열 (string) - 문자의 나열 2. 문자열 리터럴(string literal) - 문자 나열을 2개의 큰따옴표(")로 묶은 것 - 문자열 안의 문자는 메모리 공간에 연속으로 배치 - 컴퓨터는 문자열 리터럴의 끝을 나타내기 위해 널문자(null character) 추가 - 문자열 리터럴의 자료형은 char형 배열 - 문자열 리터럴의 표현식을 평가하여 얻는 자료형은 char*형이고 그 값은 첫 번째 문자에 대한 포인터 - 문자열 리터럴의 메모리 영역 기간은 정적 메모리 영역의 기간 -> 프로그램 시작부터 끝까지 메모리 영역이 유지 - 문자열 리터럴은 상수의 성질을 가짐 -> 문자열 리터럴이 저장된 메모리 영역에 값 대입 불가 - 문자열 안의 문자를 16진수와 2진수로 출력 //문자열 안의 문자.. 6-9장 도수 정렬 1. 도수 정렬하기 도수 정렬 (counting sort) - 요소의 대소 관계를 판단하지 않고 빠르게 정렬 - 데이터의 최솟값과 최댓값을 미리 알고 있는 경우에만 사용 가능 1) 도수 분포표 만들기 2) 누적도수분포표 만들기 3) 목적 배열 만들기 4) 배열 복사하기 ex) 10점 만점의 테스트에서 학생 9명의 점수 배열 a, 요소의 개수 n, 점수의 최댓값 max 1.1 도수분포표 만들기 - '각 점수에 해당하는 학생이 몇명인지' - 배열 f: 도수분포표를 나타내기 위한 배열 - 먼저 배열 f의 모든 요소의 값을 0으로 초기화 - 배열 a를 처음부터 스캔하면서 도수분포표 제작 for(int i=0; i < n; i++) f[a[i]]++; 1.2 누적도수분포표 만들기 - '0점부터 점수 n까지 몇 명.. 6-8장 힙 정렬 1. 힙 정의하기 힙(heap) - '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전 이진트리 - 힙의 가장 위쪽에 있는 루트가 가장 큰 값이 됨 - 모든 부모와 자식의 관계는 항상 부모의 값 >= 자식의 값이 성립되어야 함 - 형제 사이의 대소 관계는 일정하지 않음 완전 이진트리 - 완전 : 부모는 자식을 왼쪽부터 추가하는 모양을 유지 - 이진 : 부모가 가질 수 있는 자식의 개수는 최대 2개 1) 부모는 a[(i-1)/2] 2) 왼쪽 자식은 a[i*2+1] 3) 오른쪽 자식은 a[i*2+2] 2. 힙 정렬 알아보기 - '가장 큰 값이 루트에 위치'하는 특징을 이용 - 선택 정렬을 응용한 알고리즘 - 1) 힙에서 가장 큰 값인 루트를 꺼냄 2) 루트 이외의 부분을 힙으로 전환 - 힙에서 .. 6-7장 병합 정렬 1. 정렬을 마친 배열 병합하기 - '각 배열에서 선택한 요소의 값을 비교하여 작은 값의 요소를 꺼내 새로운 배열에 넣는 작업'을 반복하여 정렬을 끝냄 - 병합에 필요한 시간 복잡도 O(n) - 정렬을 마친 배열을 병합하는 프로그램 //정렬을 마친 배열을 병합하는 프로그램 #include #include void merge(const int a[], int na, const int b[], int nb, int c[]) { int pa = 0; int pb = 0; int pc = 0; while(pa < na && pb 이전 1 2 3 4 5 다음
