Mr.Linker ::

quickSort

프로그래밍 2008/03/27 20:37

import java.io.*;

public class Round02_Ex01 {

public static void swap(int[] num, int lhs, int rhs) {
int tmp = num[lhs];
num[lhs] = num[rhs];
num[rhs] = tmp;
}

public static void quickSort(int[] num, int l, int h) {

if (l < h) {
int m = partion(num, l, h);
quickSort(num, l, m - 1);
quickSort(num, m + 1, h);
}
}

public static int partion(int[] num, int l, int h) {

int firsthigh = l;
int p = h;

for (int i = 0; i < h; i++) {
if (num[i] < num[p]) {
swap(num, firsthigh, i);
firsthigh++;

}
}
swap(num, firsthigh, p);

return firsthigh;
}

public static void main(String[] ar) throws IOException {
int num[] = { 10, 20, 100, 50, 70 };

quickSort(num, 0, num.length - 1);

for (int i = 0; i < num.length; i++) {
System.out.println(num[i]);
}
}
}

이올린에 북마크하기(0)

이올린에 추천하기(0)

TAG 알고리즘

트랙백 0 : 댓글 0

Trackback Address :: http://misterlinker.tistory.com/trackback/21

#include <stdio.h>

#include <iostream>
#include <vector>

using namespace std;

void mergeSort(vector<int> arrayA, vector<int> arrayB, vector<int> &arrayRes)
{
int indexA=0, indexB=0;

while(indexA < arrayA.size() && indexB < arrayB.size()) {
if(arrayA[indexA] < arrayB[indexB]) {
arrayRes.push_back(arrayA[indexA]);
indexA++;
}
else {
arrayRes.push_back(arrayB[indexB]);
indexB++;
}
}
while(indexA < arrayA.size()) {
arrayRes.push_back(arrayA[indexA]);
indexA++;
}
while(indexB < arrayB.size()) {
arrayRes.push_back(arrayB[indexB]);
indexA++;
}

return;
}

int main()
{
int inputA[] = {1, 5, 37, 42, 61};
int inputB[] = {11, 15, 19, 48, 59};

vector<int> arrayA(&inputA[0], &inputA[sizeof(inputA)/sizeof(int)]);
vector<int> arrayB(&inputB[0], &inputB[sizeof(inputB)/sizeof(int)]);
vector<int> arrayRes;

mergeSort(arrayA, arrayB, arrayRes);

for(vector<int>::iterator vi=arrayA.begin(); vi != arrayA.end(); vi++) {
printf("%d ", *vi);
}
cout << endl;

for(vector<int>::iterator vi=arrayB.begin(); vi != arrayB.end(); vi++) {
printf("%d ", *vi);
}
cout << endl;

for(vector<int>::iterator vi=arrayRes.begin(); vi != arrayRes.end(); vi++) {
printf("%d ", *vi);
}
cout << endl;

return 1;
}

이올린에 북마크하기(0)

이올린에 추천하기(0)

TAG 알고리즘

트랙백 0 : 댓글 0

Trackback Address :: http://misterlinker.tistory.com/trackback/14

Insertion Sort

프로그래밍 2007/11/18 13:31

#include <stdio.h>

#include <vector>
#include <iostream>

using namespace std;

void insertion_sort(vector<int> &array)
{
int i, j, cur_data, array_length = array.size();

//printf("array_length=>[%d]\n", array_length);
for(i=1; i<array_length; i++) {
cur_data = array[i];
for(j=i-1; j>=0 && (array[j] > cur_data); j--) {
array[j+1] = array[j];
}
array[j+1] = cur_data;
}

return;
}

int main()
{
int a[] = {26, 5, 37, 1, 61, 11, 59, 15, 48, 19};

vector<int> array(&a[0], &a[sizeof(a)/sizeof(int)]);

for(vector<int>::iterator vi=array.begin(); vi != array.end(); vi++) {
printf("%d ", *vi);
}
cout << endl;

insertion_sort(array);

for(vector<int>::iterator vi=array.begin(); vi != array.end(); vi++) {
printf("%d ", *vi);
}
cout << endl;

return 1;
}

이올린에 북마크하기(0)

이올린에 추천하기(0)

TAG 알고리즘

트랙백 0 : 댓글 0

Trackback Address :: http://misterlinker.tistory.com/trackback/13

Selection Sort

프로그래밍 2007/11/18 13:29

