천상낙원

Brick Wall Patterns

ACM 퀴즈
원문 : http://acm.uva.es/p/v9/900.html

높이가 폭의 2배인 벽돌을 이용해서 담을 쌓고자 한다. 담의 높이는 벽돌의 높이와 동일하고, 길이는 원하는 길이로 해서 담을 쌓는다.  다음 그림을  보면..
사용자 삽입 이미지
- 담의 길이를 기본 1 (벽돌 한개의 폭)으로 하는 방법: 벽돌 하나를 세워두는 한가지 패턴
- 담의 길이를 2으로 하는 방법: 벽돌 두개를 세워두는 방법과 눞혀두는 두가지 패턴
- 담의 길이를 3으로 하는 방법은 3가지 패턴이 있다.

문제
담의 길이가 주어졌을 때, 몇개의 패턴으로 담을 쌓을 수 있는지를 구하라.입력한 줄에 한개씩 담의 길이를 의미하는 양의 수가 입력된다. 담의 길이는 퇴대 50이며 0을 입력하면 입력이 종료된다.

입력 예시
1
2
3
0

출력 예시
1
2
3

'ACM 퀴즈' 카테고리의 다른 글

Bee  (1) 2007.03.24
Airline Hub  (0) 2007.03.24
ACM/ICPC 2004 서울대회 출제 문제  (0) 2006.09.16

Bee

ACM 퀴즈

원문 : http://acm.uva.es/p/v110/11000.html

아프리카에 매우 특이한 종류의 벌이 있다. 매년마다, 암컷 벌은 같은 종의 수컷 벌을 한 마리 출산한다. 반면에 수컷 벌은 한 마리의 수컷 벌과 암컷 벌을 출산한다. 출산 후, 벌은 죽는다

과학자들은 새로운 마법 암컷 벌을 발견했다. 그 마법 암컷 벌은 죽지 않지만, 암컷 벌을 한 마리씩 출산한다. 과학자들은 N년 후에 몇 마리의 벌이 있을지 알고자 한다. N년 후에 수컷 벌의 총 수를 알 수 있는 프로그램을 작성하라.

입력
N (>=0). N=-1인 경우에 입력이 종료된다.

출력
N년이 지난 후, 수컷 벌의 수와 벌의 총 수를 출력하라. (두수는 2^32를 넘지 않는다.)

입력 예
1
3
-1

출력 예
1 2
4 7

참고사항
0년 후, 마법 암컷 벌 = 1
1년 후, 마법 암컷 벌 + 수컷 벌 = 2
2년 후, 마법 암컷 벌 + 수컷 벌 + (수컷 벌 + 암컷 벌) = 마 1 + 수 2 + 암 1 = 4
3년 후, 마법 암컷 벌 + 수컷 벌 + 2 * (수컷 벌 + 암컷 벌) + 수컷 벌 = 마 1 + 수 4 + 암 2 = 7
4년 후, 마법 암컷 벌 + 수컷 벌 + 4 * (수컷 벌 + 암컷 벌) + 2 * 수컷 벌 = 마 1 + 수 7 + 암 4 = 12
5년 후, 마법 암컷 벌 + 수컷 벌 + 7 * (수컷 벌 + 암컷 벌) + 4 * 수컷 벌 = 마 1 + 수 12 + 암 7 = 20
....

'ACM 퀴즈' 카테고리의 다른 글

Brick Wall Patterns  (1) 2008.01.28
Airline Hub  (0) 2007.03.24
ACM/ICPC 2004 서울대회 출제 문제  (0) 2006.09.16

Airline Hub

ACM 퀴즈
원문 : http://acm.uva.es/p/v103/10316.html

World Wide Flyer (WWF)는 세계의 여러 공항에 착륙 권한을 가지고 있다. 그들은 세계의 어떠한 다른 공항과의 허브간의 직접 비행거리들의 최대값이 최소가 되는 중앙 허브를 설치하고자 한다.

입력
입력 파일은 여러 입력 세트로 되어있다. 각 세트는 첫 줄은 입력될 공항의 개수(n <= 1000)를 포함한다. 그 뒤에 공항의 경도(-90~+90), 위도(-180~+180)가 n개 입력된다. 입력값의 소수점은 두자리를 넘지 않는다. 입력은 파일의 끝으로 종료된다.

출력
각 입력 세트에 해당하는 중앙 허브의 위치를 한 줄에 출력한다. 2개 이상 존재할 경우에는 나중에 입력된 값을 출력한다. 위치는 소수점 둘째자리까지 출력한다.

입력 예
3
3.2 -15.0
20.1 -175
-30.2 10
3
3.2 -15.0
20.1 -175
-30.2 10

