'Architecture for Software/Algorithm'에 해당하는 글 6건

최대 공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘을 올립니다.
휴~ 모두 간만에 하나 헷갈리는군요~ Java로 최대 공약수 구하는 알고리즘을 찾는 분에게 도움이 되었으면 좋겠습니다.
/**
 * Copyright (C) 2009, http://www.softwareinlife.com
 *
 * This file is part of "Software in Life".
 *
 * "Vision Software in Life" is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see .
 */
package com.softwareinlife.codes;

/**
 * GCD
 * 
 * @author Jang, Sun-Jin (jangsunjin@softwareinlife.com)
 * @date 2009. 11. 9.
 * 
 */
public class GCD {

	public static int count = 0;

	/**
	 * Constructor
	 */
	public GCD() {
		super();
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		GCD gcd = new GCD();
		int res = gcd.solve(15135, 9823);
//		int res = gcd.solve(3000, 2025);
//		int res = gcd.solve(280, 30);
		
		System.out.print("The Greatest Common Divisor: " + res);
		System.out.print("\t");
		System.out.print("(Count: " + count + ")");
	}

	/**
	 * Solve
	 * 
	 * @param j
	 * @param i
	 */
	private int solve(int u, int v) {
		int r = 0;
		int c = 0;

		if (u > v) {
			r = u % v;
			c = v;
		} else {
			r = v % u;
			c = u;
		}

		count ++;
		
		if (r == 0) {
			return c;
		} else {
			return solve(r, c);
		}
	}
}

저작자 표시 비영리
신고

'Architecture for Software > Algorithm' 카테고리의 다른 글

최대 공약수 구하기  (0) 2009.11.09
RLE(Run-Length Encoding) 알고리즘  (2) 2009.11.09
Top Coder에 도전하세요!  (4) 2009.01.01
Algorithm 이란  (0) 2008.11.17
The 3n+1 Problem  (3) 2008.11.11
스택(Stack)  (0) 2008.10.08

WRITTEN BY
jangsunjin
전세계 사람들의 삶의 질을 높일 수 있는 소프트웨어를 만들어 함께 나누는 것이 꿈입니다. 이 세상 그 무엇보다 사람이 가장 소중합니다.

받은 트랙백이 없고 , 댓글이 없습니다.
secret
나름 Java로 풀어본 RLE 입니다. O(n)이 되도록 신경썼는데~ 잘 풀어진건지 모르겠네요~
고수님들의 많은 의견 부탁드립니다.

참고로 RLE(Run-Length Encoding)는 연속적인 데이터나 문자열 등을 압축하는 알고리즘에 하나입니다. 대표적인 BMP가 이러한 RLE를 사용하여 압축합니다.


/**
 * Copyright (C) 2009, http://www.softwareinlife.com
 *
 * This file is part of "Software in Life".
 *
 * "Vision Software in Life" is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see .
 */
package com.softwareinlife.codes;

/**
 * RLE
 * 
 * @author Jang, Sun-Jin (jangsunjin@softwareinlife.com)
 * @date 2009. 11. 9.
 * 
 */
public class RLE {

	/**
	 * Constructor
	 */
	public RLE() {
		super();
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		RLE rle = new RLE();
		
		String result = rle.solve("qwwwwwwweeeeerrtyyyyyqqqqwEErTTT");
//		String result = rle.solve("caaab");
		
		System.out.println(result);
	}

	/**
	 * Solve the Problem
	 * 
	 * @param seed
	 * @return
	 */
	private String solve(String seed) {
		StringBuffer rle = new StringBuffer();

		int i = 0;
		int j = 1;
		while (i < seed.length()) {
			char current = seed.charAt(i);
			char after = seed.charAt(j);

			if (current == after) {
				j++;

			} else if (j == (i + 1)) {
				rle.append(current);
				
				i++;
				j = i + 1;
				
			} else {
				rle.append(j - i);
				rle.append(current);

				i = j++;
				j = i + 1;
			}
			
			if (j >= seed.length()) {
				if ((j - i) > 1) {
					rle.append(j - i);					
				}
				rle.append(after);
				
				print(i, j, current, after, rle);				
				break;
			}

			print(i, j, current, after, rle);
		}
		
		return rle.toString();
	}