#include <stdio.h>

#include <iostream>
#include <vector>

using namespace std;

void selectionSorter(vector<int> &array)
{
vector<int>::iterator imin;
int tmp;

for(vector<int>::iterator i=array.begin(); i!= array.end(); i++) {
imin = i;
for(vector<int>::iterator j=i; j!= array.end(); j++) {
if(*imin > *j) {
imin = j;
}
}
tmp = *i;
*i = *imin;
*imin = tmp;

/*
for(vector<int>::iterator vi=array.begin(); vi != array.end(); vi++) {
printf("%d ", *vi);
}
cout << endl;
*/

}

return;
}

int main(void)
{
int input[] = {26, 5, 37, 1, 61, 11, 59, 15, 48, 19};
vector<int> array(&input[0], &input[sizeof(input)/sizeof(int)]);

for(vector<int>::iterator vi=array.begin(); vi != array.end(); vi++) {
printf("%d ", *vi);
}
cout << endl;

selectionSorter(array);

for(vector<int>::iterator vi=array.begin(); vi != array.end(); vi++) {
printf("%d ", *vi);
}
cout << endl;

return 1;
}

이올린에 북마크하기(0)

이올린에 추천하기(0)

TAG 알고리즘

트랙백 0 : 댓글 0

Trackback Address :: http://misterlinker.tistory.com/trackback/12

infix를 postfix로 바꾸기 예제

프로그래밍 2007/11/12 23:50

한국정보올림피아드 강의 자료에 나와 있는 알고리즘을 따라서 코딩해 봤다..

1. 피연산자가 나오면 결과 배열에 차례로 담는다.
2. 연산자가 나오는 경우 스택에 집어넣는다. 스택에 넣기전에 스택 위에 위치한 자신보다 우선순위가 같거나 높은 연산자들을 pop시켜 결과 배열에 담는다.
3. 여는 괄호'('가 나오는 경우 스택에 집어넣는다.
4. 닫는 괄호')'가 나오는 경우 '('가 나올 때까지 stack에 담겨 있는 연산자를 pop시켜 결과 배열에 넣는다.

수식을 다 살펴본 후 스택에 담긴 연산자들을 모두 pop시켜 결과 배열에 넣는다.

#include <stdlib.h>

#include <iostream>
#include <vector>
#include <stack>
#include <list>
#include <string>

using namespace std;

#define printpos(func) cout << __FILE__ << ", " << func << ", " << __LINE__ << endl;

int getPriNum(char ch) {
if(ch == 'x') return 4;
else if(ch == '%') return 4;
else if(ch == '+') return 3;
else if(ch == '-') return 3;
else if(ch == '(') return 0;
else return 0;
}

int main(void)
{
const char *numForm="5+(4-2)-3x2";
list<char> infixList(&numForm[0], &numForm[strlen(numForm)]);

stack<char> opStack;
list<char> resList;

for(list<char>::iterator it=infixList.begin(); it!=infixList.end(); it++) {
//printf("%c:%d\n", *it, isdigit(*it));
if(isdigit(*it) != 0) {
resList.push_back(*it);
}
else {
if(*it == '(') {
opStack.push(*it);
}
else if(*it == ')') {
while(opStack.top() != '(') {
resList.push_back(opStack.top());
opStack.pop();
}
opStack.pop();
}
else {
if(opStack.empty() == 0) {
if(getPriNum(opStack.top()) >= getPriNum(*it)) {
//printf("%c, %c\n", opStack.top(), *it);
resList.push_back(opStack.top());
opStack.pop();
}
}
opStack.push(*it);
}
}

/*
printf("opStack.size()=>%d\n", opStack.size());
printf("=========\n");
stack<char> opTmpStack = opStack;
while(opTmpStack.empty() == 0) {
printf("%c\n", opTmpStack.top());
opTmpStack.pop();
}

printf("---------\n");

for(list<char>::iterator itRes=resList.begin(); itRes!=resList.end(); itRes++) {
printf("%c\n", *itRes);
}
printf("=========\n\n");
*/
}

/*
printf("opStack.size()=>%d\n", opStack.size());
printf("=========\n");
stack<char> opTmpStack = opStack;
while(opTmpStack.empty() == 0) {
printf("%c\n", opTmpStack.top());
opTmpStack.pop();
}
printf("---------\n");
*/

for(list<char>::iterator itRes=resList.begin(); itRes!=resList.end(); itRes++) {
printf("%c\n", *itRes);
}
//printf("=========\n\n");

return 1;
}

