Study Room

컴퓨터에서 수행되는 정렬은 컴퓨터 메모리 내요에서 정렬하는 내부 정렬(Internal Sort)과 메모리의 외부인 보조 기억 장치에서 정렬하는 외부 정렬(External Sort)로 분류할 수 있다.

내부정렬

내무정렬은 정렬할 자료를 메인 메모리에 올랴서 정렬하는 방식으로, 정렬 속도는 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한된다.

교환방식 : 키를 비교하교 교환하여 정렬하는 방식(선택정렬, 버블정렬, 퀵정렬)

삽입방식 : 키를 비교하고 삽입하여 정렬하는 방식(삽입정렬, 셸정렬)

병합방식 : 키를 비교하고 병합하여 정렬하는 방식(2-way 병합, n-way 병합)

분배방식 : 키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬하는 방식(기수 정렬)

선택방식 : 이진 트리를 사용하여 정렬하는 방식(히트 정렬, 트리 정렬)

외부정렬

외부정렬은 대용량의 보조 기억 장치를 사용하기 떄문에 내부 정렬보다 속도는 떨어지지만, 내부 정렬로 처리할 수 없는 대용량의 자료를 정렬할 수 있다.

공배수

두 개 이상의 자연수의 공통인 배수

최소공배수

공배수중 가장 작은 수

최소공배수 소스코드

n1과 n2의 최소공배수 구하기

public class lcm {

public static void main(String[] args) {

int n1=27,n2=65;

int lcm=0;

for(int i=1 ; (i%n1!=0)||(i%n2!=0);i++){

lcm=i;

}

System.out.println(lcm+1);

}

}

최대공약수(greatest common measure, GCD)

2개 이상의 수의 공약수 중에서 최대인 수이다.

초대공약수 소스코드

num1과 num2의 최대공약수 구하기

public class gcd {

public static void main(String[] args) {

int num1=12, num2=18;

int gcd=0;

for(int i=1 ; i<=num1 && i<=num2 ; i++){

if((num1%i==0)&&(num2%i==0))

gcd=i;

}

System.out.println(num1+"과 "+num2+"의 최대공약수는 : "+gcd);

}

}

약수

어떤 수를 나누어 떨어지게 하는 수

약수 구하기 소스 코드

num의 약수 구하기

public class subMultiple {

public static void main(String[] args) {

int num=24;

System.out.print(num+"의 약수는 : ");

for(int i=1 ; i<=num ; i++){

if(num%i==0){

System.out.print(i+"  ");

}

}

}

}

소수

1과 자기자신으로만 나누어지는 1보다 큰 양의 정수

소스코드

1부터 100까지의 소수를 구하는 프로그램

public class primeN {

public static void main(String[] args) {

int num=100,cnt=0;

int i,j;

for(i=1 ; i<=num;i++){

cnt=0;

for(j=2 ; j<i ;j++){

if((i%j)==0){

cnt++;

break;

}

}

if(cnt==0){

if(i!=1)

System.out.println(i);

}

}

}

}

피보나치 수열

피보나치 수열은 바로 이전의 두 항의 합으로 다음의 새로운 항이 만들어지는 수열이다.

첫 번째 항을 f0이라고 하고 그 다음을 항을 f1이라고 하면, f0=0, f1=1이 되고 일반항 f(n)=f(n-1)+f(n-2)가 된다.(단 n은 2이상)

피보나치 수열 알고리즘

fibonacci(n)

if (n<0) then

stop;

if (n<=1) then

return 1;

f1=0;

f2=1;

for(i=2;i<=n;i++) do {

fn=f1+f2;

f1=f2;

f2=fn;

}

return fn;

end

피보나치 수열 소스코드

public class fibo {

public static void main(String[] args) {

int a=10;

int result=0;

result=fibonacci(a);

System.out.println(a+"번째 피보나치 수열은"+result+"입니다.");

}

static int fibonacci(int n){

if(n<=0){

System.out.println(0);

return 0;

}

else if(n<=1){

System.out.println(1);

return 1;

}

else{

int f0=0, f1=1,temp=0;

System.out.print(f0+"  "+f1+"  ");

for(int i=2;i<=n ; i++){

temp=f0+f1;

f0=f1;

f1=temp;

System.out.print(temp+"  ");

}

return temp;

}

}

}

재귀호출

자기 자신을 호출하여 수행

재귀호출의 예 -> 팩토리알

소스)

public class fact {

public static void main(String[] args) {

int a=6, result=0;

result=factorial(a);

System.out.println(a+"! 값은"+result+"입니다.");

}

static int factorial(int n){

return (n==1)?n:n*factorial(n-1);

} 

}

해설) 조건연사자를 사용하여 재귀호출을 실행

call by value/ reference

value : 실 매개변수값이 형식 매개변수로 복사된다. 그래서 원본데이터의 수정이 불가하다

reference : 실 매개변수의 시작주소값이 전달되면, 원본데이터의 값을 수정할 수 있다.

어레이(Array), 리스(List), 맵(Map)의 차이점

- 어레이 : 연속리스트. 데이터 기반. 같은 자료형의 연속, 연속된 주소를 가지고 있어서 원하는 위치에 접근시간이 빠름. 

- 리스트 : 연결리스트. 데이터와 링크를 기반으로 구현. 데이터의 순서가 의미 있는 단순 나열이 필요한 경우 많이 사용된다. 정렬되지 않은 리스트에서 데이터 항목을 찾으려면 하나씩 비교해서 찾는 수밖에 없다. 

- 맵 : 해시테이블은 데이터 순서는 상관 없으면서 특정 항목을 빠르게 찾고 싶은 경우에 사용. 아무리 데이터 항목수가 많아도 일정한 실행시간이 걸린다.