본문 바로가기

코드103

ACM 10315, Poker Hands http://acm.uva.es/p/v103/10315.html 크게 어려운 문제는 아니나... brute force 알고리즘의 무시무시함을 느끼게 해주었다. 즉흥적으로 코딩하다보니, 결과는 time exceed limits가 나와버렸다. 700줄이 넘어가던 이전 코드를 거의 다 버리고, 새로 작성했다. 에구... 번호가 동일한 카드 개수를 세어서 맵에 보관함으로써 쉽게 계산할 수 있었다. 한편, 승부가 비겼을 때 사용하는 2차 조건이 양수이다. 각 경우에 대한 맵도 만들어서 2차 조건을 보관했다. 그러므로써, 1차 조건 만족여부와 2차 조건을 동시에 체크할 수 있도록 했다. 2006. 1. 20.
ACM 102, Ecological Bin Packing http://acm.uva.es/p/v1/102.html 쉬운 문제지만, 고생을 했다. 이유인즉, 나의 의욕 과잉 때문... 너 무 간단한 문제라 생각하여, 오히려 복잡하게 코드를 작성하다 완전히 잘못된 사례가 되었다. 게다가 속출하는 컴파일 에러로 인해 신경질도 상당히 발생했다... 어쨌든 이제 컴파일 에러는 해방이 되었다. online judge 컴퓨터가 g++ 2.95를 사용하여 컴파일한다는 사실을 알았고, 이는 DEV-C++ 4 버전을 사용하여 쉽게 문제를 발견할 수 있기 때문이다. g++ 2.95는 를 인식하지 않는다는 사실을 그래서 5분 만에 알아내서 컴파일 문제를 해결했다. 그 다음 문제는 문제를 대강 보는 버릇... 동일한 최소 이동 값이 나왔을 때, 알파벳 순서대로 있는 것을 우선적으로 .. 2006. 1. 19.
ACM 10038, Jolly Jumpers http://acm.uva.es/p/v100/10038.html 지난 번에 너무 골치를 썩여 쉬운 문제를 택했다. 그러나... 입력 끝부분을 제대로 처리하지 못해 괜시리 헤맸다. 게다가 알고리즘 트레이닝 북의 번역 또한 문제였다. 입력 부분이 애매하게 설명이 되어있다. 입력되는 수열의 가장 처음은 정수 개수인데, 이런 설명은 어디로 가버렸다. 역시 원문을 보는 것이 훨씬 낫다. 참고로 정수의 범위는 int 를 써도 무방하다. 2006. 1. 11.
ACM 104, Arbitrage http://acm.uva.es/p/v1/104.html 각 국가 간의 환율을 입력으로 제공한다. 이것을 바탕으로 환차익을 거두어야 하는데, 1% 이상 얻을 수 있으면서, 거래 국가는 최소로 해야한다. 이 번 문제는 아주 많은 고민을 했다. 다음과 같은 점을 아주 뒤늦게 생각해냈기 때문이다... 국가가 정점(vertex)이고, 환율이 경로(path)라고 가정하자. 그럼 문제가 쉽게 파악된다. 국가를 가장 적게 거치는 경로를 구하기 위해 Floyd-Warshall 알고리즘이 있다. 여기까지는 생각했으나 교환 법칙이 성립하지 않고, 이로 인해 중간 경로를 활용할 수 없어 FW 알고리즘을 적용할 수 없다고 판단해버렸다. 당연히 이것은 내 실수이며 acm.uva.es의 게시판에서 힌트를 얻어 답을 찾을 수 있었.. 2006. 1. 10.
ACM 10142, Australian Voting http://acm.uva.es/p/v101/10142.html 생 소한 호주식 투표 제도 덕에 문제가 눈에 잘 들어오지 않는다는 점을 제외하고는 그리 어려울 것 없는 문제다. 나는 deque을 사용하여 문제를 해결했다. deque은 가장 앞/뒤에 있는 원소를 제거/삽입할 수 있다. 삽입은 push_back ()으로 넣고, 참조는 front ()하여 가장 높은 우선순위의 투표자를 가려냈다. 가장 앞에 최소로 표를 획득한 자가 있을 경우는 pop_front () 하여 제거했다. 덕분에 알고리즘은 쉽게 구현되었다. 그러나... 이번 문제는 나의 시간복잡도 측정 능력이 얼마나 조악한지 깨닫게 해주었다. 일단 제거하는데 많은 시간이 소요되었다. 그도 그럴 것이 투표는 최대 20명에 대한 투표가 1000건이 들어.. 2006. 1. 7.
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.

티스토리툴바