	/**
	 * Print 
	 * 
	 * @param i
	 * @param j
	 * @param current
	 * @param after
	 * @param rle
	 */
	private void print(int i, int j, char current, char after, StringBuffer rle) {
		System.out.print("i: " + i);
		System.out.print("\t");
		System.out.print("j: " + j);
		System.out.print("\t");
		System.out.print("current: " + current);
		System.out.print("\t");
		System.out.print("after: " + after);
		System.out.print("\t");
		System.out.println("rle: " + rle.toString());
	}
}


저작자 표시 비영리
신고

'Architecture for Software > Algorithm' 카테고리의 다른 글

최대 공약수 구하기  (0) 2009.11.09
RLE(Run-Length Encoding) 알고리즘  (2) 2009.11.09
Top Coder에 도전하세요!  (4) 2009.01.01
Algorithm 이란  (0) 2008.11.17
The 3n+1 Problem  (3) 2008.11.11
스택(Stack)  (0) 2008.10.08

WRITTEN BY
jangsunjin
전세계 사람들의 삶의 질을 높일 수 있는 소프트웨어를 만들어 함께 나누는 것이 꿈입니다. 이 세상 그 무엇보다 사람이 가장 소중합니다.

rle
받은 트랙백이 없고 , 댓글  2개가 달렸습니다.
  1. 이거... 약간 잘못되었다고 생각합니다... abbc는 ab2c로 나오겠지만 abbca는 a2b2c로 나와버립니다... 이렇게되면..인코딩하고 디코딩하면.. 데이타가 바껴버리졍...
secret

평소 소프트웨어(Software) 개발에 관심이 많거나, 특히 알고리듬(Algorithm)이나 소프트웨어 디자인(Software Design)에 관심이 많다면 Top Coder(http://www.topcoder.com)라는 사이트에서 자신의 능력을 다른 사람들과 함께 겨루어 보는 것도 참 좋은 일이라고 생각합니다.

 

 

전 세계에서 소프트웨어에 관심이 많은 사람들이 모여서 자신의 능력을 겨루고 있는데 재미있는 점은 우리나라의 순위입니다.

현재 우리나라의 순위는 8위인데 세계최고의 소프트웨어 강국인 미국은 7위로서 별 차이가 없으며, 세계 2위의 소프트웨어 강국인 인도의 경우 14위로 우리보다 많이 떨어집니다. 인도의 경우 1133명이나 참여하고 있지만, 우리나라의 경우 149명정도밖에 참여하지 않았는데도 좋은 성적을 거두고 있습니다.

하지만 얼마전에는 우리나라의 국가순위가 5위 정도까지 올라간 적도 있습니다. 이 순위에 큰 의미를 두기는 어려운듯 합니다만, 10위권안에 우리나라가 올라와 있다는 자체가 기분 좋네요 :-)

 

Top Coder는 소프트웨어 개발에 필요한 개발자의 능력을 온라인상에서 확인할 수 있는 좋은 사이트입니다.

특히 알고리듬 문제나 다른 문제등을 풀어서 좋은 성적을 거둔다면 자신의 능력을 검증함과 동시에 상금도 탈 수 있습니다.

 

저의 경우 소프트웨어 디자인(Software Design) 분야 중에서 컴포넌트에 많은 관심을 가지고 있습니다.

컴포넌트 문제는 대략 다음과 같습니다. 주로 Java를 사용하는 저에게 적합한듯 합니다.

 

일반적으로 C나 C++만을 중심적으로 다룰것 같지만, 거의 Java와 C++를 주로 사용하고 UML도 다루고 있습니다.

따라서 소프트웨어에 관심을 가지고 있다면 자신이 참여할 수 있는 분야는 매우 많습니다.

 

아울러 본 사이트에서 좋은 성적을 거둔다면 여러가지 해택이 따르는듯 합니다. 단순히 돈을 번다기 보다 국내외에 자신의 능력을 객관적으로 증명할 수 있는 좋은 이점이 있습니다.

만약 컴포넌트 디자인(Component Design) 분야에서 좋은 성적을 거둔다면, 많은 컴포넌트 관련된 회사에 취업이나 이직시 객관적으로 자신의 능력을 증명할 수 있습니다. 물론 얼마나 인정할지는 모르지만, 해외 유수의 기업에서 Top Coder를 후원하고 있으니 분명히 해외에서 더욱 많이 인정해 줄 듯 합니다.

 

