키리Kirri's IT노트

문자열 검색(String Searching)이란? 어떤 문자열 안에 다른 문자열이 들어 잇는지 조사하고, 들어 있다면 그 위치를 찾아내는 것 편의상 검색할 문자열을 패턴(pattern)이라 하고, 문자열 원본은 텍스트(text)라고 정의 브루트-포스법 검색할 텍스트의 맨 처음부터 한 칸씩 뒤로 옮기며 패턴 검색 패턴의 앞 글자부터 순서대로 텍스트와의 일치 여부 검색 그러다가 다른 문자가 나타나면 검사를 중단하고 검색할 텍스트의 위치를 한 칸 뒤로 이동 선형 검색을 확장한 알고리즘으로 단순법, 소박법이라고도 함 효율이 좋은 검색법은 아님 [실습 코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 //브루트-포스법으로 문자열을 검색하는 메서드 static int bfMat..

집합과 요소 집합(set)이란 객관적으로 범위를 규정한 '어떤 것'의 모임이며, 그 집합 안에서 각각의 '어떤 것'을 요소(element)라고 부름 예를 들어, 아이돌 그룹 '트와이스'를 하나의 집합으로 규정한다면 '모모', '미나', '다현' 등은 '트와이스'라는 집합의 요소라고 할 수 있음 집합의 요소는 중복될 수 없음 ※요소의 중복을 허용하는 집합은 다중집합이라고 하며, 집합과는 구별해서 부름 집합 X의 요소가 1, 5인 경우 아래와 같이 표현 X = {1, 5} 집합의 요소에는 순서가 없기 때문에 아래와 같이 표현해도 무방 X = {5, 1} 자연수의 집합: 일반적으로 N이라는 집합의 이름과 ...기호를 사용 N = {1, 2, 3, 4, ...} 정수의 집합: 일반적으로 Z라는 집합의 이름과 ...

도수 정렬 요소의 대소 관계를 비교할 필요가 없음 도수분포표 작성, 누적도수분포표 작성, 목적 배열 만들기, 배열 복사의 4단계로 이루어짐 [10점 만점의 테스트에서 학생 9명의 점수 도수 정렬] 1단계. 도수분포표 만들기 학생 점수 배열 a를 바탕으로 '각 점수에 해당하는 학생이 몇 명인지'를 나타내는 도수분포표 작성 모든 요소의 값을 초기화한 배열 f에 배열 a를 처음부터 스캔하면서 도수분포표 작성 예를 들어, a[0]이 5점이면 f[5]를 1만큼 증가시키고 a[1]이 7점인 경우 f[7]을 1만큼 증가시키는 작업을 반복 for(int i = 0; i < n; i++) f[a[i]]++; 2단계. 누적도수분포표 만들기 '0점부터 점수 n까지 몇 명의 학생이 있는지' 누적된 값을 나타내는 누적도수분포표..

힙이란? 힙(heap)을 사용해 정렬하는 알고리즘 힙은 '부모의 값이 자식보다 항상 크다'는 조건을 만족하는 완전이진트리 부모의 값이 자식보다 항상 작아도 힙이라고 함(부모와 자식 요소의 관계만 일정하면 됨) 완전이진트리 → 힙 힙은 루트가 가장 큰(혹은 작은) 값이어야 함 즉, 모든 부모와 자식의 관계는 항상 부모의 값 >= 자식의 값이 성립되어야 함 힙에서 부모와 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않음 힙의 요소를 배열에 저장 부모와 자식의 인덱스 사이에는 다음과 같은 관계 성립 1. 부모는 a[(i - 1) / 2] 2. 왼쪽 자식은 a[i * 2 + 1] 3. 오른쪽 자식은 a[i * 2 + 2] 힙 정렬 '가장 큰 값이 루트에 위치'하는 특징을 이용하는 정렬 알고리즘 힙에..

정렬을 마친 배열의 병합 : 정렬을 마친 각 배열에서 선택한 요소의 값을 비교해 작은 값의 요소를 꺼내 새로운 배열에 넣는 작업을 반복하여 정렬 [그림] 배열 a와 b를 앞에서부터 차례로 비교하여 작은 값을 꺼내 비에 넣음 [실습 코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 static void merge(int[] a, int na, int[] b, int nb, int[] c) { int pa = 0; int pb = 0; int pc = 0; while(pa