본문 바로가기

집546

ACM 10196, Check the Check http://acm.uva.es/p/v101/10196.html 역시 별로 어려운 문제는 아니다. 그러나 좌표계에 음수가 있다고 생각하고 알고리즘을 짜는 바람에 디버그하기 아주 힘들었다... 어이없는 하루였다. 비트플래그를 사용하는 STL 컨테이너인 bitset 사용에 익숙해졌다는데 그나마 의의를 찾을 수 있겠다. 풀이는 간단하다. king 주변의 근접 2타일까지는 점프할 수 있는 knight와 특정 위치에서만 출현하는 pawn을 체크하기 위해 bitset을 사용하여 플래그를 비교하였다. 2006. 1. 5.
ACM 10041, Vito's family http://acm.uva.es/p/v100/10041.html 이번 문제는 참으로 황당하지 않다 아니할 수 없다. 문 제에서 입력되는 번지에 집이 하나만 있다고 생각하여, set 자료 구조에 입력 값을 집어 넣는 바람에 해결 방법 자체가 틀렸기 때문이다. 다 푼 후에는 시간 초과까지 걸렸다. 여기에 특히 많은 시간이 걸렸다. 쉬운 문제라 생각하여 가볍게 풀어 보려 했는데 덕분에 많은 시간을 날려버렸다... 예 를 들어 1 1 8 이란 입력이 들어왔다고 하자. 이는 1번 거리에 친척이 2명 산다는 것을 의미한다. 따라서 비토가 1번 거리에 산다고 가정했을때, 친척 간의 이동 거리는 abs(1-1)+abs(1-1)+abs(1-8)=7이 된다. 또 다른 예로 비토가 4번 거리에 산다고 가정하자. 이때는 ab.. 2006. 1. 1.
ACM 10033, Interpreter http://acm.uva.es/p/v100/10033.html 간단한 문제. 그냥 문제대로 코딩하면 된다. 그런데... 알고리즘 트레이닝 북에 오타가 있어서 엄청나게 헤매서 억울할 뿐이다. 책 에서는 입력을 두줄 간격으로 받는다고 써있는데, 원래는 한 줄이다... 두줄 간격으로 처리해서 계속해서 Time Limit Exceed를 받았고, 선형 알고리즘에 괜한 의심을 품고 쓸데없이 inline을 쓰거나 변수의 초기화를 아끼는 것 같은 괜한 짓에 시간 허비... 다음부터는 차라리 원문을 봐야겠다. 2005. 12. 31.
ACM 10267, Graphical Editor http://acm.uva.es/p/v102/10267.html 어려운 문제는 아니다... 코딩은 금방 마쳤다. 허나 문제를 오해해서 파일 입출력을 해서 나중에 빼고, F 명령에 대해 설계 상으로 실수가 많아 버그 잡느냐 한참 걸렸다... 생각을 정확히 정리하고 코드에 들어가는게 훨씬 시간 절약하는 길이다... 2005. 12. 30.
ACM 706, LC-Display http://acm.uva.es/p/v7/706.html 역시 쉬운 문제. 허나 presentation error로 괜한 시간 허비... 입력을 모두 받은 다음 출력했더니 PE가 나왔다. 왜 그럴까? 어쨌든 1시간 반을 헛짓한 끝에 입력하자마자 출력하는 것으로 변경한 다음에야 accept... 2005. 12. 30.
ACM 10137, The Trip http://acm.uva.es/p/v101/10137.html 더치 페이를 하면서, 가장 금액을 적게 교환하는 방법을 택해야 한다. 각자 낼 금액은 다음과 같이 구한다. 일단 평균을 구한다. 낼 금액 - 평균 * 사람 수 = 남은 거스름 돈. 이때 거스름이 사람 수로 나누어 떨어지지 않을 경우가 있다. 이때의 거스름돈 금액은 사람 수보다 작다. 남은 거스름돈은 돈을 많이 낸 사람 순으로 나눠준다. 많이 낸 사람이 1센트라도 더 내게 산정해놓는 이유는 다음과 같다, 돈을 적게 낸 사람이 많이 낸 사람에게 주는 금액이 1센트라도 적어지기 때문이다. 문제는 최소 교환 금액을 원하므로, 선불로 많은 금액을 내었는데도 불구하고(?) 1센트 더 내는 건 어쩔 수 없게 된다. 2005. 12. 29.
ACM 10189, Minesweeper http://acm.uva.es/p/v101/10189.html 정말 쉬운 문제이다. 그런데, 심심해서 반복자하고 템플릿 좀 써서 화려(?)하게 코드를 짜보려다 엄청난 컴파일 에러에 절망하고 다 뺐다... 그리고 출력 방식을 오해해서 괜히 시간이 걸렸다. 풀어도 답답한 느낌... 추가 템플릿이구 for_each건 안되는게 아니다... 헤더 파일을 빼먹어서 컴파일 오류가 났던 것이었다. 쩝. http://www.programming-challenges.com에서는 잘 되던데... CE compile error가 나면 사용한 함수의 헤더를 확인해서 삽입해야 한다. 2005. 12. 28.
ACM 136, Ugly Numbers http://acm.uva.es/p/v1/136.html 소수(prime factor)인 2, 3, 5의 승을 구하여 작은 순대로 정렬된 숫자들의 1500번째 값을 구해야 한다. 알고리즘을 찾아내 실시간으로 해결해보려고 했으나, introduce to algorithm에서 소인수에 대한 판정 자체도 쉽지 않다는 생각을 듣고 포기...: 그거 찾아내려고 3일동안 코드를 세번 짰는데... 안타깝다... 그 알고리즘을 포기하니 오히려 답은 쉽게 보였다. 나는 휴리스틱 스타일로 문제를 해결했다. 어느 큰 값 n을 구한다.n 보다 작은 2의 제곱에 대한 숫자들을 구한다. 1, 2 , 4, 8, 16 ... < nn 보다 작은 3의 제곱에 대한 숫자들을 구한다. 1, 3 , 6, 9, 27 ... < nn 보다 작.. 2005. 12. 27.
ACM 101, The Blocks Problem http://acm.uva.es/p/v1/101.html 역시 쉬운 문제지만, 정연한 생각을 필요로 한다. 이렇게 쉬운 문제도 1시간 내에 짜기란 힘들다... 1시간 30분 소요 수정 잘못된 인덱스 값이 들어올 경우 인식하지 못하는 경우가 있었음. 운좋게도 ACM 테스트 케이스가 발견하지 못했음... -.-;; 어쨌든 수정. 2005. 12. 22.
ACM 100, 3n + 1 http://acm.uva.es/p/v1/100.html [풀이] 아주 쉬운 문제지만, 출제되는 문제의 성격을 엿보게 해준다. 문제에 없는 조건을 참가자가 가정해서는 안된다. 예제에서는 항상 두번째 입력값이 큰데, 그런 조건이 항상 성립되지 않는다는 점만 유의하면 된다. 2005. 12. 22.
ACM 103, Stacking Problem http://acm.uva.es/p/v1/103.html 긴 육각 입체가 있다고 생각해보자. 또 다른 긴 육각 입체가 있으나 앞의 것보다는 작다. 전자에 후자를 넣으려면 어떻게 해야할까? 가능한 모양을 비슷하게, 즉 둘다 길게 넣는 편이 더 잘 들어갈 것이다. 이것은 모든 n 차원에 동일하게 적용된다. 따라서 입력된 n 차원의 값을 정렬하면 - 형태를 비슷하게 만들면 - 최장거리 구하기가 된다. 이제는 플로이드 알고리즘을 적용하기만 하면 된다. 2005. 12. 18.
ACM 10069, Distinct Subsequences 동적 프로그래밍 기법을 익히고자, 관련 문제를 풀고 있다. 이번은 결과가 10의 100승까지 나온다는 점을 잊은데다, string으로 변환하고 다시 정수로 변환하는 등의 거추장스런 짓을 했더니 time limit도 나오고 해서, 프로그램을 두번이나 엎었다... 한심하다. 문자열과 단어를 입력받는다. 문자열 안에 단어의 조합이 몇 번 나올 수 있는지 체크한다. 순서는 유지되어야 한다. http://acm.uva.es/p/v100/10069.html [풀이] 동전 문제의 응용이다. 예를 들어 aaabbb 문자열에서 abb의 조합을 찾아보자. 일단 ab가 aaabb에서 나오는 회수를 x라 하자. 그리고 단어 b의 회수는 1이다(abb는 반드시 ab가 나오면 끝에 b가 나와야 올바른 조합이 되므로 1이다). 따.. 2005. 12. 17.
ACM 10131, Is Bigger Smarter? 코끼리의 체중과 아이큐를 입력받아서 체중은 증가하는 순서로, IQ는 감소하는 순서로 된 목록 중 가장 긴 것을 뽑는다. 문제: http://acm.uva.es/p/v101/10131.html [풀이] 플로이드의 길찾기 문제로 해결할 수 있다. 다음과 같은 입력이 있다고 하자. 번호체중 IQ 1 40100 2 10070 3 11060 4 5090 아래 그림은 각 번호가 연결될 수 있는 지점을 나타낸 것이다. 즉, 1번 뒤에는 모든 코끼리가 위치할 수 있고 3번 뒤에는 어떤 코끼리도 올 수 없다. 결국 이것은 플로이드의 최단 경로를 반대로 해석하여 해결 할 수 있다. 최장 경로를 찾으면 되는 것이다. 2005. 12. 4.
Floyd의 최단 경로 구하기 동적 프로그래밍의 이해를 돕고자 Floyd의 최단 경로 알고리즘을 구현해보았다. 컴파일러: Dev-C++ 4.9.9.2 [풀이] 최단 경로 알고리즘은 동적 프로그래밍을 바탕으로 해결된다. A, B, C, D 가 있다고 하자. A-C를 직접 이은 값보다 A-B-C를 이은 값이 적다면 후자가 최단 경로일 것이다. 이 값을 버퍼에 넣고, 다음에 A-D-C를 이은 값과 비교한다. 중요한 점은 다른 점들도 동시에 비교를 해야한다. 즉, A-D-C를 하기 전에 이미 A-D에 최적 경로와 D-C에 대한 최적 경로가 구해져야하는 것이다. 이는 동적 프로그래밍의 성립 조건이기도 하다. 그에 따라, 노드 개수만큼 그래프의 자료 구조를 탐색해야 한다. 알다시피 그래프의 자료 구조는 행과 열로 이루어진다. 이에 따라 프로그램.. 2005. 11. 27.
지뢰찾기 문제 설명은 pdf 참조 풀이 지뢰를 배치할 때 현재 위치에서 한칸만 앞으로 배치하면 모든 문제가 자연스럽게 해결된다. 단 한 경우에 문제가 생기는데, 아래와 같은 경우이다. 1 1 0# * # #: 지뢰 없음*: 지뢰 이때의 경우에만 지뢰를 한 칸 뒤로 물리면 된다. 2005. 11. 24.
동전 문제 문제에 대한 설명은 problem.pdf 참조. input.txt에 있는 데이터를 파이프 입력으로 주어 output과 같은 답을 얻어야 한다. ★ 풀이 예를 들어 동전이 10원, 50원, 100원이 있습니다. 이 동전을 사용하여 1000원을 맞추는 경우의 수를 생각해봅시다. 첫째로 100원을 쓰고, 나머지 900원을 10원 / 50원 / 100원으로 조합하는 방법이 있을 것입니다.둘째로 100원을 쓰지 않고, 1000원을 10원 / 50원으로 조합하는 방법이 있을 것입니다. 위 둘은 경우가 다르므로(사용하는 동전의 개수가 달라져 다른 경우가 됩니다), 더해서 올바른 조합 회수를 얻을 수 있습니다. 첫째 값은 이렇게 구할 수 있습니다. 900원에 대한 조합 회수를 가져오는 것이지요. 그럼 900원에 대한 .. 2005. 11. 24.
생선찾기 개요:윈도우 API를 공부하며 제작한 습작. 윈도우 지뢰찾기 기능을 모방하려 애썼다.객체지향 개념을 사용하려 애썼다. 컴파일 :Visual Studio .net 2003 C++ 문제점:1. 난이도를 고급으로 할 때 지뢰가 적절히 배치되지 않는다.2. GDI 방식, 비트맵의 높은 색상 비트, 크기로 인해 깜박거림 현상이 발생한다.3. 본래 첫번째로 타일을 클릭할 때에는 항상 지뢰가 없어야 하나, 미처 이 점을 파악못했다.4. 단일 스레드를 이용하여, 효과음 출력 중에 이벤트 발생 시 끊김 현상이 발생한다.5. 난이도 고급 이상의 타일 개수를 사용하고, 게임을 재시작할 때 종종 메모리 참조 오류가 발생한다. 2005. 11. 22.
신들의 사회 기억나는 문구: "나는 당신 때문에 목숨을 건졌고, 당신의 빵도 먹었소..." 이 소설은 신실한 신앙을 가진 사람에게 조금은 위험할 수 있다. 작가는 종교가 말하는 모든 기적이 과학으로 충분히 존재할 수 있다는 것을 소설 전체에서 보여준다. 지구와 비슷한 행성에 도착한 인간들은 강력한 문명으로 강력한 도시를 건설하고, 육체와 육체에 의식을 옮기면서 수천년동안 살아남는다. 그러면서 생겨난 그들의 자손이 그들에게 대항하는 것을 막기 위해 철저한 종교 사회로 만들고, 어떠한 기술적 진보도 봉쇄한다. 싯다르타는 그들의 자손들에게 기술적 진보의 길을 열어주기 위해 신들의 사회에 도전한다. 이 소설에는 불교, 힌두교, 기독교로 대표되는 은유들이 서로 대결한다. 재미있는 점들은 싯타르타 자신은 단순히 신들(자신의 동.. 2004. 6. 5.
불사판매 주식회사 과학 소설은 참으로 흥미롭다. 현실에서 불가능하리라고 생각되는 조건에 인물들을 몰아넣으며 맞닥뜨리는 사건들은 그야말로 현실적이기 때문이다. 이 소설은 매우 흥미로운 주제를 바탕에 깔고 이야기를 전개한다. 내세가 과학적으로 증명이 되었다는 주제. 그런데, 주인공은 과거에 죽어 미래에 환생이 되었다(과학의 힘으로). 소설은 주인공이 미래에 적응하면서 내세를 믿어가는 심정을 추적한다. 마침내 후반부에는 자신이 영향을 미친 한 사람에게 자신의 육체를 양도하고 스스로 죽음을 택한다. 결말은 조금 맥없다. 하지만, 죽음에 대해 고민을 해봤다면, 하나의 풍자로서 읽을만한 소설이다. 어쨌든 책을 읽은 후 의문이 생겼다. 자신이 선택한 내세에서 또 다른 선택을 한다면...? 또 다른 내세가 기다리고 있을까? 만일 그토록.. 2004. 6. 5.
대망 흔히 종달새 이야기 비유에 등장하는 일본 전국시대 3인방, 오다 노부나가 / 도요토미 히데요시 / 도쿠가와 이에야스. 후자이자, 도쿠가와 막부를 연 최후의 승리자인 그는 간단히 평가하면 종달새가 울기까기 기다린 인물로 그려진다. 그러나, 한 인물의 생애를 그렇게 간단하게 논할 수 있다면 삶의 나날은 극단과 파괴로만 빛날 것이다. 이 소설은 이에야스가 막부를 열기까지 겪는 전국시대의 다양한 사건들을 다루고 있다. 하도 잔잔한 에피소드가 많다보니 이 소설을 끝까지 읽기는 매우 힘들다. 이른바 시선이 분산된다고나 할까. 물론 18년 동안 연재하려면 작가는 많은 이야기를 늘어놓을 수 밖에 없었을 것이다. 그 사정은 이해하지만, 이에야스의 일대기에 관심있는 나에게는 전국시대 에피소드 모음집을 끝까지 읽기에는 성이.. 2004. 6. 4.
More Effective C++ 장점: 고급자로 발돋움하려는 그대를 위해 추천 단점: 속도 시대에 능률은 어떤 의미를 가질까... 일단 딴 얘기. 쉬운 스크립트 언어를 찾다가 파이썬을 만나게 되었다. 그 사이트 게시판에서 어떤 글을 보았다. "C++은 일부러 어렵게 보이려는 언어 같아요." 정말 아닌게 아니라 그런 거 같다. 예전 마소 잡지에서 본 기사가 생각이 난다. C 프로그램 어렵게 찾기 대회였나? C코드를 난독조차 할 수 없도록 마구 뒤엉켜놓은 코드였다. 특별히 1등 코드가 소개되어 있었는데, #define이 다단계로 되어 있고 main함수 조차 define으로 선언해놓아 발견할 수 조차 없는 그야말로 괴상망칙한 코드였다. 어쨌든 버그는 없었다 ^^; 왜 이런 생각이 들었을까. 이 책은 확실히 공부하는데 좋은 교재다. 그러나 밑.. 2003. 12. 10.
비주얼 베이직 6 비주얼 베이직을 만만히 보는 분들이 있을 것이다. 머, 나도 그랬다 ^^; 그러나 최근의 프로그래밍 흐름은 조금씩이나마 변하고 있다. 이제 효율성보다 생산성이 점점 강조되고 있다. 시스템 성능이 급격히 향상되고 컴파일러 성능도 이에 걸맞게 발달되어, 코드 수준의 최적화는 솔직히 예전만큼 큰 의미를 갖지 않게 되었다. 이런 시대 환경을 맞이하여 비주얼베이직은 윈도우 플랫폼 에서의 산출물을 제작하는데 최고의 도구이다. 배우기 쉽고, 응용하기도 더할나위 없이 좋다. 그 세계로 입문하게 도와주는 좋은 책이 여기에 있다. 본인은 책 내용도 중요히 여기지만, 편집을 한층 더 중요히 생각한다. '보기 좋은 떡이 먹기도 좋다'라는 속담 때문일까. 컴퓨터 책은 집중을 요하고 보통 책보다 읽어야하는 내용이 많다. 편집이 .. 2003. 12. 10.
컴퓨터 무작정 따라하기 사실 내가 이 책을 볼 이유는 전혀 없었다. ^^; 그러나, 아버님이 오랜 직장 생활을 관두고 회사에서 쉬고 계신 지금, 그 이유가 생겨났다, 신문에서 지겹게 떠들어대는 정보화시대에 뒤쳐졌음을 느끼신 아버님의 요구가 초보(?)용 쉬운 책을 알아보도록 만들었던 것이다. 게다가 불호령이 두려웠기 때문에, 아버님이 좌절하지 않을 만한 쉬운 책을 찾기 위해 열심일 수 밖에 없었던 것이다. 그런데... 쉬운 책 찾기가 이리 어려울 줄이야! 처음이 쉬우면 나중에 이상하고, 책은 쉬운 것 같은데 편집이 문제이고... 맘에 딱 맞는 책을 찾으려고 보낸 수시간! 결국 못 찾고 표지가 예쁜 책을 골라버리고 말았다... ^^; 아버님에게 정성껏 골랐음을 강조하며 책을 드렸다. 그리고, 변변이 가르쳐드리지도 못하고 출퇴근을 .. 2003. 12. 10.
초보자를 위한 윈도우즈 게임 프로그래밍 주의! 이 책을 사기 전에 단 하나 주의할 점이 있다. 제목에 당당히 써있는 '초보자를 위한...'이란 말이 새빨간 거짓말이란 사실이다. 하긴 어떤 경우에는 사실이다. C/C++에 대한 충분한 지식을 갖고 있고 윈도우 프로그래밍도 조금 알고 있는, 프로그래머 초보자에 해당될 경우에. 프로그래밍의 '프'자도 모른다? 그런 경우 이 책을 구입하는 건 그야말로 돈 낭비다. 이 책의 장점? 바로 핵심을 요약한 것에 있다. 거의 모든 컴퓨터 책이 천 페이지가 넘는 두께에 두손으로 들기에도 힘겹다.(하긴 2천 페이지가 넘는 책도 있지만) 하지만 이 책은 공부하기에 딱 알맞다. 먹기 좋다! 쉽고 양이 적당하여 초보 프로그래머를 질리게 하지 않기에 진짜 딱 좋다. 그러고보니 저자가 쓴 비슷한 책이 하나 있다. "Tri.. 2003. 12. 10.
해킹, 속임수의 예술 고등학교때인가? 리더스 다이제스트에 케빈 미트닉과 그를 체포한 사람의 이야기를 본 적이 있다. 뭐, 그 때는 어린지라 정말 흉악한 범죄자로 보였다. 제 집처럼 드나들면서 정보를 맘대로 조작하고 훔쳐내고... 반면에 그를 잡는데 공헌한 사람은 실력은 부족하지만(?) 인내심의 극한을 발휘한 끝에 성공했다는 이야기였다. 컴퓨터에 관심을 갖기 전이어서 그런지 그 사람의 기술은 더 놀랍게 보이기만 했다. 이제 나 이가 들고, 컴퓨터도 조금은 아는 지금 이 사람이 교도소에 갔다가 석방되었다는 소식도 들었고 한 권의 책을 냈다는 소식도 들었다. 제목 한번 끝내준다. 사기술? 이 사람의 책에서는 실제(?) 해킹 기법이 소개된다. 그러나 엄청난 기술을 생각했던 일반인들이 보기에는 너무나 어이없을 것이다. 정말 사기술 맞.. 2003. 12. 10.
Essential(에센셜) C++ 출근 전, 자기 전, 화장실 등에서 틈나는대로 가볍게 읽는 중인데, 어느덧 반을 넘게 읽었다. 이유인즉 이 책의 분량은 비교적 작기 때문이기도 하다. 일단 평가자의 상태를 적어보자. C언어는 비교적 자신있게 알고 있고 하드웨어도 다뤄봤다. 그러나 제대 후 지금까지 공부에 소홀한 탓에(대신 게임에...) C++의 현대적 테크닉에 대해서는 무지몽매한 상태. 여러 권의 C++ 책을 갖고 있고 봤으나, 여는 순간부터 분위기가 남달랐다. 알고만 있었으나, 뇌 속에 사문화되어 사용처를 몰랐던 여러 예약어를 예제를 통해 보여준다. 헉... 이건 이럴 때 쓰는 거구나. 감탄을 한 것이 몇 번인지 모르겠다. 이렇게 번역이나 편집 상태나 간접적으로 언급되었다. 구어체로 서술된 탓인지 참 읽기 쉽다는 느낌이 든다. 중간중간.. 2003. 12. 10.
C++ Standard Library: 튜토리얼·레퍼런스 먼저 언급해둘 사항이 두 가지 있다. 리뷰어의 상태이다. 첫째, 나는 STL을 안 지 일주일도 되지 않았다. 헉... 그런 만큼 나의 리뷰는 나처럼 어디서 STL을 귀동냥으로 얻어들은(^^;) 사람에게는 참고가 될 만할 듯 싶다. 둘째, 이 책을 본 지는 24시간도 되지 않았다. 헉... 그것도 내 책도 아니다. ^^;;; 황당한 상황이다... 이렇게 고해성사를 했으니, 시원한 마음으로 글을 써보겠다. STL 쌩초보자인 내가 어떻게 관심을 갖게 되었을까. 회사의 한 프로그래머와 대화를 했는데, 자신도 프로젝트 끝나고 STL을 알게 되었다고 한다. 그런데, 진작에 이걸 알았다면 프로젝트를 5개월은 빨리 끝냈을 거라고 했다. 평소 효율적(?)인 프로젝트 수행에 관심이 많은 나는 당연하게도 STL에 관심을 갖.. 2003. 12. 10.

티스토리툴바