출력 예
3.20 -15.00
3.20 -15.00


'ACM 퀴즈' 카테고리의 다른 글

Bee  (1) 2007.03.24
ACM/ICPC 2004 서울대회 출제 문제  (0) 2006.09.16
ACM/ICPC 2005 서울대회 출제 문제  (0) 2006.09.14

힘내라~! 전주 케이씨씨 이지스~!!

일상이야기
흐흑.. 팀 최다연패가 되어버렸네요. 그토록 응원했건만 오늘도 힘없이 무너져버렸네요. 저는 농구에 대해서 잘 알지는 못합니다. 농구했던지도 한 5년은 지난거 같습니다만... -ㅅ-;; 작년부터 케이씨씨 농구 경기 진행요원으로 아르바이트를 하면서 농구에 재미를 붙이기 시작했고, 지금은 아르바이트도 관둔 상황이지만 그 당시에 코트 바로 옆에서 보던 재미를 잊지못하고 있네요.

아르바이트하던 때까지만해도 점수는 뒤지고 있었도 경기에 집중하고 재미있게 볼수있었습니다. 아쉬운 경기는 있었지만 힘빠지는 그런 경기는 없었거든요. 하지만 요즘 케이씨씨 경기는 마음 편히 보고 있기가 힘드네요. 허재감독님을 비롯 선수들의 힘빠져있는 모습을 보고 있으면 정말 기운빠지게 만들어 주더군요.

모두들 이번 시즌 꼴지는 케이씨씨라고들 하지만 케이씨씨 팬들은 포기하고 있지 않습니다. 케이씨씨 선수들도 이런 팬들의 마음을 알고 다시 힘내서 열심히 경기하는 모습을 보여줬으면 합니다.


사용자 삽입 이미지

짤방은.. 아르바이트 시절 모습입니다. 다들 사진을 보면 손준영선수나 표명일선수를 보지만 저는 진행요원(아르바이트)을 먼저 봅니다. 후훗.. 단체사진(?)엔 자기 모습 먼저 찾는게 인지상정 아니겠습니까?

영상처리를 이용한 악보 인식

DoItMyself
개요
음악 분야에서도 전산화의 필요해짐에 따라 음악(악보) 데이터베이스의 구축이 필요해졌다. 기존의 키보드, 마우스를 이용한 수동 입력 방식은 많은 시간이 소요되며 오입력되는 경우도 많이 발생했다. 인쇄된 악보를 스캐너 등을 통해 입력 받고 입력된 이미지를 이용하여 악보의 정보를 인식하고자 한다. 영상처리와 패턴인식을 통하여 원하는 정보를 인식함으로 입력에 필요한 노력을 최소화하고 입력을 자동화할 수 있다. 또한 전산화된 악보정보를 목적에 맞는 정보로 변환하여 다양한 분야에 응용이 가능하다.

개발 환경
운영체제 : Windows XP
사용언어 : C++ (MS Visual Studio .Net)
라이브러리 : OpenCV

악보 인식기 기본 구조
사용자 삽입 이미지

악보 인식기 기본 구조



악보 인식 과정
1. 악보 이미지 전처리 (기울기 보정 및 노이즈 제거)
2. 오선 인식 및 제거
3. 각 인식 영역 설정
4. 기본 영역 (음자리표, 조표, 박자) 인식
5. 음표 영역 인식
    a. 음표 / 기호 분류
    b. (각 인식기를 통한) 음표 및 기호 인식
6. 가사 인식
    a. 한 글자별 분리
    b. 각 글자 인식
7. 인식된 악보 표시
8. 인식된 악보 연주

'DoItMyself' 카테고리의 다른 글

GML을 이용한 지도 서비스  (3) 2006.08.16
모의 수강신청  (0) 2006.02.14
배차 관리 시스템 (Marshalling of Cars)  (0) 2006.01.23

ACM/ICPC 2006 Asia Regional Contest - Seoul 참가 후기

일상이야기
지난 2006년 11월 3일 백범기념관에서 'ACM International Collegiate Programming Contest / 2006 Asia Regional Contest - Seoul'가 열렸습니다. 저는 예선 탈락으로 대회에 출전하지 못한 까닭으로 진출팀이 아닌 스태프로서 대회에 참여하였습니다. 스태프로서의 참가가 어쩌면 출전팀으로서보다 더 많은 경험을 할 수 있었지않나 싶습니다.



