728x90 알고리즘기초6 선택정렬 복습 복습이라고 적은 이유는 이 노트가 컴공들의 선생님 같은 존재인 '나동빈' 선생님의 알고리즘 기초 강의를 보고 작성하는 거기 때문입니다. 선택정렬을 정렬 중에서 가장 기본이고 가장 비효율적인 정렬이라고 할 수 있습니다. 말로 풀어보자면 '가장 작은 수를 선택해서 앞에 수와 바꾼다' 인데요. 일단 가장 작은 수를 선택하기 위해서 배열을 다 돌아야하기 때문에 말로만 들어도 좀 비효율적인 느낌입니다. 그럼 예시를 들어보겠습니다. 다음과 같이 정렬되지 않은 배열이 있습니다. 3 4 1 5 2 배열을 쓱 보고 가장 작은 수를 선택합니다. 1입니다. 그럼 첫번째 수인 3과 교환해줍니다. 1 4 3 5 2 이제 1은 신경쓰지 않아도 됩니다. 2번째 수인 4부터 시작해서 가장 작은 수를 찾아봅니다. 처음부터 봐도 끝까지.. 2020. 5. 26. 서로소 집합 데이터 구조_Abstract Data Type 안녕하세요. 부산 공수니 입니다! 오늘은 서로소 집합 데이터 구조에 대해 알아보겠습니다. 그리디(Greedy) 알고리즘에서 크루스칼(kruscal) 알고리즘에서는 초기 자기자신의 마디(vertex))만 포함된 서로소 부분집합들을 만들고 모든 마디들이 같은 집합에 속할 때까지 되풀이 하여 부분 집합을 합병(merge) 합니다. 이 알고리즘 구현을 위해 서로소 집합에 대한 데이터 구조가 필요합니다. 추상 데이터구조(abstract data type)은 데이터 객체와 그 객체에 대한 연산으로 이루어집니다. 여기선 U 라는 구성요소의 전체영역(universe) 로 시작합니다. ( 글씨가 이쁘지 못한 점 양해 부탁드립니다.) 이 멤버로 부터 집합을 만드는데 필요한 프로시저가 makeset입니다. for(each .. 2020. 5. 20. 이전 1 2 다음 728x90
