15678번: 연세워터파크 - DP kks227님 블로그의 동적계획법 4를 읽고 인상 깊어 작성하게 되었다.이 문제는 임의의 시작점에서 번호가 증가하는 방향으로 징검다리를 건너게 되는데한번에 D개 이하의 징검다리를 뛰어넘을 수 있을 때 점수의 최댓값을 구하는 문제이다.풀이는 간단하다.어떤 도착점 k의 관하여 dp(k)를 도착점 k에 도착했을 때 얻을 수 있는 최대 점수라 하면,dp(k)는 max(0, k-D) ~ k까지의 dp값 중 최댓값이 된다.이후 모든 i에 대하여 dp(i)의 최댓값이 답이다. 이 때 구간에 대하여 최댓값을 구하는 과정을 반복하여야 한다.구간이기에 구간 트리를 이용하여 O(lgN)만에 최댓값을 찾을 수 있고이는 시간복잡도가 O(NlgN)만에 문제를 해결할 수 있다. 이 때 kks22..
안녕하세요 hellogaon입니다.2018년 12월 29일, 한양대학교 에리카 알고리즘 학회 '영과일'의 첫 내부대회Zero One Algorithm Contest 2018(이하 ZOAC 2018)가 열렸습니다! 오프라인 대회에서는 8팀, 온라인 Open Contest에서는 20여명 분들이 참여해주셨습니다. 아무래도 대회 수상자 및 알고리즘 멘토들이 대회 운영진을 맡았고대부분 신입생들이 대회를 참가하다보니 난이도 조절에는 실패가 있었지만Open Contest에서 많은 분들이 참여해주셔서 재밌었습니다. 공식적으로 공지하지는 않았지만 출제진들끼리 상의하여 많이 풀릴 거 같은 순으로 배치를 하였음에도 불구하고출제진의 생각과 푸는 사람의 체감 난이도는 정말 다르다는 것을 새삼 느낄 수 있었고아쉬운 점도 있었지만..
A - Oh Those Palindromes 100,000자리의 문자열이 주어질 때 문자들을 잘 조합하여 만든 문자열의 부분문자열의 팰린드롬의 개수가최대가 되게 하는 문자열을 구하는 문제이다.이는 문자열 내의 문자들을 정렬하여 출력하면 된다. 생각해보면 이 방법이 답이라는 것을 쉽게 유추할 수 있다. B - Labyrinth 시작점이 주어지고 왼쪽, 오른쪽으로 갈 수 있는 횟수가 정해져있을 때주어진 매트릭스에서 몇 개의 칸에 도달할 수 있는 지를 구하는 문제이다.queue 를 선언하여각각 { {y좌표, x좌표}, {왼쪽으로 갈 수 있는 횟수, 오른쪽으로 갈 수 있는 횟수} }를 담을 것이다.위아래로 움직이는 것은 상관이 없으므로 처음에 시작 할 때 시작점에서 시작하여 갈 수 있는 위, 아래 칸들을 큐에 ..