'제6회 대학생 프로그래밍 경시대회'와 '제31회 국제 대학생프로그래밍경시대회' 아시아 지역 대표 선발을 겸하는 대회로 국내 58팀과 아시아 지역의 5팀, 총 63팀이 출전하여 우열을 가렸습니다. 10시부터 15시까지 5시간동안 A부터 J까지 모두 10개의 문제를 풀게되는데요. 서울대학교의 'Do not touch anything'팀이 8문제를 풀어 대상을 받았고, '제31회 국제 대학생프로그래밍경시대회'에도 참여하게 되었습니다. 작년대회의 경우, 중국팀이 출전권을 얻었던 것으로 알고 있는데 이번 대회에서도 해외팀이 출전권을 앚아갈까 많이 걱정되었습니다. 마지막까지 해외팀인 '베이징대학'의 '중산대학'팀, 'Zhongshan Univ.'의 'ZSU_Everest'팀과 치열한 접전을 벌여었는데 다행히도 1위를 지켜냈네요.
(순위 및 결과 확인 http://acm.kaist.ac.kr/forum/viewtopic.php?t=572)

문제는 모두 영문으로 주어지고, 문제에 해당하는 프로그램 소스를 작성하여 PC^2라는 프로그램을 통하여 소스를 검증받게 됩니다. PC^2에서 소스를 확인하여 Sovled, Wrong answer, Time limited.. 등의 결과를 보여줍니다. 이때 올바른 답안이 아닐 경우, 그 문제에 패널티가 주어집니다. 그리고 문제를 해결하는데 소요된 시간 또한 패널티가 됩니다. 다수의 팀이 동일한 수의 문제를 풀었을지라도 이러한 패널티 제도를 통하여 순위를 가리게 됩니다.

각 팀들은 소스나 기타 문서 등 대회 진행시 원하는 문서를 인쇄하여 참고할 수 있는데요. 이번 대회에선 모든 63팀이 1~2대의 프린터를 사용합니다. 이를 위해 (또 다른 이유가 있는지도 모르겠지만) 워터마크를 이용하는데요. 인쇄면에 옅은 배경으로 팀명이 찍혀나오도록 워터마크를 설정해두어 어떠한 팀이 출력한 문서인지 확인하고, 스태프는 인쇄 문서를 해당 팀으로 배달해줍니다.

문제를 해결할때마다 해당 팀에 풍선을 달아주게 되는데요. 각 문제에 따라서 해당하는 풍선의 색상이 있습니다. 문제 A는 빨간색, 문제 B는 하늘색.. 뭐 이런식으로 정해져있습니다. 작년대회까지는 문제 - 풍선색상이 공개되지 않았지만 이번 대회에는 공개가 되었습니다. 대회장 뒤쪽 문옆에 부착되어 있었는데 많은 팀들이 확인을 위해 다녀가더군요. (제가 알고 있는 바로는) 문제 난이도와 관계없이 동일한 배점을 가지고 있어 우선 많은 문제를 푸는 것이 중요하기에, (많이 달려있는 풍선의 색상을 파악해) 좀 더 쉬운 문제를 찾기위한 꼼수가 아니였나 싶습니다. 팀별 문제 해결 현황이 서버실에서부터 대회장의 스태프에게 온라인으로 통보되어 문제를 해결한 팀에게 문제에 해당하는 색의 풍선을 달아주게 됩니다.(작년의 경우엔, 스태프가 직접 서버실에 가서 확인했다고 하더군요.)



이번 대회 역시 인터넷 예선 대회와 마찬가지로 온라인상에 실시간으로 팀별로 해결한 문제 수와 패널티가 공개되었는데요. 패널티까지 알 수 있어, 현재까지의 순위를 바로 확인할 수 있었습니다. 대회장의 뜨거운 열기때문인지(반팔티를 입고도 땀이 날 지경;;) 코치분들이 많이 안보이셨는데요. 아마도 문제 풀이 현황을 보시면서 F5키를 연타하고 계시지 않았을까 싶더군요.

* http://acm.kaist.ac.kr/2006/photo/Photo1.html 에서 대회 사진을 확인하실 수 있습니다.

ACM/ICPC 2004 서울대회 출제 문제

ACM 퀴즈

'ACM 퀴즈' 카테고리의 다른 글

Airline Hub  (0) 2007.03.24
ACM/ICPC 2005 서울대회 출제 문제  (0) 2006.09.14
개와 땅다람쥐 (Dog and Gopher)  (0) 2006.04.14

ACM/ICPC 2005 서울대회 출제 문제

ACM 퀴즈

'ACM 퀴즈' 카테고리의 다른 글

ACM/ICPC 2004 서울대회 출제 문제  (0) 2006.09.16
개와 땅다람쥐 (Dog and Gopher)  (0) 2006.04.14
체스판 위의 개미 (Ant on a Chessboard)  (0) 2006.03.26