알고리즘 (2) 알고리즘의 설계와 분석

알고리즘 2023.03.19

보호되어 있는 글입니다.

알고리즘 (1) 알고리즘의 정의와 중요성

알고리즘 2023.03.14

보호되어 있는 글입니다.

병합 정렬(Merge Sort)

알고리즘/정렬 알고리즘 2020.11.23

병합 정렬이란? 배열의 요솟수가 2개 이상인 경우, 배열을 반으로 나눠 앞부분을 병합 정렬하고 뒷부분을 병합 정렬한 후, 앞부분과 뒷부분을 병합하는 정렬 알고리즘. 여기서 병합이란 단순히 합치는 것이 아니라, 다음과 같이 이미 정렬된 두 배열의 요소 중 더 작은 요소를 선택해 목표 배열에 넣는 것이다. 이미 정렬된 두 배열 병합하기 static void mergeArray(int[] a, int[] b, int[] c) { //각 배열의 포인터를 모두 0으로 초기화 int pa, pb, pc; pa=pb=pc=0; //두 배열의 포인터가 모두 각 배열의 끝에 닿지 못했을 때 while(pa

셸 정렬 알고리즘

알고리즘/정렬 알고리즘 2020.11.22

단순 삽입 정렬의 장점(정렬을 마친 상태에 가까울 수록 정렬 속도가 매우 빨라짐)은 그대로 가져가고 단점(삽입할 위치가 멀리 떨어져 있으면 이동해야하는 횟수가 많아짐)을 보완한 알고리즘. 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법. 자바로 구현하기 static void shellSort(int[] a, int n) { //각 부분 리스트의 요소가 1이 될 때까지, //즉 증분값 h가 1이 될 때까지 전체 반복 for(int h=n/2; h>0; h/=2) { //부분 리스트들끼리 나눠서 반복할 수도 있지만 여기서는 //전체 요소들을 반복하면서 각 부분 리스트에 맞게 비교 되도록 구현하겠다. for(int..

재귀 알고리즘

알고리즘 2020.11.17

재귀란? 어떤 사건이 자기 자신을 포함하고, 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 한다. 대표적인 재귀 알고리즘 1 : 팩토리얼 구하기 package recursive; import java.util.Scanner; public class Factorial { //양의 정수 n의 팩토리얼을 반환합니다. static int factorial(int n) { if(n>0) { return n*factorial(n-1); } else { return 1; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("팩토리얼을 구하고 싶은 양의 정수를 입력하세요 ..

BM 검색 알고리즘

알고리즘/검색 알고리즘 2020.11.17

BM 검색 알고리즘이란? 문자열을 데이터에서 검색할 때, 검색할 문자열의 끝에서부터 비교하다가 일치하지 않는 문자를 만나면 검색할 문자열만큼 이동하여 검색을 수행하는 알고리즘. 고안자인 Boyer-Moore 법이라고도 한다. - 찾고자 하는 문자열이 중복되지 않을 경우 예를 들어 다음과 같은 데이터에서 'MYBK' 처럼 중복되지 않는 문자열을 찾을 경우. M Y B B A G M Y B K 찾고자 하는 문자열인 'MYBK'의 마지막 문자 'K'와 배열의 4번째 데이터, 배열[3] 데이터인 'B'를 비교한다. 서로 다르므로 4칸을 건너뛰고 검색한다. - 찾고자 하는 문자열이 중복되는 경우 예를 들어 다음과 같은 데이터에서 'MBMBC' 처럼 중복되는 문자열을 찾을 경우. M B M B M B C K A B..

KMP 검색 알고리즘

알고리즘/검색 알고리즘 2020.11.17

KMP 검색 알고리즘이란? 문자열 안에서 부분 문자열을 검색할 때, 검색에 실패한 위치를 기반으로 비교할 필요가 없는 문자열은 건너뛰고, 다음 번 검색 위치를 결정하는 알고리즘. - 찾고자 하는 문자열이 중복되지 않을 경우 예를 들어 다음과 같은 데이터에서 'MYBK' 처럼 중복되지 않는 문자열을 찾을 경우. M Y B B A G M Y B K 'MYB'까지는 일치하지만 4번째 K가 일치하지 않는다. 이럴 경우 'MYB' 다음 위치부터 검색을 다시 시작한다. - 찾고자 하는 문자열이 중복되는 경우 예를 들어 다음과 같은 데이터에서 'MBMBC' 처럼 중복되는 문자열을 찾을 경우. M B M B M B C K A B M B M C M B A B C A 'MBMB' 까지는 일치하지만 5번째 C가 일치하지 않..

문자열 검색(String Search) 알고리즘 1. 브루트-포스법

알고리즘/검색 알고리즘 2020.11.17

문자열 검색(String Search) 알고리즘 주어진 문자열에서 찾고자 하는 문자열이 있을 때, 해당 문자열의 위치를 찾는 알고리즘. 브루트-포스법이란? 텍스트의 맨 앞부터 한 문자씩 살펴보며 패턴의 첫 자와 일치하는 문자를 찾고, 일치한다면 그 문자부터 패턴의 나머지와 일치하는지 검사한다. 불일치한다면 텍스트의 다음 문자부터 다시 검사한다. 선형검색을 확장한 알고리즘으로, 단순법, 소박법이라고도 한다. 자바로 구현하기 package algorithm; public class BFMatch { //브루트-포스법으로 문자열을 검색하는 메서드 static int bfMatch(String txt, String pat) { int pt = 0;//txt 커서 int pp = 0;//pat 커서 //텍스트 커..

이진 검색(Binary Search) 알고리즘

알고리즘/검색 알고리즘 2020.11.17

이진 검색(Binary Search) 알고리즘이란? 이미 키 값으로 정렬된 데이터를 대상으로, 중앙 값을 이용해 검색하는 알고리즘. 전체 데이터의 중앙 값을 찾아 검색하려는 데이터와 비교하여 중앙 값보다 작으면 왼쪽 부분의 중앙 값을 다시 취하고, 중앙 값보다 크면 오른쪽 부분의 중앙 값을 다시 취해 비교하는 작업을 반복하는 알고리즘. 선형 검색보다 좀 더 빠르다. 자바로 구현하기 //요솟수가 n인 배열 a에서 key와 같은 요소를 이진 검색한다. static int binSearch(int[] a, int n, int key) { int pl = 0; int pr = n-1; while(pl a[pc]) { pl = pc+1; } else if (key < a[pc]) { pr = pc-1; } } r..

순차 검색(Sequential Search) 또는 선형 검색(Linear Search) 알고리즘

알고리즘/검색 알고리즘 2020.11.17

순차 검색(Sequential Search) 알고리즘이란? 주어진 데이터를 처음부터 검색하는 알고리즘. 무작위로 늘어놓은 데이터 모임에서 검색을 수행할 때 유효. 순차 검색 종료조건 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 검색할 값과 같은 요소를 발견한 경우 자바로 구현하기 //요솟수가 n인 배열 a에서 key와 같은 요소를 선형 검색한다. static int seqSearch(int[] a, int n, int key) { for(int i=0; i