'Programming'에 해당되는 글 14건

  1. 2013.07.18 Binary Search
  2. 2013.07.13 좋은 사이트..
  3. 2013.07.09 c++ 급여 관리 시스템
  4. 2013.05.12 BlackJack in Python

Binary Search

2013. 7. 18. 01:41 from Programming

이진 탐색 알고리즘에 관해 간단하게 포스팅해보려 합니다.


#include <stdio.h>

int BSearch(int ar[], int len, int target){

int first = 0;

int last = len-1;

int mid;


while(first<=last){

mid = (first + last) / 2;


if(target == ar[mid]){

return mid;

}

else {

if(target < ar[mid])

last = mid - 1;

else

first = mid + 1;

}

}

return -1;

}


int main(void){

int arr[] = {1, 3, 5, 7, 9};

int idx;


idx = BSearch(arr, sizeof(arr)/sizeof(int), 7);

if(idx == -1)

printf("탐색 실패 \n");

else

printf("타겟 저장 인덱스: %d\n", idx);


idx = BSearch(arr, sizeof(arr)/sizeof(int), 4);

if(idx == -1)

printf("탐색 실패 \n");

else

printf("타겟 저장 인덱스: %d\n", idx);


return 0;

}

 


위 소스에서 최악의 경우에 대한 시간 복잡도 함수는

k를 n이 1이 되기까지 2로 나눈 횟수라 할때  T(n) = k + 1 입니다.


n이 1이 되기까지 2로 나눈 횟수가 k이므로 다음과 같은 식도 세울수 있습니다.



저 식을 정리해주면



여기서 이 식에 로그를 취하고 정리해주면



따라서 결국



가 되는데 자료구조를 조금이라도 공부해보신 분이라면 알수 있는 내용이 

저 T(n) 구조를 취한 로그 그래프가 바로 x축을 데이터수라하고 y축을 연산횟수라 하였을때 

가장 바람직한 알고리즘이 된다는 것입니다.


결국 이진탐색알고리즘은 좋은 알고리즘!





'Programming' 카테고리의 다른 글

[dovelet]-crypt  (0) 2014.01.20
os 판별 코드  (0) 2013.10.11
좋은 사이트..  (0) 2013.07.13
c++ 급여 관리 시스템  (0) 2013.07.09
BlackJack in Python  (0) 2013.05.12
Posted by xer0s :

좋은 사이트..

2013. 7. 13. 03:33 from Programming

최근에 ruby on rails도 관심이 생기고 구글링도 하면서 뒤져본 결과

http://www.tutorialspoint.com/index.htm

위 사이트를 발견했습니다. 강의들도 다 깔끔하고 좋고 pdf들도 다 제공되고

assembly부터 해서 여러 프로그래밍 강의들도 있더군요

공유합니다.


// 이 글 쓰면서 하나 ruby on rails 튜토리얼 괜찮은거 하나 더 찾았네요.

// http://ruby.railstutorial.org/ruby-on-rails-tutorial-book


'Programming' 카테고리의 다른 글

[dovelet]-crypt  (0) 2014.01.20
os 판별 코드  (0) 2013.10.11
Binary Search  (0) 2013.07.18
c++ 급여 관리 시스템  (0) 2013.07.09
BlackJack in Python  (0) 2013.05.12
Posted by xer0s :

c++ 급여 관리 시스템

2013. 7. 9. 01:45 from Programming

요즘 c++ 배우고 있는데 가상함수 복잡복잡 하네요



#include <iostream>

#include <cstring>

using namespace std;


class Employee

{

private:

char name[100];

public:

Employee(char * name)

{

strcpy(this->name, name);

}

virtual int GetPay() const =0;

virtual void ShowSalaryInfo() const =0;


    void ShowYourName() const

{

cout<<"Name: "<<name<<endl;

}

};


class PermanentWorker : public Employee

{

private:

int salary;

public:

PermanentWorker(char * name, int money) : Employee(name), salary(money)

{ }

int GetPay() const

{

return salary;

}

void ShowSalaryInfo() const

{

ShowYourName();

cout<<"salary: "<<GetPay()<<endl<<endl;

}

};


class EmployeeHandler

{

private:

Employee * empList[50];

int empNum;

public:

EmployeeHandler() : empNum(0)

{ }

void AddEmployee(Employee * emp)

{

empList[empNum++]=emp;

}

void ShowAllSalaryInfo() const

{

}

void ShowTotalSalary() const

{

int sum=0;

cout<<"salary sum: "<<sum<<endl;

}

~EmployeeHandler()

{

for(int i=0; i<empNum; i++)

delete empList[i];

}

};


class TemporaryWorker : public Employee

{

private:

int workTime;

int payPerHour;

public:

TemporaryWorker(char * name, int pay) : Employee(name), workTime(0), payPerHour(pay)

{ }

void AddWorkTime(int time)

{

workTime+=time;

}

int GetPay() const

{

return workTime * payPerHour;

}

void ShowSalaryInfo() const

{

ShowYourName();

cout<<"salary: "<<GetPay()<<endl<<endl;

}

};


class SalesWorker : public PermanentWorker

