본문 바로가기

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..
RLE(Run-Length Encoding) 알고리즘 나름 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 P..
Top Coder에 도전하세요! 평소 소프트웨어(Software) 개발에 관심이 많거나, 특히 알고리듬(Algorithm)이나 소프트웨어 디자인(Software Design)에 관심이 많다면 Top Coder(http://www.topcoder.com)라는 사이트에서 자신의 능력을 다른 사람들과 함께 겨루어 보는 것도 참 좋은 일이라고 생각합니다. 전 세계에서 소프트웨어에 관심이 많은 사람들이 모여서 자신의 능력을 겨루고 있는데 재미있는 점은 우리나라의 순위입니다. 현재 우리나라의 순위는 8위인데 세계최고의 소프트웨어 강국인 미국은 7위로서 별 차이가 없으며, 세계 2위의 소프트웨어 강국인 인도의 경우 14위로 우리보다 많이 떨어집니다. 인도의 경우 1133명이나 참여하고 있지만, 우리나라의 경우 149명정도밖에 참여하지 않았는데도 좋..
Algorithm 이란 Algorithm은 반드시 확신할 수 있어야 하며, Algorithm의 작동 방식을 배우는 가장 좋은 방법은 실제로 수행하여 보는 것이다. Algorithm의 현대적인 의미는 조리법, 공정, 방법, 기법, 절차, 루틴 등과 상당히 비슷하다. 다만 Algorithm은 5가지 주요한 특징을 가진다. 1. 유한성(finiteness) Algorithm은 여러 단계들을 수행한 후 유한한 횟수 후 반드시 종료되어야 한다. 이러한 유한성이 만족되어야 Algorithm으로 인정받을 수 있다. 2. 명확성(definiteness) Algorithm의 각 단계는 반드시 명확하게 정의되어야 한다. 수행할 행동은 모든 경우에 대하여 모호함 없이 엄격하게 명시해야 한다. Algorithm은 컴퓨터도 따라할 수 있을 정도로 명..
The 3n+1 Problem 시간날때마다 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라는..
스택(Stack) 최근 간간히 Programming Challenges를 보고 있습니다. 너무도 어려운 문제들이 많지만 나름 재미를 붙여가고 있습니다. 책의 내용 중 일부를 발췌하였습니다. 참고하세요. 스택(Stack)과 큐(Queue)는 각 항목을 내용과는 무관하게 삽입된 순서에 따라 꺼내도록 설계된 컨테이너이다. 스택은 후입선출(LIFO, last-in first-out) 규칙을 따르는 구조로서 마지막에 들어간 항목이 가장 먼저 나오는 자료구조이다. 스택의 연산에는 다음과 같은 것이 있다. Push(x, s) - x라는 항목을 s라는 스택 맨 위에 삽입Pop(s) - 스택 s의 맨 위에 있는 항목을 리턴하고 삭제Initialize(s) - 비어있는 스택을 생성Full(s), Empty(s) - 스택 s에 대하여 Pus..