제가 2019년 캠퍼스형 공동 교육과정에서 자료구조를 이수하며 정리한 것입니다. 최소 신장 트리 알고리즘 다정고등학교 이정민 - 크러스컬 알고리즘(Kruskal’s algorithm) 크러스컬 알고리즘은 변의 개수를 E 꼭짓점의 개수를 V라고 할 때 O(E log V) 의 시간 복잡도를 가진다. 크러스컬 알고리즘은 아래와 같이 작동한다. 1. 그래프의 각 꼭짓점이 각각 하나의 나무가 되도록 하는 숲A 를 만든다. 2. 모든 변을 원소로 하는 집합 S를 만든다. 3. 집합 S 가 비어있지 않는 동안 - 가장 작은 비용의 변을 S에서 하나 뺀다. - 그 변이 어떤 두개의 나무를 연결한다면 두 나무를 연결하여 하나의 나무로 만든다. - 그렇지 않다면 그 변은 버린다. 이와 다른 형태로, 변을 제거하는 방식이 ..
이제 본격적으로 공부를 시작합시다. 강의를 원활히 진행하기 위해서 구매하신 책을 꼼꼼히 읽으시고codeup.kr 사이트에 회원가입을 해놓으시면 되겠습니다. 먼저, 저희는 코드업(codeup.kr) 사이트에 있는 문제를 풀어볼건데요 그러기 위해서 문제를 찾읍시다. 사이트에 로그인하면 이렇게 되어있고요 왼쪽 상단에 문제라고 쓰여진 곳을 클릭하면 이렇게 나오죠여기서 문제집을 클릭하면이런 화면이 보이겠죠 (저는 내 문제집에 문제들이 이미 있네요 o^_^o) 여기서 왼쪽에 보이는 것들 중에 기초 100제를 클릭합시다. 그러면 문제들이 쫘르르륵 보일거고요 가장 상단에 있는 문제출력하기 1번 문제를 클릭하면 됩니다. 문제를 살펴보면 입력, 출력.. 도움말.. 이런 것들이 보일텐데요 문제 설명은 말 그대로 어떤 문제인..
준비를 마치셨다면 이제 C 개발 환경을 구축해봅시다. 먼저 구글에 접속하고 IDE(통합 개발 환경)을 설치합시다. IDE 가 프로그램 이름은 아니고 IDE인 프로그램을 설치하는 겁니다. 이런거죠 저희가 다운로드할 IDE는 제가 사용하고 있는 DEV C++ 입니다. 먼저, 구글에 들어갑시다. 그리고 구글에서 DEV c++을 검색하고 첫번째로 보이는 사이트 (파란색 밑줄쳐진 사이트)로 들어갑시다. 사이트에서 바로 눈에 띄는 Download를 클릭한뒤 기다려주시면 exe 파일이 설치됩니다. 그 파일을 실행하고 쭉쭉 넘어가시면 DEV C++이 설치됩니다. 이상으로 C 개발 환경 구축을 마칩니다. 모르는 부분 있으면 질문해주세요
크러스컬 알고리즘(Kruskal’s algorithm)이란?최소 비용 생성나무를 찾는 알고리즘이라고 볼수 있다. 일단 우리는 크러스컬 알고리즘을 구현하는 방법에 대하여 알아보겠다. 크러스컬 알고리즘은 다음 순서로 작동한다 1. 그래프의 각 꼭짓점이 각각 하나의 나무가 되도록 하는 숲A 를 만든다.2. 모든 변을 원소로 하는 집합 S를 만든다.3. 집합 S 가 비어있지 않는 동안- 가장 작은 비용의 변을 S에서 하나 뺀다.- 그 변이 어떤 두개의 나무를 연결한다면 두 나무를 연결하여 하나의 나무로 만든다.- 그렇지 않다면 그 변은 버린다. 일단 위키피디아의 말을 보면 어렵게 느껴진다. 그래서 직접 문제를 가져왔다. 크리스컬 알고리즘을 실제로 사용하자! 이 문제는 정보올림피아드 2016년 중고등부 문제 7번..