이올린에 북마크하기(0)

이올린에 추천하기(0)

TAG infix to postfix, 알고리즘

트랙백 0 : 댓글 1

Trackback Address :: http://misterlinker.tistory.com/trackback/9

왕우 2007/11/14 11:48 댓글주소 | 수정/삭제 | 댓글
와..형..요즘 공부 좀 하나봐요..^^;
ㅋㅋ 잘 지내시죠??

Write a comment

: 이름

: 비밀번호

: 홈페이지

비밀글

java에서 main이 static인 이유??

프로그래밍 2007/11/07 13:35

자바프로그램 하면서 무의식적으로 했던거..

public static void main(String[] args) {
;
}

여기에 static이라는걸 왜 붙여주고 있었지? 학교때 배운거라 넘 오래되어서 다시 찾아봤다..

static 키워드의 의미 :
1. static으로 선언된 변수는 객체가 n개 생성되더라도 하나의 메모리 공간만 가지고 모든

객체는 static 변수를 공유한다.
2. static으로 선언된 변수는 객체가 생성되기 전에 메모리에 할당된다.

변수와 동일하게 static으로 선언된 method도 객체가 생성되기 전에 메모리에 할당된다.
main method같은 경우 객체가 생성되기 전에 메모리에 올라가 있어야 하므로 static으로 선언되어야 한다.

이올린에 북마크하기(0)

이올린에 추천하기(0)

트랙백 0 : 댓글 0

Trackback Address :: http://misterlinker.tistory.com/trackback/7

Queue 알고리즘 예제

프로그래밍 2007/11/04 16:31

바이러스가 1마리 있다. 이 바이러스의 수는 1초 후에 2배로 불어 날 수도 있고 1/3(소수점 이하 버림)로 줄 수도 있다. 현재 몇 마리의 바이러스가 존재한느지 주어질 때 1마리의 바이러스에서부터 최소 몇 초의 시간이 흘러 현재 상태가 되었는지를 구하시오
ex)현재 바이러스가 7마리 있다면,
1->2->4->8->16->32->64->21->7

#include <stdio.h>
#include <string.h>

#include <iostream>

using namespace::std;

#define MAX_QUEUE_SIZE 100

class Data
{
public:
int num;
int time;

void set(int num, int time)
{
this->num = num;
this->time = time;
}

int getNum() {
return num;
}

int getTime() {
return time;
}

void view()
{
printf("[%d]:[%d]\n", num, time);
}

Data Mul2(Data input)
{
Data tmp;
tmp.num = input.num*2;
tmp.time = input.time+1;
return tmp;
}

Data Div3(Data input)
{
Data tmp;
tmp.num = input.num/3;
tmp.time = input.time+1;
return tmp;
}

};

class Queue
{
public:
int front, near;
Data queue[MAX_QUEUE_SIZE];
Data *tmpData;

void init()
{
memset(queue, 0, sizeof(Data)*MAX_QUEUE_SIZE);
front = -1;
near = 0;
}

void view()
{
printf("front:[%d], near:[%d]\n", front, near);
for(int i=near; i<=front; i++) {
queue[i].view();
}
}

void insert(Data input)
{
front++;
queue[front] = input;
}

Data remove()
{
Data tmp;
tmp = queue[near];
near++;
return tmp;
}
};

int main(void)
{
Queue myQueue;
Data myData, myDataMul2, myDataDiv3;
int time;

myQueue.init();
myData.set(1, 0);
myQueue.insert(myData);

while(1) {
myQueue.view();
//printf("i=>[%d]\n", i);
myData = myQueue.remove();
myData.view();

myDataMul2 = myData.Mul2(myData);
myDataMul2.view();
if(myDataMul2.getNum() == 7) {
time = myDataMul2.getTime();
break;
}
if(myDataMul2.getNum() > 0) {
myQueue.insert(myDataMul2);
}

myDataDiv3 = myData.Div3(myData);
myDataDiv3.view();
if(myDataDiv3.getNum() == 7) {
time = myDataDiv3.getTime();
break;
}
if(myDataDiv3.getNum() > 0) {
myQueue.insert(myDataDiv3);
}
}
//myQueue.view();

printf("answer %d times\n", time);

return 0;
}

이올린에 북마크하기(0)

이올린에 추천하기(0)