안녕하세요 hellogaon입니다.2019년 12월 28일, 작년에 이어 한양대학교 에리카 알고리즘 학회 '영과일'의 내부 대회Zero One Algorithm Contest 2019(이하 ZOAC 2019)가 개최되었습니다. 대회가 열리기 한 달 전, 대회 개최 조건이 변경되어 3명 이상의 검수진이 필요하였고 자칫하면 대회가 열리지 못할 뻔도 하였으나 영과일 회장님의 대회를 개최하겠다는 열정에 감동하여검수진을 구할 수 있었다는 후문이 있습니다. 출제자로는 저와 재현이(TheKinGoD)와 병서(bsyun0571)가 참여하였고 정말 훌륭하신 cheetose님, functionx님, h0ngjun7님, jh05013님, oree2113님, rdd6584님께서검수진으로 참여해주셔서 더욱 높은 퀄리티의 대회를..
3176번: 도로 네트워크 - LCA 간선에 가중치가 있는 트리가 주어질 때 정점 u에서 정점 v까지의 경로의 간선들 중가장 작은 가중치, 가장 큰 가중치를 출력하는 문제이다. 100,000개의 쿼리를 처리해야하기에 효율적인 방법이 필요한데경로가 유일하다는 것을 이용하여 LCA를 이용해보자u, v의 경로는 u - LCA(u,v) - v 로 이루어져 있기 때문이다.그렇다면 LCA를 구하면서 가장 작은 가중치, 가장 큰 가중치를 구할 수 있을까?LCA에서는 정점의 2^k번째 부모를 저장해놓는다.즉 한 정점의 2^(k+1)번째 부모는 그 정점의 2^k번째 부모의 2^k번째 부모와 같다를 이용하였다.이와 비슷하게 한 정점의 2^(k+1)번째 부모까지의 가장 작은 가중치는min(그 정점의 2^k번째 부모까지의 가..
3015번: 오아시스 재결합 N개의 수들이 주어질 때, 이 중 두 개의 수(한 개의 쌍)를 고른다.이 때 이 두 수 사이에 이 두 개의 수보다 크지 않은 수들로만 구성되는 쌍의 개수를 묻는 문제이다. N개의 수들이 담겨져 있는 배열을 A라 할 때앞에서부터 차례대로 A[i]를 추가함에 따라 생기는 쌍의 개수를 생각해보자.만약에 A[i-1]이 A[i]보다 작다고 생각하자.그럴 경우에는 앞으로 A[j](i < j)를 확인 할 때 A[i-1]과 A[j]이 쌍을 이룰 일은 절대 없다.이 두 수 사이에 A[i-1]보다 큰 A[i]가 존재하기 때문이다.즉 내가 A[i]를 추가하였을 때 이전의 A[i]보다 작은 수는 앞으로의 결과에 영향을 못끼친다는 것이다.그러므로 매 상황마다 이전의 자신보다 작은 수를 제거하면서 답..
14577번: 일기 예보 - 구간트리 (세그먼트 트리) kks227님 블로그의 오프라인 쿼리를 읽고 인상 깊어 작성하게 되었다.이 문제에서는 4개의 쿼리가 있다.1. 하나의 값에 X를 더한다.2. 하나의 값에 Y를 뺀다.3. 값이 L ~ R 사이인 원소의 개수를 구한다.4. K번째로 큰 값을 구한다.이러한 쿼리들을 10^5개를 처리해주면 되는 문제이다. 1번과 2번은 구간트리에서 많이 접해본 적이 있다.어떤 idx에 대하여 X를 더하는, Y를 더하는 과정은 O(lgN)에 구할 수 있다. 3번 쿼리는 값이 L ~ R 사이인 원소들의 개수를 구하는 쿼리이다.이 쿼리를 어떻게 처리해야할까?나라들의 현재 값이 들어있는 배열을 A라 할 때 A = {1, 2, 10, 2, 4} 가 된다고 하자.구간트리에 이 값이 ..
12995번: 트리나라 - DP kks227님 블로그의 동적 계획법 5를 읽고 인상 깊어 작성하게 되었다.트리에서 DP를 사용하는 문제 유형에 대하여 설명하는데 그 중노드 u를 루트로 하는 서브트리 안에서 모든 자식 노드에 분배를 해야하는 문제를 어떤 식으로 접근할까?에 대한 유형이다. 이 문제는 트리가 주어질 때 크기가 K인 트리를 만들기 위한 경우의 수를 묻는 문제이다.이런 문제를 풀 때 기본적인 아이디어는 u의 자식 노드를 v1, v2, ... vm이라 하면u와 v1을 루트로 하는 서브트리랑만 연결 될 때,u와 v1, v2를 루트로 하는 서브트리랑만 연결 될 때,...u와 v1, v2, ... vm을 루트로 하는 서브트리랑만 연결 될 때 순으로 구하게 된다.약간 플로이드 와샬에서 i 정점에서 j 정..
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좌표}, {왼쪽으로 갈 수 있는 횟수, 오른쪽으로 갈 수 있는 횟수} }를 담을 것이다.위아래로 움직이는 것은 상관이 없으므로 처음에 시작 할 때 시작점에서 시작하여 갈 수 있는 위, 아래 칸들을 큐에 ..
Mojave 업데이트 이후 크롬의 글씨체가 미세하게 얇아지며 오래 볼 경우 눈이 아파지는 현상이 나타납니다. Mojave 업데이트 이전 Chrome Mojave 업데이트 이후 Chrome 이렇게 비교해보면 글씨폰트가 미세하게 다른 점을 확연히 볼 수 있습니다.업데이트 이전처럼 보이게 하기 위한 해결방법은 터미널에 defaults write -g CGFontRenderingFontSmoothingDisabled -bool NO 을 작성해 준 다음 크롬을 종료한 뒤(Command + Q) 다시 실행해주면 사용할 수 있습니다.