이너의 Computer Library

#include <stdio.h>
int main() {
	int coin[10];
	int count=0;
	int N,K,i;
	int check=0;
	
	scanf("%d %d",&N,&K);
	
	for(i=0;i<N;i++) {
		scanf("%d", &coin[i]);
	}
	
	i=N-1;
	
	while(i>-1) {
		if(coin[i]>K) {
			i--;
		} else if(coin[i]<K) {
			K-=coin[i];
			count++;
		} else {
			check=1;
			count++;
			break;
		}
	}
	
	if(check) {
		printf("%d",count);
	}
}

위 코드는 동전 액수를 오름차순으로 입력받을 때임에 유의한다 :>

생각나는 대로 올리겠슴니다

출처 : 서울특별시교육청 출간 고등교과 <알고리즘>, 위키백과

동적 계획법(DP : Dynamic Programming)

문제를 해결하기 위해 문제를 해결이 가능한 더 작은 문제로 분할함. 그런 다음 작은 문제를 먼저 해결하고 그 결과를 활용하여 전체 문제를 해결하는 방법.

> 메모이제이션(Memoization)

컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술.

ex) fiboncci 수열을 구하는 함수 fib(n)이 있을 때, 여러 번 함수를 수행할 경우 같은 인자값에 대해 반복함. 실행시간 단축을 위해 따로 저장공간을 두어 fib(n)을 계산할때마다 그 저장공간에 저장하고 필요할때 마다 참조.

활용 : 검색, 소스 코드 생성, 암호화 또는 데이터 압축 영상 변환과 같은 반복 계산 ..

https://ko.wikipedia.org/wiki/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98

> Top down(하향식) vs Bottom up(상향식)

문제를 여러 작은 부분으로 분할하는 형식의 Top down(=분할 정복)

제일 작은 부분부터 해결해 나가면서 큰 부분을 해결하는 형식의 Bottom up(=동적 프로그래밍)

욕심쟁이 알고리즘(그리디 알고리즘 : Greedy Algorithm)

현재의 상태에서 가장 좋다고 판단되는 것부터 선택하여 나가는 방법. 때로는 그리디 알고리즘이 가장 효율적이고 간단할 때가 있기 때문에 알고리즘이 항상 최적인 해답을 주는지 확인이 필요함.

역추적 기법(Back Tracking)

가능한 모든 방법을 빠짐없이 탐색하여 문제를 해결하는 방법. 이 기법은 데이터의 양이 조금만 늘어나도 실행시간이 엄청나게 늘어나기 때문에 불필요한 탐색을 하지 않기 위해 가지치기 전략을 구사하여 실행시간을 줄여야 함.

분할 정복(Divide and Conquer)

주어진 문제를 원래 문제와 같은 형태의 작은 문제들로 나누어 문제를 해결하는 기법. 나누어진 문제가 해결이 어렵다면 해결할 수 있을 만큼 더 작은 문제들로 나누어 해결하는 방식

그래프 탐색 방법

> DFS(Depth First Search, 깊이 우선 탐색)

> BFS(Breadth First Search, 너비 우선 탐색)

#include <stdio.h>

int main() {
	int a[1001] = {0,}; //에라토스테네스의 체를 이용한 소수 찾기 알고리즘
	int i,j,count=0;    //acmicpc 1987번 문제풀이  
	int N;
	
	for(i=2;i<1001;i++)
		a[i]=1;
		
	for(i=2;i<1001;i++) {
		if(!a[i]) continue;
		
		for(j=i*2;j<1001;j+=i) {
			a[j]=0;
		}
	}
	
	scanf("%d",&N);
	
	for(i=0;i<N;i++) {
		scanf("%d",&j);
		if(a[j]) count++;
	}
	
	printf("%d",count);
}

에라토스테네스의 체? : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

1. 개념

이미 정렬된 자료에 대한 검색 알고리즘. 파일을 이분화하면서 검색 대상이 되는 키 값과 중간 위치의 값을 비교하면서 검색하는 방법.

앞에서부터 하나하나 검색하는 순차 검색보다 보다 효율성이 높다.

한번 비교할때마다 검색의 범위가 반으로 줄어드므로 수행 복잡도는 최소 O(log^n)

2. 과정

① 정렬된 데이터에서 첫 번재 위치를 left, 마지막 위치를 right로 설정

② middle 값을 구한다. (middle = (left + right) / 2)

③ middle 값이 찾고자 하는 데이터이면 검색을 종료.

   찾고자 하는 데이터가 아닐떄,

   1) 찾고자 하는 값 > middle 값일때

   left = middle+1로 재설정 후 2~3번의 과정 반복

   2) 찾고자 하는 값 < middle 값일때

   right = middle-1로 재설정 후 2~3번의 과정 반복

④ left>right이 되면 검색 종료(찾고자 하는 데이터 값이 없음)

3. Code

#include <stdio.h>

int binary_search(int a[], int n, int key) {
	int left, right, middle;
	left = 0;
	right = n-1;
	
	while(!(left>right)) {
		middle = (left+right)/2;
		if(key>a[middle])
			left = middle+1;
		else if(key<a[middle])
			right = middle-1;
		else
			return middle;
	}
	
	return -1;
}

