줭 Blog

1. 퀵 정렬(Quick sort) 1) 퀵 정렬이란? - 일반적으로 사용되고 있는 아주 빠른 정렬 알고리즘 - 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하여 모든 그룹이 1명이 되면 정렬을 마침 - 피벗(pivot) : 그룹을 나누는 기준이 되는 요소 - 시간복잡도는 O(n log n) - 하지만 최악의 경우, O(n²) 2) 배열을 두 그룹으로 나누기 - x : 피벗 - pl : 왼쪽 끝 요소의 인덱스 - pr : 오른쪽 끝 요소의 인덱스 (1) a[pl] >= x 가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔 (2) a[pr] pr + 1인 경우에는 피벗과 일치하는 값을 가지는 그룹(a[pr+1], ... , a[pl-1])이 생길 수 있음 static void swap(int[] a,..

1. 최대공약수 최대공약수(GCD, Greatest Common Divisor) : 두 수의 공통된 약수 중 가장 큰 약수 '유클리드 호제법(Euclidean algorithm)'을 사용하면 효율적으로 구할 수 있음 [x와 y의 최대공약수를 구하는 법] 1) 자연수 x와 y에 대하여 x를 y로 나누어 r을 얻는다. (단, x > y일 때) 2) 다시 y를 r로 나누어 r2를 얻는다. 3) 이를 반복하다가 나머지 rn이 0이 되면 y가 최대공약수가 된다. public static void main(String[] args) { int x = 72; int y = 30; int result = gcd(x, y); } public static int gcd(int x, int y) { if(y == 0) re..

1. 정렬(Sorting) 1) 정렬이란? - 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업 - 데이터를 정렬하면 검색을 더 쉽게 할 수 있음 - 오름차순(ascending order) 정렬 : 키 값이 작은 데이터를 앞쪽에 놓는 정렬 - 내림차순(descending order) 정렬 : 키 값이 큰 데이터를 앞쪽에 놓는 정렬 - 안정된(stable) 정렬 : 같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지되는 것 2) 내부 정렬과 외부 정렬 - 내부 정렬(internal sorting) : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용 - 외부 정렬(external sorting) : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우..

1. 재귀란? - 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 함 - 재귀를 효과적으로 사용하면 정의뿐만이 아니라 프로그램도 간결하게 할 수 있음 2. 재귀의 사용 예 - 팩토리얼 구하기 1) 재귀적 정의 - 음이 아닌 정수 n의 팩토리얼(n!)은 재귀적으로 정의할 수 있음 ① 0! = 1 ② n > 0이면 n! = n × (n-1)! static int factorial(int n) { if (n > 0) return n * factorial(n-1); else return 1; } 2) 재귀 호출(recursive call) - 위의 코드와 같이 자기 자신과 똑같은 메서드를 호출하는 것 - factorial 메서드 안에서 factorial 메..

1. 검색(Searching) - 키(key)를 이용하여 원하는 데이터를 찾는 것 - 배열 검색을 위한 알고리즘 1) 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행 2) 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행 3) 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행 (1) 체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법 (2) 오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법 - 데이터 집합에 대한 검색뿐 아니라 데이터의 추가, 삭제 등 다른 작업까지 고려해야 함 - 용도, 목적, 실행 속도, 자료구조 등을 고려하여 알고리즘을 선택하기 2. 선형 검색(Linear search) 1) 선형 검..

1. 알고리즘 1) 알고리즘이란? 1. 문제를 해결하기 위한 것 2. 명확하게 정의되고 순서가 있는 유한 개의 규칙으로 이루어진 집합 2) 순차적 구조와 선택 구조 import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); System.out.print("a의 값: "); int a = sc.nextInt(); System.out.print("b의 값: "); int b = sc.nextInt(); System.out.print("c의 값: "); int c = sc.nextInt(); int max = a; if(b > max) max = b;..