> mergesort [1,5,3,7,6]
[1,3,5,6,7]

하스켈은 대표적인 함수형 언어로, 변수가 존재하지 않는 신기한 언어이다. 변수가 없으므로 side-effect가 없어 디버깅에 쏟을 시간을 절약할 수 있다.

.. 라지만 이게 내 첫 하스켈 소스이다.

more..

class Disjointset
  def initialize(n)
    @set = (0..n).to_a    
    @cnt = n;
  end
 
  def getroot(i)
    i=@set[i] while i!=@set[i]
    return i
  end  
 
  def same?(i,j)
    getroot(i)==getroot(j)
  end
 
  def union(i,j)      
    @cnt-=1
    b = getroot(j)
    i, @set[i]=@set[i], b while @set[i]!=b
    j, @set[j]=@set[j], b while @set[j]!=b
  end
  attr_reader :cnt
end

어떤 두 원소가 같은 그룹에 속해 있는지 알아낼 수 있고, 빠른 시간에 그룹을 결합할 수 있는 자료구조인 서로소 집합입니다. Kruskal 등의 알고리즘을 구현할 때 많이 쓰입니다.

more..

 

$Inf=999999999999999
class Pair
  include Comparable
  def initialize(first=0, second=0)
    @first, @second = first, second
  end
  def to_s()
    "(%d, %d)" % [first, second]
  end
  attr_reader :first, :second
end

class Network
  def initialize()
    @net=Hash.new(nil)
  end
  def plusedge(s,e,value)
    @net[s]=@net[s] || Hash.new(nil)
    @net[s][e]=value
  end
  def add(s, e, value)
    plusedge(s,e,value)
    plusedge(e,s,value)
  end
  attr_accessor:net
  def dup
    Marshal::load(Marshal.dump(self))
  end
end
class Maxflow
  def augment(pos, ed, m=$Inf)        
    return false if (@check & (1<<pos))!=0    
    @check ^= (1<<pos)
    if pos==ed :
      @m=m;
      return true
    else
      @G.net[pos].each do |to, val|              
        next if(val==0)        
        @path[to]=pos
        return true if(augment(to, ed, m>val ? val : m))    
      end
    end    
    @check ^= (1<<pos)
    false
  end

  def fordfulkerson(ed, t)
    ret=0      
    @G=t.dup
    while(augment(1,ed)) do      
      @check=0
      pos=ed
      ret+=@m
      while(pos!=1) do
        prev=@path[pos].to_i
        @G.net[prev][pos]-=@m
        @G.net[pos][prev]+=@m
        pos=prev
      end
    end    
    ret
  end
  def initialize()
      @check=0
      @path=[]
  end
end

def input
  ret=Network.new
  inf=File.open("worldwar.in","r")
  inf.readline=~/(\d+)\s(\d+)/
  $n, $m = $1.to_i, $2.to_i

  $m.times{ inf.readline=~/(\d+)\s+(\d+)\s+(\d+)/
    ret.add($1.to_i, $2.to_i, $3.to_i)
  }
  ret
end

#실행 부분

graph=input
algo=Maxflow.new
ans=$Inf
2.upto($n) { |i| t=algo.fordfulkerson(i,graph);
  ans=t if ans > t
}

File.open("worldwar.out","w").puts ans

전혀 루비스럽지 않은 코드 ... orz

많이 느립니다. 다시 구현할 생각입니다.

현재 상용 압축 프로그램에 가장 많이 쓰이는 알고리즘들은, 바로 이 Lempel-Ziv 알고리즘의 변형들이다. Lempel과 Ziv는 이 알고리즘을 처음 고안한 사람들의 이름이다. 이들의 머릿글자를 따서 LZ 알고리즘이라고도 부르며, 만든 연도, 또는 사용한 기법에 따라 LZ77, LZ78, LZW, LZSS 등으로 부른다.

압축의 철학은, 반복하는 데이터는 축약해서 표현할 수 있다는 것이다. 예를 들어서, RLE의 경우는 aaaa -> a4 와 같이 반복되는 '문자'를 축약한다. 반면, LZ는 반복되는 '패턴'을 축약한다.

다음의 문자열이 입력으로 들어오면, RLE는 전혀 압축이 되지 않는다.

abababcabc

그러나 기본적인 LZ방법에서는, 다음과 같은 방식으로 표현된다.

ab(2,2)(4,2)c(3,3)

(n,m)은 n만큼 앞에서부터 m개의 문자를 반복하라는 의미이다. 그러나, 최적의 압축률을 보이는 대입을 찾기란 쉬운 일이 아니다. 이 패턴을 찾는 방법에 따라서 LZ 알고리즘의 압축률과 소요 시간이 좌우된다. 이를 위해서 suffix tree 등을 이용하는데, 이게 은근히 난제다. 구현이 꽤 까다롭기 때문이다.

RLE

압축 알고리즘을 배우고자 할 때, 아마도 가장 처음 접하게 되는 알고리즘이 아닐까 생각한다. 기본적인 개념은 이렇다. 여러 개의 중복된 문자를 다음처럼 치환하는 것이다.

원문 : aaabbccccddddd
압축문 : a3bbc4d5

보다시피, 여러 개의 문자가 반복되면, 그 문자가 몇번이나 반복되었는지만 저장하는 것이다. 방법은 간단하지만, 압축률은 그다지 좋지 않다. 한 문자가 계속 반복되는 데이터가 얼마나 있겠는가?

의문을 가진 독자도 있을 것 같다. 숫자가 데이터로 들어오면 어찌할 것인가? 그래서 데이터와 반복  회수를 구분할 방도가 필요하다. 이는 LZ등의 알고리즘에서도 마찬가지인데, 주로 탈출 문자를 사용한다. C/C++의 '\'을 생각하면 이해가 갈 것이다.

어떤 두 정수의 합이 주어진 숫자가 되는 경우가 있는가? - art. oriented님의 블로그에서 트랙백


문제를 간단히 설명하자면, 어떤 수열이 있다.
이 수열 내에서 어떤 두 정수를 더하여, 임의의 정수 M을 만들 수 있는가? 하는 것이다.
수열은 오름차순으로 정렬되어 있다.

다음과 같은 O(N^2) 알고리즘은 쉽게 찾을 수 있을 것이다.

그러나, 이 방법은 N이 조금만 커져도 너무 오랜 시간이 걸린다. 개선해야 한다.
두 번째의 loop를 다음과 같이 고쳐보자.

여전히 알고리즘은 O(N^2)의 복잡도를 보이지만, 약간 개선된 것을 알 수 있다.
하나의 숫자를 A[first]로 정하면, 찾아야 하는 다른 숫자는 M-A[first]이다.

수열은 오름차순 정렬 상태이기 때문에, last가 감소할수록 A[last]의 값은 감소한다.
자, 마찬가지 이유로, first가 증가하면 A[first]도 증가한다.

따라서, M-A[first]는 감소한다.

찾고자 하는 값인 M-A[first]가 감소했으므로, 그에 대응하는 짝인 A[pair]의 위치도 감소할 것이다. 이를 이용해서 간단한 O(N) 알고리즘을 만들 수 있다.