이너의 Computer Library

1. 개념

사전에서 단어를 찾는 것처럼 특정 단어가 있을 만한 부분으로 탐색 범위를 제한해 검색하는 방법. 따라서 저장된 데이터들이 미리 정렬된 형태를 가지고 있어야함.

2. 과정

① 찾고자 하는 자료에서 첫 번째 위치를 left, 마지막 위치를 right로 한다.

② 중간값 위치 middle을 구한다.

middle = left + (right-left) * ((key-a[left]) / (a[right]-a[left]))

③ 중간값 array[middle]가 원하는 값과 같으면 검색을 종료한다.

   (array[middle] > 원하는 값) left = middle+1

   (array[middle] < 원하는 값) right = middle-1

④ left <= right 이면 ③번 과정 반복

3. Code

#include <stdio.h>

int inter_search(int a[], int n, int key) {
	int left, right, middle;
	left = 0;
	right = n-1;
	
	while(left <= right) {
		middle = left + (right-left) * ((key-a[left]) / (a[right]-a[left]));
		
		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[] = {5,7,12,15,20,22,25,27,30,32};
	
	count = sizeof(array) / sizeof(int);
	
	printf("배열 array[] :");
	for(i=0;i<count;i++) 
		printf("%5d",array[i]);
	printf("\n");
	
	printf("찾고자 하는 데이터 : ");
	scanf("%d",&key);
	
	find = inter_search(array, count, key);
	
	if(find < 0)
		printf("찾고자 하는 값이 없다..");
	else
		printf("array[%d] = %d",find,array[find]);
}

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

#include <iostream>
#include <vector>

using namespace std;

vector<pair<int, int> > v;
bool isDeleted[1001];
int n;

int main() {
	scanf("%d",&n);
	
	for(int i=0;i<n;i++) {
		int temp;
		scanf("%d",&temp);
		v.push_back(make_pair(temp,i+1));
	}
	
	int pos = 0;
	
	while(1) {
		printf("%d ",v[pos].second);
		int haveToGo = v[pos].first;
		isDeleted[pos] = true;
		
		int flag = 0;
		for(int i=0;i<n;i++) 
			if(!isDeleted[i]) flag = 1;
		
		if(!flag) break;
		
		if(haveToGo > 0) {
			while(haveToGo != 0) {
				haveToGo--;
				pos++;
				
				if(pos >= n) pos = 0;
				
				if(isDeleted[pos]) {
					haveToGo++;
					continue;
				}
			}	
		} else if(haveToGo < 0) {
			while(haveToGo != 0) {
				haveToGo++;
				pos--;
				
				if(pos < 0) pos = n-1;
				
				if(isDeleted[pos]) {
					haveToGo--;
					continue;
				}
			}
		}
	}	
}

vector를 이용해 움직일 거리와 index를 삽입하고 isDeleted를 이용해 풍선이 터졌는지 안터졌는지 체크하며 이동시키는 과정을 구현했습니다. flag로 모든 풍선이 터지면 while문을 빠져나오게끔 하였습니다.

#include <iostream>
#include <vector>

using namespace std;

int a[20];
int n,s;
int cnt = 0;
vector<int> v;

void cnt_case(int n, int r, int index) {
	
	if(r == 0) {
		int sum = 0;
		for(int i=0;i<v.size();i++) 
			sum += v.at(i);
			
		if(sum == s) cnt++;
		return;
	} 


	if(n == r) {
		int sum = 0;
		
		for(int i=0;i<n;i++) 
			v.push_back(a[i+index]);
		
		for(int i=0;i<v.size();i++) 
			sum += v.at(i);
			
		if(sum == s) cnt++;
		
		for(int i=0;i<n;i++) 
			v.pop_back();
		
		return;
	} 
	
	v.push_back(a[index]);
	cnt_case(n-1,r-1,index+1);
	v.pop_back();
	cnt_case(n-1,r,index+1);

}


int main() {
	scanf("%d %d",&n,&s);
	
	for(int i=0;i<n;i++) 
		scanf("%d",&a[i]);
	
	for(int i=1;i<=n;i++) {
		cnt_case(n,i,0);
	}
	
	printf("%d",cnt);
}

조합(comb)를 사용해서 풀었습니다(조합 알고리즘 : http://2nners-computer.tistory.com/21?category=756885)

nC1 부터 nCn까지의 부분집합들을 조합으로 꺼내 vector에 집어넣은 후 그 합을 s와 비교하는 원리입니다 :)

#include <iostream>
#include <vector>

using namespace std;

int data[] = {1,2,3,4};
vector<int> v;

int comb(int n, int r, int index) {
	int sum = 0;
	
	if(r == 0) {
		for(int i=0;i<v.size();i++) {
			printf("%d ",v.at(i));
		}
		printf("\n");
		return 1;
	} 

	if(n == r) {
		for(int i=0;i<n;i++) {
			v.push_back(data[i+index]);
		}
		for(int i=0;i<v.size();i++) {
			printf("%d ",v.at(i));
		}
		printf("\n");
		for(int i=0;i<n;i++) {
			v.pop_back();
		}
		return 1;
	} 
	
	v.push_back(data[index]);
	sum += comb(n-1,r-1,index+1);
	v.pop_back();
	sum += comb(n-1,r,index+1);
	
	return sum;
}

int main() {
	int r;
	int n = sizeof(data) / sizeof(int);
	scanf("%d",&r);
	
	printf("sum : %d", comb(n,r,0));
} 

nCr = {n x (n-1) x ... x (n-r+1)} / {r x (r-1) x ... 2 x 1} -> 서로 다른 n개에서 r개를 뽑는 경우의 수

알고리즘의 원리 : nCr = (n-1)C(r-1) + (n-1)Cr 와 nCn = 1, nC0 = 1임을 이용. vector에 그때그떄 정해진 수를 넣었다 뺐다를 반복.

#include <iostream>

using namespace std;

int data[] = {1,2,3,4};

void swap(int i, int j) {
	int temp;
	
	if(i == j) return;
	temp = data[i];
	data[i] = data[j];
	data[j] = temp;
}

int perm(int n, int r, int index) {
	
	int sum = 0;
	
	if(r == index) {
		for(int i=0;i<r;i++) {
			printf("%d ",data[i]);
		}
		printf("\n");
		return 1;
	}
	
	for(int i=index;i<n;i++) {
		swap(i,index);
		sum += perm(n,r,index+1);
		swap(i,index);
	}
	
	return sum;
}

int main() {
	int r;
	int n = sizeof(data) / sizeof(int);
	scanf("%d",&r);
	
	printf("sum : %d",perm(n,r,0));
} 

nPr = n x (n-1) x (n-2) x ... x 1 -> 서로 다른 n개에서 r개를 뽑아 나열하는 경우의 수

알고리즘의 원리 : 한 경우의 수에서 첫번째를 고정시키고 그 뒤의 나머지 수들을 swap함수로 변환하면서 경우의 수를 세어 간다. swap 함수를 두번 쓰는 이유는 바꾸고 다시 제자리로 돌려놓아야 하기 때문이다.

#include <iostream>

using namespace std;

void printDecimal(int a, int b) {
	int iter=0;
	
	if(a==0) {
		 cout << "0";
		 return;
	}
	while(a>0) {
		if(iter++ == 1) cout << '.';
		cout << a/b;
		a = (a%b)*10;
	}
}

int main() {
	printDecimal(0,400);
	printDecimal(1,8);
}

(단, a,b > 0이고, 무한소수가 아님)

#include <iostream>
#include <queue>

using namespace std;

int graph[1001][1001];
int check[1001] = {0,};
queue<int> q;

void DFS(int start, int max) {
	printf("%d ",start);
	check[start] = 1;
	
	for(int i=1;i<=max;i++) {
		if(graph[start][i] == 1 && !check[i]) {
			check[i] = 1;
			DFS(i,max);
		}
	}
}

void BFS(int start, int max) {
	
	for(int i=0;i<=max;i++) 
		check[i] = 0;
	
	q.push(start);
	check[start] = 1;
	
	while(!q.empty()) {
		int current = q.front();
		q.pop();
		
		printf("%d ",current);
		
		for(int i=1;i<=max;i++) {
			if(graph[current][i] == 1 && !check[i]) {
				check[i] = 1;
				q.push(i);
			}
		}
	}
}

int main() {
	int N,M,V;
	
	scanf("%d %d %d",&N,&M,&V);
	
	for(int i=0;i<M;i++) {
		int u,v;
		scanf("%d %d",&u,&v);
		
		graph[u][v] = 1;
		graph[v][u] = 1;
	}
	
	
	DFS(V,N);
	printf("\n");
	BFS(V,N);
}

DFS와 BFS의 사용법을 익히는 문제입니다.

간단히 설명을 끄적이자면, 

트리(or 그래프)의 대표적인 탐색 방법 두가지에는

DFS(Depth First Search, 깊이 우선 탐색) : 정점과 이어진 간선을 쭉 따라가다 더이상의 정점과 이어지지 않으면 이전의 정점으로 돌아와 다른 길로 우회하면서 탐색하는 방법. 주로 스택을 이용하여 구현함.

BFS(Breadth First Search, 너비 우선 탐색) : 큐를 이용해 이어지는 간선을 push pop함으로써 탐색하는 방법.

이라고 할 수 있겠습니다.

위 코드는 무방향 그래프를 인접 행렬로써 정점과 간선을 입력받고 DFS와 BFS를 사용하여 탐색 과정을 출력해주는 예제입니다.

이 문제를 풀면서 중요한게 하나 있습니다. 문제를 보시면 "단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다." 라는 조건이 존재합니다. 따라서 저처럼 인접 행렬로 for문을 이용해 정점 번호가 작은 것부터 탐색하지 않고 인접 리스트를 사용하셨다면 오름차순으로 정렬하실 필요가 있습니다. vector로 푸셨다면 sort(vector_name.begin(), vector_name.end())를 사용하셔야 되겠습니다.

앞으로 DFS BFS문제 풀때 유용하게 Ctrl+C,V.. 가 아니라 참고용..으로 쓰시길 바랍니다 :)

