다이어트(무장해제 후 67.50kg) 중인
2015-08-28 08:06:39
일상
사람에게 아침식사 가능성이 희박하다는 사실은 매우 큰 초조함을 야기한다
그렇다 왜 아침애 샤워를 두번해서 이 사단을 일으켰단 말인가 이 물부족 국가에서!
▼ more
APS 강사 자료 재귀를 이용한 선택정렬
2015-08-23 18:24:22
컴퓨터
#include <iostream>
#define MAX_N 10
int A[MAX_N];
void selectSort(int k){
if(k==MAX_N-1) return;
int min = 100000;
int minIdx;
for(int i=k;i<MAX_N;i++){
if(A[i] < min){
min = A[i];
minIdx = i;
}
}
int temp = A[k];
A[k] = A[minIdx];
A[minIdx] = temp;
selectSort(k+1);
}
int main(){
A[0]= 8;
A[1]= 5;
A[2]= 1;
A[3]= 2;
A[4]= 1;
A[5]= 4;
A[6]= 3;
A[7]= 2;
A[8]= 9;
A[9]= 15;
selectSort(0);
return 0;
}
▼ more
Graph BFS(Queue), DFS(Recursive, Stack)
2015-08-19 00:00:49
컴퓨터
#include <iostream>
#define MAX_N 1000
using namespace std;
//map의 0 에 사이즈를 저장한 인접배열
int map[MAX_N+1][MAX_N+1];
int visit[MAX_N+1];
void DFS_Recursive(int n){
cout << " " << n;
visit [n] = 1;
for(int i=1;i<=map[n][0];i++){
if(!visit[map[n][i]])
DFS_Recursive(map[n][i]);
}
}
int stack[MAX_N+1];
int stack_p =0 ;
void DFS_Stack(int v){
stack[stack_p++] = v;
while (stack_p > 0){
v = stack[--stack_p];
if(!visit[v]){
cout << " " << v;
visit[v] = 1;
for(int w=1;w<=map[v][0];w++){
if(!visit[map[v][w]])
stack[stack_p++] = map[v][w];
}
}
}
}
int queue_p_begin = 0;
int queue_p_end = 0;
int queue[MAX_N+1];
void BFS_Queue(int v){
queue_p_begin = 0;
queue[queue_p_begin] = v;
queue_p_end = 1;
while (queue_p_begin < queue_p_end){
v = queue[queue_p_begin++];
if(!visit[v]){
cout << " " << v;
visit[v] = 1;
for(int w=1;w<=map[v][0];w++){
if(!visit[map[v][w]])
queue[queue_p_end++] = map[v][w];
}
}
}
}
int main(){
int T, test_case;
int N;
int src,dst;
freopen ( "sample_input.txt", "r", stdin );
cin >> T;
for(test_case = 1; test_case <= T; test_case++){
for(int i=0;i<=MAX_N; i++){
map[i][0] = 0;
}
cin >> N;
cout << "Graph" <<endl;
for(int i=0;i<N;i++){
cin >> src &\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0gt;> dst;
map[src][0]++;
map[src][map[src][0]] = dst;
cout << src << " -> "<<dst << endl;
}
for(int i=0;i<=MAX_N; i++) visit[i] = 0;
//BFS(Queue)
cout << "BFS(Queue):";
BFS_Queue(1);
cout << endl;
//DFS(Recursive)
cout << "DFS(Recu.):";
for(int i=0;i<=MAX_N; i++) visit[i] = 0;
DFS_Recursive(1);
cout << endl;
//DFS(Stack)
cout << "DFS(Stack):";
for(int i=0;i<=MAX_N; i++) visit[i] = 0;
stack_p =0;
DFS_Stack(1);
cout << endl;
//Dijkstra
}
return 0;
}
▼ more
Graph Dijkstra
2015-08-18 23:58:51
컴퓨터
#include <iostream>
#define MAX_N 1000
using namespace std;
//adjacent array version
//A의 0 에 사이즈를 저장한 인접배열
int A[MAX_N+1][MAX_N+1];
int maxNode;
int D[MAX_N+1]; // distance
int U[MAX_N+1]; // selected vertex set
int UN=0;
void dijkstra(int s){
U[s] = 1;
cout << (char)(s+'a') <<" ";
UN++;
//0 에서 해당 정점까지의 거리를 초기값으로 입력한다.
for(int i=0;i<=maxNode;i++){
D[i] = A[s][i];
}
while(UN<=maxNode){
//이미 선택되지 않은 정점중 가장 가까운 것을 찾는다.
int min = 1000;
int minIdx ;
for (int i=0;i<=maxNode;i++){
if( i!=s && !U[i] && min > D[i] && D[i]!=-1){
minIdx = i;
min = D[i];
}
}
U[minIdx] = 1;
UN++;
cout << (char)(minIdx + 'a') <<" ";
if(UN>maxNode){ break;} //it is really needed??
for(int i=0;i<=maxNode;i++){
if(A[minIdx][i]!=-1){
//i 로 바로갈까 아니면 다른데 들러서 갈까?
D[i] = (D[i] !=-1 && (D[i] < (D[minIdx] + A[minIdx][i])))?D[i]:(D[minIdx] + A[minIdx][i]);
}
}
}
//for(int i=0;i<=maxNode;i++){
// if(U[i]==0){
// cout << (char)(i + 'a') ;
// }
//}
cout << endl;
}
int main(){
int T, test_case;
int N;
char src,dst;
int weight;
freopen ( "sample_input.txt", "r", stdin );
cin >> T;
for(test_case = 1; test_case <= T; test_case++){
for(int i=0;i<=MAX_N; i++){
for (int j=0;j<=MAX_N;j++){
if(i==j)
\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 A[i][j] = 0;
else
A[i][j] =-1; // dijkstra 는 - 값을 다루지 않는다.
}
}
cin >> N;
cout << "Graph" <<endl;
maxNode =0;
for(int i=0;i<N;i++){
cin >> src >> dst >> weight;
A[src-'a'][dst-'a'] = weight;
if (src-'a'> maxNode){
maxNode = src-'a';
}
if (dst-'a'> maxNode){
maxNode = dst -'a';
}
}
for(int i=0;i<=maxNode;i++){
for(int j=0;j<=maxNode;j++)
cout << A[i][j] <<" ";
cout << endl;
}
//Aijkstra
dijkstra(0);
}
return 0;
}
▼ more