Algorithm (12) 썸네일형 리스트형 [문자열 검색] 브루트-포스법 브루트-포스법(brute force method) 브루트-포스법은 선형 검색을 확장한 알고리즘 ■ 브루트-포스법을 이용한 문자열 검색 - 텍스트(text) : 문자열 원본 - 패턴(pattern) : 검색할 문자열 - while문의 조건[pp != pat.length()]는 텍스트에서 일치하는 패턴이 있는 경우 pp의 값과 pat.length()값이 같아져 while문을 멈추게 된다. - while문의 조건[pt != txt.length()]는 텍스트에서 일치하는 패턴이 없을 경우 문자열 전체 검색을 완료 후 while문을 멈추게 된다. public class BFmatch { static int bfMatch(String txt, String pat) { int pt = 0; //text 커서 int .. [재귀 알고리즘] 하노이의 탑 하노이의 탑 하노이의 탑(Towers of Hanoi)은 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에 옮기는 문제 ■ 하노이의 탑 시작 기둥 : 처음에 원반이 놓인 기둥 목적 기둥 : 목적지의 기둥 중간 기둥 : 남은 중간의 기둥 그룹 : 두 개의 원반이 겹친 것 [하노이의 탑 프로그래밍 과정] - 바닥 원반을 제외한 그룹(원반[1] ~ 원반[n-1])을 시작 기둥에서 중간 기둥으로 옮긴다. - 바닥 원반 no를 시작 기둥에서 목표 기둥으로 옮겼음을 출력한다. - 바닥 원반을 제외한 그룹(원반[1] ~ 원반[n-1]을 중간 기둥에서 목표 기둥으로 옮기다. public class Hanoi { //no개의 원반을 x번 기둥에서 y번 기둥으로 옮김김 static void.. [재귀 알고리즘] 재귀 알고리즘 분석 재귀의 개념 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)라고 한다. ■ 팩토리얼 구하기 재귀의 사용 예 음이 아닌 정수의 팩토리얼 구하는 프로그램 0! = 1 [예제] = 3!= 3 * 2! = 3 * 2 * 1! = 3 * 2 * 1 * 0! = 3 * 2 * 1 * 1 public class Factorial { public static void main(String[] args) { int i = 3; System.out.println("factorial : " + factorial(i)); } static int factorial(int n){ if(n > 0){ return n * factorial(n-1); }else{ return 1; }.. [정렬 알고리즘] 퀵 정렬 퀵 정렬(quick sort) 퀵 정렬은 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하며 모든 그룹이 1명이 되면 정렬 완료 피벗은 그룹을 나누는 기준 ■ 배열을 두개의 그룹으로 나누는 프로그램 피벗(x)을 설정 후, 왼쪽 끝 요소의 인덱스를 pl, 오른쪽 끝 요소의 인덱스를 pr 그룹을 나누기 위해서는 피벗 이하의 요소를 왼쪽 배열로, 이상의 요소를 오른쪽 배열로 옮겨야 한다. - a[pl] >= 피벗(x)가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔 - a[pr] x) pr--; if (pl [정렬 알고리즘] 단순 선택 정렬 단순 선택 정렬(straight selection sort) 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘 단순 선택 정렬의 교환 과정은 - 아직 정렬하지 않은 부분에서 가장 작은 키의 값(a[min])을 선택 - a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환 단순 선택 정렬 알고리즘은 서로 떨어져 있는 요소를 교환하는 것이기 때문에 안정적이지 않음 ■ 단순 선택 정렬 프로그램 import java.util.Arrays; public class Sort { static void swap(int[] a, int idx1, int idx2){ int tmp = a[idx1]; a[idx1] = a[idx2]; a[idx2] = tmp; } static void s.. [정렬 알고리즘] 버블 정렬 정렬(sorting) 핵심 항목(key)의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업 정렬 알고리즘을 통해 데이터를 정렬하면 검색에 용이 정렬 알고리즘의 핵심 요소는 교환, 선택, 삽입 버블 정렬(bubble sort) 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복 비교와 교환 작업을 패스라고 표현 어떤 패스에서 요소의 교환 횟수가 0이면 더 이상 정렬할 요소가 없다는 의미 bubble sort version2 에서는 각각의 패스에서 비교, 교환을 하다가 어떤 시점 이후에 교환이 수행되지 않는다면 그보다 앞쪽의 요소는 이미 정렬을 마친 상태이기에, 다음 패스에서 수행할 범위를 제한해 줄 수 있다. ■ 버블 정렬 프로그램 import java.util.Arrays; .. [기본 자료구조] 링 버퍼[ring buffer] 링 버퍼 오래된 데이터를 버리는 용도로 사용 ■ 링 버퍼를 활용한 실습 요소의 개수가 n인 배열에 계속해서 데이터가 입력될 때 가장 최근에 들어온 데이터 n개만 저장하고 오래된 데이터는 버리는 용도로 사용 ※ 배열 a의 요솟수는 10, 정수 입력(인큐)는 무한히 할 수 있지만 배열에 저장되는 데이터는 가장 최근에 입력한 10개의 데이터만 링 버퍼에 존재 import java.util.Scanner; public class LastNElements { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); final int N = 10; int[] a = new int[N]; // 입력 받은 값을 저장 int cn.. [기본 자료구조] - 큐 큐(Queue) 데이터를 일시적으로 저장하기 위해 사용하는 자료구조 선입선출(FIFO, First In First Out) - 가장 먼저 넣은 데이터를 가장 먼저 꺼낸다. ■ 큐 자료구조 큐에 데이터를 넣는 작업을 인큐(enqueue) 큐에서 데이터를 꺼내는 작업을 디큐(dequeue) ※ 배열 요소를 앞쪽으로 옮기지 않는 큐 구현을 위해 링 버퍼(ring buffer) 자료구조를 사용 링 버퍼 : 배열의 처음이 끝과 연결되었다고 보는 자료구조, 프런트와 리어의 값을 업데이트하며 인큐와 디큐를 수행 1) 프런트(front)와 리어(rear) 논리적으로 어떤 요소가 첫 번째 요소이고 어떤 요소가 마지막 요소인지 식별하기 위한 변수 프런트(front) : 맨 처음 요소의 인덱스를 저장 리어(rear) : 맨.. 이전 1 2 다음