#include <iostream>

int main() {
	int N,M;
	int D[301][301];
	
	scanf("%d %d",&N,&M);
	
	for(int i=1;i<=N;i++) 
		D[i][1] = i-1;
	for(int i=1;i<=M;i++) 
		D[1][i] = i-1;
	
	for(int i=2;i<=N;i++) {
		for(int j=2;j<=M;j++) {
			if(i%2 == 0) D[i][j] = 1+D[i/2][j]*2;
			else D[i][j] = 1+D[i/2][j]+D[i-i/2][j];
		}
	}
	
	printf("%d",D[N][M]);
}

DP를 사용해서 풀어보았습니다.

D[i][j] = i x j 의 초콜릿을 자르는데 필요한 횟수

1 x n 또는 n x 1 의 초콜릿을 자르는데 필요한 횟수는 n-1번!

<점화식>

가로 길이가 짝수이면 절반으로 자르는데 필요한 1번을 더하고 나뉜 두조각을 자르는데 필요한 횟수를 더합니다.

가로 길이가 홀수이면 가로길이를 i/2와 i-(i/2)로 나누어 자르는데 필요한 1번을 더하고 위와 같이 나뉜 두조각을 더합니다.

-> 더 쉽게 푸는 법(드래그)

이 문제를 다풀고 뒤늦게 알아챘던거지만 사실은 DP를 쓸 필요 없이 그냥 N*M-1하면 답이였네요 ㅎㅎ DP로 풀었다는 것에 의의를 두..려.. 합니다ㅠㅠ

1. itoa (need to include stdlib.h)

int a = 10;
char *convStr = itoa(a);
string str = string(convStr);

2. to_string

int a = 10;
string s = to_string(a);

3. sstream (need to include sstream)

string intToString(int n) {
	stringstream ss;
	ss << n;
	return ss.str();
}

int main() {
    
    int a = 10;
    string s = intToString(a);

}

4. sprintf

int a = 10;
char buf[10];
string str;
	
sprintf(buf,"%d",a);
str = buf;