호주식 투표법(Australian Voting)

Programming/Algorithm 2010. 8. 27. 22:02
호주식 투표 제도에서는 투표권자가 모든 후보에 대해 선호도 순으로 순위를 매긴다.
처음에는 1순위로 선택한것만 집계, 한 후보가 50 % 이상 득표시 바로 선출된다. 하지만 50% 이상 득표한 후보가 없으면 가장 적은표를 받은 후보(둘 이상 될 수도)가 우선 탈락된다. 그리고 이렇게 탈락된 후보를 1순위로 찍었던 표를 다시 집계, 아직 탈락되지 않은 후보가운데 가장 높은 선호도를 얻는후보가 그 표를 얻는다. 이런 식으로 가장 약한 후보들을 탈락시키면서 다음 순위의 탈락하지 않은 후보에게 표를 주는 과정을 50% 이상을 얻는 후보가 나오거나 탈락되지 않은 모든 후보가 동률이 될 때까지 반복한다.

입력

입력 케이스의 개수를 나타내는 양의 정수 한 개가 들어있는 행으로 시작되며 그 줄에는 그 숫자밖에 입력되지 않는다.
그 뒤에는 빈줄이 하나 들어가고 서로 다른 입력 케이스 사이에는 두개의 빈줄이 입력된다.
각 케이스의 첫번째 줄에는 후보 수를 나타내는 20 이하의 정수 n이 입력된다. 그 밑으로 n개의 줄에 걸쳐서 후보의 이름이 순서대로 입력되며 각 후보의 이름은 80글자 이하로, 출력가능한 문자로 구성된다.
그 뒤에는 최대 1,000줄이 입력될 수 있는데, 각 줄에는 투표 내역이 입력된다. 각 투표 내역에는 어떤 순서로 1부터 n까지의 수가 입력된다. 첫번째 숫자는 1순위로 찍은 후보의 번호, 두번째 숫자는 2순위로 찍은 후보의 번호, 이런식으로 숫자가 입력된다.

출력

각 테스트 케이스에 대해 당선된 후보의 이름 한줄, 또는 동률을 이룬 후보들의 이름이 들어있는 여러 줄을 출력한다.
두 개 이상의 테스트 케이스가 있는 경우 각 결과는 한 개의 빈 줄로 구분한다


입력 예                                            출력 예

1                                                  John Doe
3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2

주의해야 할 점
말이 조금 어렵게 나와있다. 입력케이스는 현재 개표(?)중인 선거를 나타낸다는 것과 1,000줄 입력중에 중지하는 키워드는 "두개의 빈줄"임을 확인하자. 두 개의 빈줄은 개인적으로 아주 조잡하게.. gets함수를 이용하였다.
또한 같이 푼 동료가 대단히 헷갈려한 부분인데, 위의 입력예에서 첫번째 사람이 가장 선호하는 후보자가 1번 후보자(john)이며, 그다음이 2번째, 3번째 임을 기억하자. john이 1점을 받고 jane이 2점을 받는다는 식이 아님을 기억하자!





 


'Programming > Algorithm' 카테고리의 다른 글

ACM-ICPC 2009년도 기출 _ Candy War  (0) 2010.10.01
암호 깨기 (Crypt Kicker)  (0) 2010.09.30
동맹 휴업 (Hartal)  (0) 2010.09.03
포커 패(Poker Hands)  (0) 2010.09.01
유쾌한 점퍼(Jolly Jumpers)  (0) 2010.08.31

Matlab을 이용한 영상처리 - 6. 필터링이란?

Programming/Image Processing 2010. 8. 27. 14:28

Filter는 그 단어의 의미대로 특정 픽셀을 거르는 역할을 한다.

마스크에 해당하는 배열을 넘겨주면 그것을 현재 픽셀과 그 주변 픽셀과의 계산을 통해 적절한 결과를 낸다.

그 계산 과정을 c 언어로 표현하자면, 

for(int i = 1 ; i < N; i ++ ){
  for( int j = 0; j < M; j++){
    for(int offset_I = -3; offset_I < 3 ;  offset_I ++){
       for(int offset_j = -3; offset_j < 3; offset_j++){
           product =  마스크배열[offset_i][offset_j] * 주변픽셀[offset_i][offset_j];
           sum += product;
       }    
    }//주변 픽셀 검색
     image[i][j] = sum;
  }
}//전체 이미지 픽셀
와 같은 형태다. 

주어지는 마스크 배열에 따라 이 결과는 천차만별인데 , 이를 이용해 이미지에 다양한 변화를 줄 수가 있다.

이번 포스팅에서는 평균필터링과 고주파 필터링에 대해 살펴본다.

평균필터의 형태는 다음과 같다. ( 3 X 3 일때 )

1/9 * [ 1 1 1 ; 1 1 1 ; 1 1 1] 

위의 알고리즘과 연계해서 생각해보면, 현재 수정하고 있는 픽셀의 값은 주변 픽셀들과 자신을 평균내어 결정 된다는 것이다.

평균을 낸다면 이미지는 ? 경계선뿐만아니라 이미지가 전체적으로 흐려지게 될것이다. 
(모든 픽셀이 주변픽셀들의 값과 비슷해진다는 얘기니까.)

이해를 돕기위해 간단한 예를 들어보자.

255    0   255
250    0   250
150   10  150

와 같은 3 X 3 의 원본 이미지가 있다. 
원본이미지는 중앙에 선명한 검은 선이 있다.
현재 정중앙의 픽셀을 검색하고 있다고 할 때 이 이미지에 평균 필터링을 적용하면,

255 * 1/9 + 255 * 1/9 + 250 * 1/9 + 250 * 1/9 + 150 * 1/9 + 150 * 1/9 = 146.6666...

이미지는 

255  0   255
250 146 250
150  10 150

이 된다. 한 픽셀에만 적용해보았지만 중앙의 경계선이 뭉개졌다.
이와 같은 과정이 전체 이미지에 적용된다면 전체 이미지가 흐려질 것이라고 이해할 수 있다.

Matlab에서는 필터를 만들때 fspecial이라는 함수를, 
필터를 적용할때 filter2(filter,image, shape)의 함수를 이용한다.

직접 저렇게 필터배열을 넘겨주어도 되지만 자주 이용되는 필터는 Matlab에 이미 배열로 저장되어 있다.

평균필터링은 'average'로 호출할수있으며, fspecial 첫번째 인자로 지정가능하며 두번째 인자로 마스크의 크기를 지정할 수 있다.

평균필터링의 실행 결과를 보자.



확연한 차이를 보이기위해 마스크의 크기를 11 X 11로 처리했다.
원영상과 비교해 확실히 흐리게 나타났다.