아직 많은 문제를 풀어보지는 않았지만, 문제의 수준은 낮지는 않은 듯 합니다.  변별력을 가지기 위한 방안인듯하다.

 

세계적인 소프트웨어 개발자가 되기 위한 방안은 매우 많습니다. Top Coder에서 시작해보면 어떨까 싶습니다.

본 포스트를 보고 Top Coder에 가입하려면 http://www.topcoder.com/reg/ 에서 하면 됩니다.  가입시 jangsunjin을 추천해주면 감사하겠습니다. ;-)

신고

'Architecture for Software > Algorithm' 카테고리의 다른 글

최대 공약수 구하기  (0) 2009.11.09
RLE(Run-Length Encoding) 알고리즘  (2) 2009.11.09
Top Coder에 도전하세요!  (4) 2009.01.01
Algorithm 이란  (0) 2008.11.17
The 3n+1 Problem  (3) 2008.11.11
스택(Stack)  (0) 2008.10.08

WRITTEN BY
jangsunjin
전세계 사람들의 삶의 질을 높일 수 있는 소프트웨어를 만들어 함께 나누는 것이 꿈입니다. 이 세상 그 무엇보다 사람이 가장 소중합니다.

받은 트랙백이 없고 , 댓글  4개가 달렸습니다.
  1. 추천자 아이디 입력도 있나보군요 ㅎㅎ

    새해 복 많이 받으시구 올 한해 늘 행복하세요!!!
    • 네~ 추천점 부탁드려요 :)

      아직 저도 본격적으로 문제를 풀어보지 않았는데~ 워밍업점하고 함 풀어보려구요~ ㅎㅎㅎ

      잘 풀 수 있을지 모르겠습니당~

      지환님도~ 새해 복 많이 받으시구요~ 좋은일 가득하시길 기원드립니당~ ;-)
  2. 이 글 보고 한번 도전해보려고 합니다. :D 좋은 글 감사합니다.
secret
http://seo.seocompany.ca/google-algorithm-exposed/

출처: http://seo.seocompany.ca/google-algorithm-exposed/



Algorithm은 반드시 확신할 수 있어야 하며, Algorithm의 작동 방식을 배우는 가장 좋은 방법은 실제로 수행하여 보는 것이다.

Algorithm의 현대적인 의미는 조리법, 공정, 방법, 기법, 절차, 루틴 등과 상당히 비슷하다.
다만 Algorithm은 5가지 주요한 특징을 가진다.

1. 유한성(finiteness)
Algorithm은 여러 단계들을 수행한 후 유한한 횟수 후 반드시 종료되어야 한다. 이러한 유한성이 만족되어야 Algorithm으로 인정받을 수 있다.

2. 명확성(definiteness)
Algorithm의 각 단계는 반드시 명확하게 정의되어야 한다. 수행할 행동은 모든 경우에 대하여 모호함 없이 엄격하게 명시해야 한다.

Algorithm은 컴퓨터도 따라할 수 있을 정도로 명확하여야 한다.

출처: The Art of Computer Programming

3. 입력(input)
Algorithm은 0 또는 그 이상의 입력들을 가진다. 여기서 입력이라 함은 Algorithm이 시작되기 전에 Algorithm에 제공되거나, Algorithm 수행 중에 동적으로 주어진 수량들을 말한다.

4. 출력(output)
Algorithm은 1개 이상의 출력들을 가진다. 출력은 입력과 특정한 관계를 가지는 수량이다.

5. 효과성(effectiveness)
일반적으로 Algorithm은 효과적(effective)이어야 한다고 간주된다. 여기서 효과적이라는 말은, 이론적으로는 Algorithm의 모든 연산들이 종이와 연필을 이용하여 유한한 시간안에 정확하게 수행할 수 있을 정도로 충분히 단순해야 한다는 차원의 이야기이다.


현실적으로 우리가 원하는 것은 그냥 Algorithm이 아니라 다소 느슨한 미학적인 정의를 가진 좋은 Algorithm이다. 여기서 좋은 Algorithm에 대한 한가지 조건은 Algorithm의 수행시간이다. 이 수행시간은 각 단계의 수행 횟수로 표현할 수 있다. 또 다른 조건들로는 다양한 종류의 컴퓨터들에 대한 적응성이나 Algorithm의 단순성, 우아성 등을 들 수 있다.

