동아리 내에서 진행되는 알고리즘 스터디 정리본입니다. delena0702 codingstarfish님과 함께 진행하였습니다.

03.20 OT

첫 만남을 통해 스터디의 가이드 라인을 잡았다.

팀 목표

1. 각종 대회(팀 대회 및 개인 대회) 수상
2. 새로운 알고리즘 학습
3. PS 대회 정보 공유

스터디 진행 방식

• 선정된 문제를 스터디 이전에 풀고, 정기 모임에서 코드를 리뷰 및 해설하는 시간을 가집니다.
• 문제 선정은 BOJ에서 특정 조건에 따라 임의 추출하거나, Codeforces 및 대회 기출 문제를 이용합니다.
• BOJ에서 문제를 선정할 경우 백준 그룹의 연습 기능을 이용합니다.

세부 일정

• 정기 모임은 별도의 일정이 없는 경우 월요일 16시 ~ 18시에 학교 내 공간에서 진행합니다.
• 정기 모임 종료 후, 다음 주제를 정하여 문제를 선정하고 다음 정기 모임까지 풀이 아이디어와 간단한 해설을 준비합니다.

BOJ 문제 선정 기준

• 스터디 참여 인원이 모두 풀지 않은 문제여야 합니다.
  • ~@id 혹은 !@id 쿼리를 이용하면 해당 id를 가지고 있는 인원이 풀지 않은 문제를 뽑을 수 있습니다.
• 팀원과 합의한 태그들 중에서 문제를 선정합니다.
  • #tag 쿼리를 이용하면 해당 tag를 가진 문제를 뽑을 수 있습니다.
• 각자 공부하고 싶은 알고리즘 주제 위주로 문제를 선정합니다.

Codeforces가 스터디 진행 중에 있고, 모든 팀원이 참여할 수 있는 여건이 되는 경우, 대체될 수 있습니다.

03.27 1차 코드 리뷰

5문제에 대해 문제 풀이를 진행하였습니다.

A [1101번] 카드 정리 1

접근 과정

어느정도의 생각을 통해 특징을 발견할 수 있었다.

• 최소 이동 횟수는 반드시 $N-1$이하이다. 이는 모든 박스의 카드를 조커 박스로 이동하는 경우 $N-1$번 안에 이동할 수 있다.
• 각 카드 박스는 $0$회 또는 $1$회 이동으로 정리 가능하다. 이동을 해야하는 경우는 모두 조커 박스로 이동시키면 된다.

풀이

각 박스를 조커 박스라고 가정하고, 최소 이동 횟수를 구하여 답을 결정한다.

$i(1\leq i\leq N)$번 박스가 조커 박스일 때 조커 박스를 제외한 나머지 박스에 대해 아래의 규칙대로 수행한다.

• 박스 내에 카드가 없는 경우 - 이동하지 않는다.
• 박스 내에 카드가 1종류인 경우 - 해당 종류의 카드를 보관 중인 박스가 있으면 이동이 필요하다. 없으면 이동하지 않는다.
• 박스 내에 카드가 2종류 이상인 경우 - 모든 카드를 조커 박스로 이동한다.

Comment

모두가 같은 방식으로 풀어주었습니다.

B [1229번] 육각수

접근 과정

육각수의 규칙을 찾아 미리 육각수를 구한 후에 진행을 해야했다.

$n$번 육각수를 $a_n$라 했을 때

$\begin{cases} a_1 &= 1 \\ a_{n + 1} &= a_n + (4n + 1) \\ \end{cases}$

$\therefore a_n = n(2n-1)$
위와 같이 일반화가 가능했다.

육각수를 바로 구할 수 있으니 나머지는 DP를 이용하여 N을 만드는 최소 개수를 구하려고 하였다.

풀이1(DP)

$a$를 만드는데 사용한 육각수의 최소 개수를 $x$라고 하자. $a$는 특정 수에서 어느 육각수를 더해 만든 수일 것이다. 여기서 특정 수를 $b$라고 하자. 그렇다면 $b$를 만드는데 사용한 육각수의 최소 개수는 $x-1$이다. dp table에 최솟값만 남기면서 갱신을 해주면 된다.

$i(1\leq i\leq N)$에서 각 $i$에서 $i$보다 작거나 같은 육각수를 모두 돌면서 dp table을 갱신해주었다.

풀이2(BFS)