int main() {
	int i, key, find, count;
	int array[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
	
	count = sizeof(array)/sizeof(int);
	printf("array[] 데이터 : ");
	for(i=0;i<count;i++) {
		printf("%d\t", array[i]);
	}
	printf("\n");
	
	printf("찾고자 하는 데이터를 입력해주세요 : ");
	scanf("%d", &key);
	
	find = binary_search(array, count, key);
	if(find > -1)
		printf("array[%d] = %d", find, array[find]);
	else
		printf("값이 존재하지 않습니다.\n");
}

1. 정렬(Sort)이란?

컴퓨터 기억 공간 내에 순서 없이 배열된 자료들 중에서 특정 항목을 키로 하여 키 값에 따라 오름차순 또는 내림차순으로 자료를 재배열하는 것

2. 수행되는 장소에 따른 정렬의 구분

1) 내부정렬 - 정렬되는 자료가 적어서 자료 전체의 정렬이 주기억 장치에서 이루어지는 정렬 방식

삽입법 : 레코드의 키를 비교하여 삽입하는 방식 ex) 삽입 정렬(insertion sort), 쉘 정렬(shell sort)

교환법 : 레코드의 키를 비교하여 교환하는 방식 ex) 선택 정렬(selection sort), 퀵 정렬(quick sort), 버블 정렬(bubble sort)

선택법 : 레코드의 키들 중에서 가장 큰 값이나 작은 값을 선택하는 방식 ex) 힙 정렬(heap sort)

병합법 : 레코드의 키를 병합하는 방식 ex) 병합 정렬(merge sort)

분배법 : 레코드의 키를 구성하는 각 자릿수를 특정 버킷에 분배하여 정렬하는 방식 ex) 기수 정렬(radix sort)

2) 외부정렬 - 정렬되어야 할 자료가 매우 많아 자료를 보조 기억 장치에 기억시켜 놓은 상태에서 주기억 장치에서 처리할 수 있는 양만큼을 가져와 정렬하고 보조 기억 장치에 저장하는 과정을 반복하면서 자료 전체의 정렬이 보조 기억 장치에서 이루어지는 정렬 방식

ex) 병합 정렬(merge sort)

3. 정렬에 따른 수행 속도 비교

삽입 정렬, 선택 정렬, 버블 정렬 : O(n^2)                                                                              

- 대량의 데이터를 정렬하는 방법으로는 이용 x

쉘 정렬 : 증분에 따라 성능이 조금씩 달라지만 일반적으로 O(n(logn)^2) ~ O(n^2)의 성능을 가짐      

- 속도면에서 빠르고 안정적임. 부분적으로 정렬되어 있을 때 더 효율적.

힙 정렬 : O(nlogn)

- 힙을 생성하는데 O(n)의 수행 과정을 거치고 n번 삭제하는데 O(nlogn)의 수행 과정을 거침. 수나 형태에 무관하게 거의 고른 성능을 보여줌.

퀵 정렬 : O(nlogn)

- 보통 pivot값은 배열의 끝의 값을 이용하지만 한 번의 탐색을 통해 average 값을 pivot 값으로 설정하면 효율을 높일 수 있다. 매우 빠르고 성능이 좋지만 구간이 넓을 경우에 한하고 구간이 어느 정도 좁혀지면 그다지 빠르지 않음. 분할된 데이터 수가 적다면 삽입 or 선택 정렬이 오히려 더 빠를 수 있음.

n개의 레코드 개수가 있을때 레코드 위치를 결정하기 위해 n번의 비교를 하고 서브 파일에 대해 n/2번 비교를 하고 계속해서 n/4, n/8 ... 번 비교를 하게 됨.

병합 정렬 :

2-way 병합 정렬 알고리즘 : O(m+n)

- 이미 정렬된 두 개의 파일을 정렬하여 한 개의 다른 파일로 만드는 것. 두개의 while문은 두 배열중 어느 한쪽이 끝나면 다른 한쪽에 있는 자료를 새로운 배열에 비교 없이 넣는 연산을 수행하므로 첫 번째 파일 개수를 m, 두 번째 파일 개수를 n이라 하면 두 개의 정렬된 파일을 병합하는데 이를 더한 수행 시간이 소요됨.

n-way 병합 정렬 알고리즘 : O(nlogn)

- n개의 데이터를 분할하는데 O(n), 분할을 한 번 할때마다 부분 배열의 길이가 절반으로 줄기 때문에 log₂n회 분할됨.

기수 정렬 : O(n)

- 각 버킷을 배열을 이용하기 보다는 연결리스트를 이용하여 처리하면 기억 장소를 절약할 수 있음.

  정렬될 자료의 개수가 n일때 비교 횟수는 각각의 레코드에 대해 n번씩 수행됨 -> O(n), 자리수가 b일때 O(bn)의 수행 시간이 걸리지만 b를 상수 취급.

4. 빅오표기법으로 본 수행 시간 비교(레코드의 수, 키값 무시. 병합정렬 제외)

기수 정렬(O(n)) > 퀵 정렬(O(nlogn)) > 힙 정렬(O(nlogn)) > 쉘 정렬(O(n(logn)^2) ~ O(n^2)) >= 삽입 정렬, 선택 정렬, 버블 정렬(O(n^2))