계산적 방법을 컴퓨터 언어로 표현한 것을 프로그램이라고 한다.

출처: The Art of Computer Programming

신고

'Architecture for Software > Algorithm' 카테고리의 다른 글

최대 공약수 구하기  (0) 2009.11.09
RLE(Run-Length Encoding) 알고리즘  (2) 2009.11.09
Top Coder에 도전하세요!  (4) 2009.01.01
Algorithm 이란  (0) 2008.11.17
The 3n+1 Problem  (3) 2008.11.11
스택(Stack)  (0) 2008.10.08

WRITTEN BY
jangsunjin
전세계 사람들의 삶의 질을 높일 수 있는 소프트웨어를 만들어 함께 나누는 것이 꿈입니다. 이 세상 그 무엇보다 사람이 가장 소중합니다.

받은 트랙백이 없고 , 댓글이 없습니다.
secret
시간날때마다 Programming Challenges를 보고 있습니다. 그중에 한 문제를 올립니다.

문제는 http://acm.uva.es/p/v1/100.html를 보시면 정확하게 설명되어있습니다.

짧은 설명은 다음과 같습니다.
어떤 수열을 만들어내는 알고리즘이 있는데 n이 짝수이면 2로 나누고, n이 홀수이면 n * 3 + 1을 한다. n=1이 될때까지 같은 작업을 계속 반복한다.

아직 명확하게 증명되지 않았지만 모든 정수 n에 대하여 이 알고리즘을 적용시키면 결국에는 n=1이 된다고 추측된다. 이 가설은 적어도 1,000,000까지의 정수에 대해서는 참이다.

n이라는 값이 입력되었을 때 1이 나올때까지 만들어진 수의 개수(1 포함)를 n의 사이클 길이(cycle-length)라고 한다. i와 j라는 두개의 수가 주어졌을 때 i와 j사이의 모든 수(i, j 포함)에 대하여 최대 사이클 길이를 구하라.

우선 C++로 문제를 풀면 다음과 같다.

// 3nplus1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

unsigned long cycle(unsigned long num);

int main(int argc, char* argv[])
{

    long lbound, ubound, lbOrg, ubOrg, temp;
    long i, length, max_length;

    while(scanf("%ld %ld", &lbound, &ubound) == 2) {
        lbOrg = lbound;
        ubOrg = ubound;

        //printf("%ld %ld", lbound, ubound);
   
        if (lbound > ubound) {
            temp = lbound;
            lbound = ubound;
            ubound = temp;
        }

        max_length = 0;

        for (i = lbound; i <= ubound; i++) {
            //printf("Loof of %ld \n", i);

            length = cycle(i);

            if (length > max_length) {
                max_length = length;
            }

            printf("%ld ~ %ld = %ld\t(Max: %ld)\n", lbOrg, ubOrg, length, max_length);
        }

        printf("Max Cycle is %ld!\n\n", max_length);
    }

    return 0;
}

unsigned long cycle(unsigned long num){
    //printf("New cycle: %ld\n", num);

    unsigned long length, tmp_num;
    tmp_num = num;
    length = 1;

    while(tmp_num != 1) {
        if (tmp_num & 1) {
            tmp_num = tmp_num * 3 + 1;
            length ++;
        }

        while (!(tmp_num & 1)) {
            tmp_num = tmp_num / 2;
            length ++;
        }
    }

    return length;
}

흠.. 적당한지 모르겠다. 뭔가 더 줄일 수 있을것 같기도 하고..
알고리즘 문제는 하나 하나 풀때마다.. 더 어려워지는 것 같다.. 아직도 한발도 나아지지 못한것 같다..

더 좋은 알고리즘을 알고 계신분은 많은 조언부탁드립니다.

신고

'Architecture for Software > Algorithm' 카테고리의 다른 글

최대 공약수 구하기  (0) 2009.11.09
RLE(Run-Length Encoding) 알고리즘  (2) 2009.11.09
Top Coder에 도전하세요!  (4) 2009.01.01
Algorithm 이란  (0) 2008.11.17
The 3n+1 Problem  (3) 2008.11.11
스택(Stack)  (0) 2008.10.08