100만 이내의 모든 육각수를 만들고 bfs로 $N$에서 육각수를 빼가면서 0으로 도달할 때까지 탐색을 진행해준다.

Comment

delena0702님이 단순 bfs는 $N=999999$에서 시간 초과가 일어날 가능성이 있어 이미 탐색에 사용한 육각수 보다 작은 육각수는 탐색하지 않도록 최적화를 진행해주었다고 한다.

문제에 1791보다 큰 정수는 ~ 의 설명을 이용하여 각 범위 내에서 미리 구해놓은 육각수를 반복문을 돌려 구하는 방법도 있다.

C [17398] 통신망 분할

접근 과정

간선의 제거는 어려운 문제이다. 따라서 간선을 추가하는 문제로 변형하였다. 즉, 제거되는 간선을 제외한 그래프에서 간선을 추가하는 방식으로 해결하고자 하였다.

연결을 제거할 때 통신망이 분리되는 것은 변형된 문제에서 연결을 추가할 때 통신망이 합쳐지는 과정과 같다. union-by-size를 사용해 카운팅까지 진행해주었다.

풀이

1. 쿼리에 사용된 연결을 check 배열에 저장하였고, check 되지 않은 간선들을 union 해주었다.
2. 가장 마지막에 주어진 쿼리부터 진행을 해주었다. 해당 쿼리에서의 연결에서 주어진 두 노드를 merge하기 전에 두 노드가 다른 그룹에 속해있다면 두 그룹의 size를 곱하여 총 비용에 더해준다.
3. 연결에서 주어진 두 노드를 merge한다.

Comment

Offline Query에 대한 맛보기를 할 수 있었다. union-by-size가 뭔지 모른다면 찾아보기 바란다. Union-Find에서 경로 압축을 해도 편향되는 것을 막을 수 없기에 size에 기반하여 구현하면 이를 해결할 수 있다.

D [3779번] 주기

접근 과정 & 풀이

KMP 알고리즘의 Failure Function (pi배열) 의 성질을 이용한 문제이다.

pi배열 은 문자열의 $i$번째 문자까지의 부분 문자열(길이가 $i$인 접두사)에서 prefix 와 suffix 가 같은 최대 길이이다.

$pi[i] = k$인 부분 문자열에 대해 생각할 때(문자열의 길이는 $i$이라고 하자)

• $k\lt \frac{i}{2}$인 경우는 당연히 반복되는 문자열이 없다.
• $k\geq \frac{i}{2}$인 경우는 prefix와 suffix가 일치하는 부분이 존재하기 때문에 일부분이 반복되는 문자열이 된다.

이때, $i\ \%\ (i-k) = 0$인 경우 $k\geq \frac{i}{2}$에서의 반복되는 부분의 길이가 맞아 떨어지므로, 주기적인 문자열이 된다.

Comment

BOJ 1498번: 주기문 문제를 먼저 풀어보기 바란다.

delena0702님이 위의 접근 과정에서의 pi배열의 property에 대해 설명해주셨다.

E [2543번] 부서 배치

접근 과정

처음에는 Union-Find를 생각하였다. 하지만 해당 풀이로 쉽게 풀리지 않아 다른 풀이를 생각하게 되었다. (Union-Find로도 풀리더라..)

• 모든 노드는 두 가지 그룹 중 1가지로 결정되어야 한다.
• 모든 연결 요소 내에는 반드시 두 그룹의 개수가 결정된다. 모순이 생길 시, 부서 배치가 불가능하다.

bipartite matching과 같은 접근법으로 진행해주었다.

풀이

모든 연결 요소를 순회하며, 두 그룹 간의 차이만 저장한다.
두 그룹의 차이를 저장하였으므로 배열의 값들을 두 그룹으로 나누었을 때, 차이가 최소가 되도록 하는 문제가 된다.

dp를 이용해 해결해주었다. $dp[i]:=i$명의 차이로 부서를 배치할 수 있는가? 로 계산을 해주었다.

Comment

꽤 난이도가 있는 문제였다. bipartite matching 공부를 한지 별로 안돼서 그런지 어찌저찌 접근을 하였다.

총평

다들 굉장히 잘 푸시더라... well known에 해당하는 문제들이 꽤 있어서 정반대의 풀이방식이 나오지는 않았다.

다음 주제

SCC(Strongly Connected Component)
Maximum Flow Algorithm

동아리 내에서 진행되는 알고리즘 스터디 정리본입니다. delena0702 codingstarfish님과 함께 진행하였습니다.