{

private:

int salesResult;

double bonusRatio;

public:

SalesWorker(char * name, int money, double ratio) : PermanentWorker(name, money), salesResult(0), bonusRatio(ratio)

{ }

void AddSalesResult(int value)

{

salesResult+=value;

}

int GetPay() const

{

return PermanentWorker::GetPay() + (int)(salesResult * bonusRatio);

}

void ShowSalaryInfo() const

{

ShowYourName();

cout<<"salary: "<<GetPay()<<endl<<endl;

}

};


int main(void)

{

EmployeeHandler handler;


handler.AddEmployee(new PermanentWorker("kim", 1000));

handler.AddEmployee(new PermanentWorker("lee", 1500));


TemporaryWorker * alba = new TemporaryWorker("jung", 700);

alba->AddWorkTime(5);

handler.AddEmployee(alba);


SalesWorker * seller = new SalesWorker("hong", 1000, 0.1);

seller->AddSalesResult(7000);

handler.AddEmployee(seller);


handler.ShowAllSalaryInfo();


handler.ShowTotalSalary();

return 0;



'Programming' 카테고리의 다른 글

[dovelet]-crypt  (0) 2014.01.20
os 판별 코드  (0) 2013.10.11
Binary Search  (0) 2013.07.18
좋은 사이트..  (0) 2013.07.13
BlackJack in Python  (0) 2013.05.12
Posted by xer0s :

BlackJack in Python

2013. 5. 12. 19:04 from Programming


#BlackJack rules can be found here http://www.114pda.com/game/card/blackjack_rule.htm

import os import random def game(): os.system("cls") print "WELCOME TO PYTHON BLACKJACK" Cards = [1,2,3,4,5,6,7,8,9,10,11,12,13,14] computerHand = deal() playerHand = deal() print "-------START GAME-------" print "Computer Hand: " + str(computerHand[0]) print "Player Hand: " + str(playerHand) print "\n-------Current Score-----" if(computeScore(playerHand) == 21): print "21! You win!" message() elif(computeScore(computerHand) == 21): print "21! Computer Wins!" message() print computeScore(playerHand) cardHit = raw_input("Do you want to hit (Y/N): ") while(cardHit == "y" or cardHit == "Y" ): hit(playerHand) print "\n------NEW HAND SCORE------" print playerHand print computeScore(playerHand) if(len(playerHand) == 5 and computeScore(playerHand) < 21): print "Less than 5 and Under 21: YOU WIN " message() elif(bust(playerHand) == 1): print "BUST. You lose" message() else: cardHit = raw_input("Do you want to hit (Y/N): ") print "\n-------Computer Turn------" if(computeStrategy(computerHand) == "Hit"): hit(computerHand) print computerHand else: print "I'm done." print computerHand print "\n--------DETERMINE WINNER------" print "COMPUTER: " + str(computeScore(computerHand)) print "PLAYER : " + str(computeScore(playerHand)) if(winner(computerHand,playerHand) == "hand1" and bust(computerHand)==0): print "Computer won" elif(winner(computerHand,playerHand) == "hand2" and bust(playerHand) == 1): print "Computer won" elif(winner(computerHand,playerHand) == "hand1" and bust(computerHand) == 1): print "Player Won" elif(winner(computerHand,playerHand) == "hand2" and bust(playerHand) == 0): print "Player Won" message() def message(): again = raw_input("Do you want to play again? (Y/N) : ") if(again == "Y" or again == "y"): game() else: print "\n\n-------Thank you for playing!--------\n\n" exit() def deal(): random1 = random.randint(1,14) random2 = random.randint(1,14) if (random1 == 11):random1 = "J" if (random1 == 12):random1 = "Q" if (random1 == 13):random1 = "K" if (random1 == 14):random1 = "A" if (random2 == 11):random2 = "J" if (random2 == 12):random2 = "Q" if (random2 == 13):random2 = "K" if (random2 == 14):random2 = "A" hand = [random1,random2] return hand def computeScore(hand): total = 0 for cards in hand: if cards == "J" or cards == "Q" or cards == "K": total+= 10 elif cards == "A": if total == 11: total+= 1 else:total+= 11 else: total += cards return total def hit(hand): newCard = random.randint(1,14) if (newCard == 11):newCard = "J" if (newCard == 12):newCard = "Q" if (newCard == 13):newCard = "K" if (newCard == 14):newCard = "A" hand.append(newCard) return hand def computeStrategy(hand): strategy = "" if (computeScore(hand) > 15): strategy = "Stay" if (computeScore(hand) <=15): strategy = "Hit" return strategy def winner(hand1,hand2): score1 = computeScore(hand1) score2 = computeScore(hand2) if score1 > 21: return "hand2" if score2 > 21: return "hand1" if(score1 > score2): return "hand1" else: return "hand2" def bust(hand): if computeScore(hand) >= 21: return 1 else: return 0 if __name__ == "__main__": game()


'Programming' 카테고리의 다른 글

[dovelet]-crypt  (0) 2014.01.20
os 판별 코드  (0) 2013.10.11
Binary Search  (0) 2013.07.18
좋은 사이트..  (0) 2013.07.13
c++ 급여 관리 시스템  (0) 2013.07.09
Posted by xer0s :