WRITTEN BY
jangsunjin
전세계 사람들의 삶의 질을 높일 수 있는 소프트웨어를 만들어 함께 나누는 것이 꿈입니다. 이 세상 그 무엇보다 사람이 가장 소중합니다.

받은 트랙백이 없고 , 댓글  3개가 달렸습니다.
  1. dynamic programming으로 풀지 않는다는 가정하에 cycle length를 캐싱하면 좀 더 퍼포먼스를 높일 수 있습니다.
    • 좋은 조언 감사합니당~

      한번 머리를 싸매봐야겠습니당~ :-)

      글구~ 알고리듬에 대한 좋은 블로그를 만드시려는 것 같은데~ 화이팅입니당~ ;-)
  2. 캐싱하면 이런 문제의 경우는 시간이 엄청 길어지는데...
secret
최근 간간히 Programming Challenges를 보고 있습니다. 너무도 어려운 문제들이 많지만 나름 재미를 붙여가고 있습니다. 책의 내용 중 일부를 발췌하였습니다. 참고하세요.

스택(Stack)과 큐(Queue)는 각 항목을 내용과는 무관하게 삽입된 순서에 따라 꺼내도록 설계된 컨테이너이다.
스택은 후입선출(LIFO, last-in first-out) 규칙을 따르는 구조로서 마지막에 들어간 항목이 가장 먼저 나오는 자료구조이다.

스택의 연산에는 다음과 같은 것이 있다.
  • Push(x, s) - x라는 항목을 s라는 스택 맨 위에 삽입
  • Pop(s) - 스택 s의 맨 위에 있는 항목을 리턴하고 삭제
  • Initialize(s) - 비어있는 스택을 생성
  • Full(s), Empty(s) - 스택 s에 대하여 Push 및 Pop 연산을 적용할 수 있는지 확인

표준 스택과 큐에는 원소를 검색하는 연산이 정의되어 있지 않다는 점을 잘 기억해두세요.

상기 연산을 알아두면 자세한 구현 방법은 모르더라도 쓸 수 있는, 즉 재사용이 쉬운 스택 모듈을 만들 수 잇다.
가장 쉬운 구현법은 배열과 스택 맨 위를 나타내기 위한 인덱스 변ㅅ를 사용하는 방법이다. 또 다른 방법으로 Linked-List가 있는데 이를 이용하면 배열의 크기 제한이 걸리는 문제가 없다는 장점이 있다.

스택은 접시를 쌓아 놓은 것에 비유할 수 있다.

사용자 삽입 이미지

접시를 새로 씻고나면 그 접시는 스택 맨위에 추가된다. 즉 Push(x, s) 연산을 수행한 것이다.
그리고 접시를 사용해야 하는 사람은 맨 위에 있는 새 접시를 집어든다. 즉 Pop(s) 연산을 수행한 것이다.

접시를 올려놓거나 맨위에 있는 접시를 꺼내는 작업을 할 때는 다음에 나온느 접시에 대하여 신경 쓸 필요가 없기 때문에 이런 스택이라는 자료구조를 사용하는 것이 적합하다.

스택은 구현하기가 아주 간단한 컨테이너이기 때문에 순서가 별로 중요하지 않는 경우에는 스택을 활용하면 좋다.

중첩된 구조를 처리할 때는 스택 순서가 중요하다.
중첩된 구조의 예를 들자면 괄호로 싸여있는 공식, 재귀호출, 그래프의 깊이 우선 순회 등이 있다.
신고

'Architecture for Software > Algorithm' 카테고리의 다른 글

최대 공약수 구하기  (0) 2009.11.09
RLE(Run-Length Encoding) 알고리즘  (2) 2009.11.09
Top Coder에 도전하세요!  (4) 2009.01.01
Algorithm 이란  (0) 2008.11.17
The 3n+1 Problem  (3) 2008.11.11
스택(Stack)  (0) 2008.10.08

WRITTEN BY
jangsunjin
전세계 사람들의 삶의 질을 높일 수 있는 소프트웨어를 만들어 함께 나누는 것이 꿈입니다. 이 세상 그 무엇보다 사람이 가장 소중합니다.

받은 트랙백이 없고 , 댓글이 없습니다.
secret