문제 해결력을 높이는 알고리즘과 자료 구조 8-11장 연습 문제 풀이

8장 연습 문제 풀이

9장 연습 문제 풀이

10장 연습 문제 풀이

11장 연습 문제 풀이

 

8-11장에서는 자료 구조를 다룬다. 각 장에서 다루는 자료 구조는 다음과 같다.

• 8장에서는 배열, 연결 리스트, 해시 테이블을 다룬다.
• 9장에서는 스택과 큐를 다룬다.
• 10장에서는 그래프와 트리를 다룬다.
• 11장에서는 Union-Find를 다룬다.

8-10장은 잘 알고 있는 내용이라 가볍게 읽었다.

다만 연습 문제 9.1번은 매우 귀찮았다.

연습 문제 10.5번은 저자의 간략한 수학적 귀납법 풀이에 놀랐다.

 

11장에서는 Union-Find 자료 구조를 다룬다.

Union-Find를 naive하게 구현하면 시간 복잡도는 O(N)이다.

때문에 union by size(rank)나 경로 압축과 같은 최적화 기법을 적용해야 한다.

두 기법을 모두 적용할 시 시간 복잡도는 거의 O(1)이 된다.

 

예전에는 코딩의 간편성 때문에 경로 압축만 사용하였다.

그런데 두 기법을 모두 적용하지 않으면 TLE가 발생하는 문제도 있다고 한다.

또한 경로 압축을 사용할 수 없는 문제도 있다고 한다.

이제부터는 코드가 길어지더라도 두 기법을 모두 사용해야겠다.

 

연습 문제 11.1번은 단절선을 찾는 그래프 알고리즘을 사용할 수도 있다.

연습 문제 11.3번은 UF를 두 번 돌리고 종합하는 부분이 흥미로웠다.

연습 문제 11.4번은 부모로부터의 거리를 별도로 관리해야 한다.

저자는 이를 가중치 UF라고 부르는데 유용한 기법인 듯 하다.

 

끝