알고리즘 {먼데이} 챌린지 3주차

사실 지난 주에 4주차가 있었다.

지난 주는 워낙 바빴고, 주말에 갑자기 감기가 걸리는 바람에 4주차를 까먹고 안 풀었다... ㅠㅠ

5주차는 방금 풀고 왔는데, 어렵기보단 시간을 좀 잡아먹는다. 코딩 테스트처럼.

자세한 이야기는 5주차 블로그를 적게 되면 그때 하도록 하고... 아무튼 3주차 풀이!

 

1. 0커플

그냥 이진 탐색으로 풀었는데, 문제의 조건을 생각하면 단순 합을 통해서 구할 수도 있다.

하지만, 어떤 조건이 와도 범용적으로 사용할 수 있는 이진 탐색도 꼭 알아두면 좋겠다.

 

2. 폴더 폰 자판

각 버튼마다 갖는 목록을 std::string으로 잡아주면 구현이 편리하다.

각 string의 길이로 나눈 나머지를 이용하면 여러번 눌러 원래대로 돌아오는 성질도 포괄할 수 있다.

이처럼 순환되는 목록이 나올 때는 나머지를 이용한 꼼수를 적용할 수 있는지 한 번쯤 생각해 보는 것이 좋다.

 

3. 구름이의 여행

당연히 최단 경로 문제이고,

보기와는 다르게 Floyd-Warshall도 잘 돌아간다.

 

만약 오답에 대한 패널티가 적용되는 대회였다면 시간을 더 소요하더라도 BFS를 구현하는 것을 추천한다.

 

4. 순환하는 수로

구현이 약간 버거울 수 있다.

트리는 정점 $n$개로 이뤄져 있을 경우 간선이 $n-1$개이다.

여기에 간선이 하나 더 추가되면 사이클이 정확히 한 개 생긴다는 사실을 알 수 있다.

이는 오일러 지표를 생각하여 쉽게 증명할 수 있다.

proof) 컴포넌트는 하나니까 $v-e+f=v'-e'+f'$인데, 정점의 개수에 변함이 없으므로 $v=v'$이고 간선을 하나 추가했으므로 $e'=e+1$이어서 $f'=f+1$.

 

이 점을 이용하면 그냥 단순하게 사이클 하나만 찾아주는 문제로 바뀐다.

이는 재귀 함수를 이용해서 잘 생각해서 구현해주면 된다.

 

나는 간선 개수가 $n$개라는 걸 못 봐서 BCC 코드를 찾고 있었다고 한다...