[PS스터디 목요일팀] 7차시 6/2 크루스칼 알고리즘 & 투포인터 알고리즘

일시

• 2023년 6월 2일 금요일

모임장소

• 비대면

참여인원

• 김현아, 도소현, 이지혜, 하수민

활동내용

7주차는 그래프 알고리즘 중 하나인 크루스칼 알고리즘과 지난번에 함께 보았던 투포인터 알고리즘을 알아보았습니다. 7차시 스터디에서 풀어본 문제는 다음과 같습니다.

1. https://www.acmicpc.net/problem/1922
2. https://www.acmicpc.net/problem/17609
3. https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

스장의 발목 이슈로 비대면으로 진행이 되었습니다.. 스터디 리드 발목 얼른 낫길 다들 기도 부탁드려요..(!?)

느낀 점

크루스칼 알고리즘을 분명히 학교에서 배웠던 것 같은데 스터디 하면서 또 처음 보는 느낌이 들어서 다소 찔렸지만, 이번 기회를 통해 제대로 알아가는 것 같습니다! 로이님이 푸셨던 구조체를 사용하는 방법을 통해 저도 또한 크루스칼 구조를 다시 알게 된 것 같아요! 크루스칼 문제 풀이는 하는 방법은 대략적으로 다음과 같습니다! 

1. 모든 간선들의 가중치를 오름차순으로 정렬

2. 정렬된 기준으로 가중치가 가장 작은 간선을 선택

3. 2에서 선택한 간선이 연결하려는 2개의 노드가 아직 서로 연결되지 않은 상태라면 서로 연결한다.

4. 위의 과정을 반복한다.

7주차 과제 풀이 및 정리

풀이 코드는 아래의 깃허브 링크에서 확인 가능합니다.

https://github.com/GDSC-Ewha-4th/study-ProblemSolving

GitHub - GDSC-Ewha-4th/study-ProblemSolving: GDSC EWHA's Problem Solving Study Repository

우리의 사진