리유나의 항해일지

오랜만입니다. PS연습을 다시 시작해서 감을 살리려고, boj에서 알고리즘 분류 별로 나누어진 카테고리를 들어갔는데, 이 문제가 왜인지 눈에 밟혔다. 문제는 여기 초등부 정올 문제였다고 하는데, 언뜻 봐서는 잘 방법이 떠오르지 않았다. 대충 그리디하게 하면 될 것 같은데...하는 생각을 하고 있었다.(사실 문제 분류도 그리디였다.) 그런데 의외로 그게 이런저런 케이스들도 생각 많이 해줘야 하고, 못할 것 같지는 않아서 어려울 거라고 생각했는데, 어차피 10!은 해봐야 4백만도 안되고, 그냥 완전탐색으로 해봐도 괜찮을 것 같았다. 결국 구현의 문제였고, 파이썬에는 itertools 모듈이 있어서 구현을 아주 간편하게 할 수 있었다.(만약 그렇지 않았더라면 아마 백트래킹으로 모든 경우를 찾는 게 가장 어려운..

어제 이 문제를 해결하고 가만 생각해보니, 아무래도 더 빠른 방법이 있을 것 같다는 생각을 지울 수가 없었다. 거기에, 결국 ICPC는 C++로 짜야 할텐데, C++로 짜는 방법도 생각해봐야 하지 않겠나는 생각을 했다. 더 빠른 방법은 사실 생각해보면 꽤 빠르게 나왔다. 처음에 두개의 합으로 된 리스트를 만들 때, 원소들을 추가하는 방식이 아니라 미리 길이 40만짜리 리스트에다가 1씩 추가하는 식으로 구현하면 O(n^2)만에도 풀 수 있었을 것 같다.(게다가 이 방법이 C++로 구현하는 데에도 조금 더 도움이 될 것 같다!) 이 생각을 하고 코드를 조금 수정해보았다.(Python) w,n=map(int,input().split()) L=list(map(int,input().split())) L.sort(..

작년에 ACM-ICPC 대회에 출전했던 적이 있었다. 내가 참가했던 팀은 5개 해결로 전체 80등 언저리로 본선 진출에는 실패했었는데, 올해에 다시 이 대회에 나가려고 생각을 하고 있다. 그 과정에서 작년에 제일 고민을 많이 해봤었던(그렇지만 결국 풀지는 못했던)Parcel 문제를 다시 떠올리게 되었고, 1년만에 문제에게 복수를 하러 가보려고 한다. 문제는 여기서 볼 수 있다. 쉽게 말해서 뒤에 주어진 정수들 중에서 4개 골라서 앞에서 주어진 정수를 합으로 되게 만들 수 있냐는 문제이다. 이런 문제에서 흔히 생각할 수 있는 방법은 다음과 같다. 1. 완전 탐색. 주어진 거 4개씩 고르는 경우를 다 찾아보면 된다. 구현은 재귀적으로 대충 하면 될 거 같다. 그러나 n이 5000개까지 가능하다. 4개씩 다 ..

2001년 ACM ICPC 예선으로 나왔던 문제입니다. 문제는 여기서 확인할 수 있습니다. 고등학교 2학년 때였나, 특이한 정보과학 과목을 수강했던 적이 있었습니다. 선생님께서 마지막에 문제 24개를 주시면서 여기서 95% 이상을 풀면 시험 성적에 관계없이 A+을 주겠다고 하셨던 적이 있는데, 그 중 한 문제로 처음 접했던 기억이 납니다. 처음에 이 문제를 봤을 때는 DP(동적계획)와 같은 방법을 사용해서 재귀적으로 풀어야 하나 하고 고민했지만, 이런 시도가 언제나 그렇듯이 잘 되질 않았습니다. Brute Force(완전탐색)으로 해볼까도 생각해봤는데, 아무래도 m+n이 10 이상 30 미만인데 30이면 전체 가능한 경우의 수가 2^30(≒10^9)정도로 조금 무리인 감이 있습니다.(게다가 저게 되는지 ..