리유나의 항해일지

안녕하세요 유나입니다. 오늘은 ACM-ICPC 예선을 치르고 왔습니다. 2019 ICPC Asia Daejeon Regional Contest 팀으로 참여했습니다. 우선 진행 도중에 서버가 터지는 정말 대참사가 벌어져서... 대회 진행 도중에 문제가 뭐가 맞고 뭐가 틀린지도 모르는 채로 한참을 진행했습니다. 이 점은 굉장히 화가 많이 났습니다. 이게 작은 대회도 아닌데...제발 운영 좀 제대로 했으면 좋겠네요 일단 여기서 되게 화가 많이 났습니다. 우선 지금 공개된 스코어보드에서는 전체 5위를 기록하고 있습니다. 프리즈 된 이후 채점된 결과를 보니 A도 accept되어서 8솔브했습니다. 문제 별 후기는 다음과 같습니다. A(All you need is dating) LR 플로우로 되는 문제입니다. B(B..

문제는 여기 1520 내리막길 문제는, 제가 무려 2년 전에 틀려놓고 그뒤로 방치했던 문제입니다. 무시무시한 런타임에러... 그래서 이제와서 다시 재도전해보려고 켜봤습니다. 문제 자체는 말이 쉽습니다. 숫자들이 주어지고, 대충 그걸 높이라고 치면 쭉 내리막길이 되도록 잘 내려가는 루트가 몇개나 있는지, 찾으면 되는 문제입니다. 너무 대놓고 '나 DP예요 DP!'라고 광고하는 거 아닌가 싶을 정도의 문제입니다. 대충 첫칸부터 시작해서 DPS로 탐색을 하는데, 이미 방문한 적 있는 곳이면 기록을 미리 해두고 그곳으로 가는 내리막길이 있음+그길로 가면 끝까지 갈 수 있음이면 그 경우의 수만큼 더해주면 되는 간단한 코드를 생각할 수 있습니다. 구현 자체는 크게 어렵지 않았습니다. m,n=map(int,input..

ACM-ICPC에 이번에도 참가하게 되었습니다! 일단 예선 전까지 열심히 연습해서 전국 본선 진출을 목표로 해봐야 할 것 같네요! 다른 팀원 두분이 다 저보다 훨씬 실력자셔서, 팀에 누는 안 끼칠 정도로만 힘내보려고 합니다 ㅠ 팀명은 아직 안 정해졌지만 나중에 정해지면 올릴...수도 있습니다.

오랜만입니다. 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(..