SDS Expert-to-be

sds.md

SDS Expert-to-be

강사. 강동구

1회

• 2차원 벡터 연속된 180도 범위의 모든 벡터를 쓰는 것이 정답이다.

• 분수 찾기 이분검색 + 특정 수 이하의 기약분수 개수 구하기 (에라토스테네스의 체)

• Utopia Divided IOI 2002 보고서 참조 http://olympiads.win.tue.nl/ioi/ioi2002/contest/report.pdf

• 페리 수열의 합 여러 N에 대해 답을 출력해보고 규칙을 찾는다. N번째 페리 수열의 길이와 비례한다.

2회

• 히스토그램 스택을 쓰면 선형 시간에 풀 수 있다.

• 최소값 찾기 유명한 Sliding Window 테크닉을 쓰면 된다.

• CCW 기하의 기본인 CCW 함수를 공부하는 문제

• 다각형의 면적 사선식으로 다각형의 면적을 구하는 공식을 연습한다.

• 교차 두 선분의 교차여부 판별법을 배우고 연습하였다. box_checking과 ccw_checking이 있다.

• 볼록 껍질 Convex Hull 알고리즘을 배우고 연습하였다.

• 고속도로 볼록 껍질을 이용하여 가장 먼 두 점을 찾는 법을 배우고 연습하였다.

• 가장 가까운 두 점 분할정복으로 가장 가까운 두 점을 찾는 법을 배우고 연습하였다.

3회

• A+B: A+B를 출력한다.
• 집합의 표현: union find 연습 문제이다.
• 최소 스패닝 트리: kruscal 연습 문제이다.
• 네트워크 연결: kruscal 연습 문제
• 행성 터널: x, y, z 각각으로 정렬한 3개의 리스트를 가지고, 3n개의 이웃쌍 중 최소값을 골라 연결해 나가면 된다.
• 두 번째로 작은 스패닝 트리: 우선 MST를 구한 뒤, 나머지 간선들을 추가해 본다. cycle이 생길텐데, 이 cycle 상에서 최대 가중치 간선을 제거해주면 second MST를 구할 수 있다. 이를 위해 LCA와 PQ를 익혀야 한다.
• 스패닝 트리: kruscal을 제대로 이해했는지 보는 문제. 같은 가중치인 간선이 최대 4개이므로 많아야 2^4가지를 고려하면 된다.
• 정상: 높은 지대부터 union find로 이웃한 4칸을 합쳐나가면 된다.

3.5회

공통조상찾기와 우선순위 큐를 연습하는 세션이다. 모두 기본적인 알고리즘으로 풀 수 있다.

• 소수의 곱 1에서 출발하여 여기에 작은 소수부터 곱해나간다. 매 순간 다음 가장 작은 수가 될 후보들을 우선순위 큐에 가지고 있으면 된다.

나머지 문제는 LCA와 PQ를 변형하지 않고 그대로 쓰면 되는 기본적인 문제들이다.

4회

Range Tree들을 공부하는 세션이다.

• A: 구간 트리를 배우고 연습한다.
• B: 구간 트리 실습문제.
• C: Lazy Propagation 테크닉 연습
• D: 2차원 구간 트리 연습
• E: 2차원 구간 트리를 선형 메모리로 구현하면 된다.
• F: 현재 i번째 쿼리로 x번 DVD를 옮긴다면 마지막으로 x번을 옮겼던 쿼리의 번호 j를 찾는다. 정답은 [j+1,i-1] 구간의 쿼리에서 unique한 DVD들이 몇 가지가 등장했는지를 찾으면 된다. 각 DVD별로 마지막에 등장한 위치의 쿼리에만 +1을 해 두면 이들의 합이 정답이 된다.